AVL Tree Rebalancing в C++

Question

Я работаю над деревом AVL. Я думаю, что все функции вращения работают правильно. У меня есть функция rotateleft, rotateright, rotateleftright и rotaterightleft. Все они берут узел в качестве параметра. Я не знаю, какой узел должен пройти к этим параметрам. Можете ли вы взглянуть на мою функцию ребалансировки дерева AVL и сказать мне, правильно ли я это имею, и что мне нужно передать каждой из этих функций. До сих пор у меня есть корень или верхний узел, но я думаю, что я ошибаюсь. Как я могу сказать, что мне нужно передать этим функциям?

Вот функция:

void BinaryTree::rebalance(Node *N) 
{ 
    int count = 1; 
    if((N->getLeft()->getHeight()) > (N->getRight()->getHeight() + 1)) 
    { 
     if(N->getLeft()->getLeft()->getHeight() > N->getLeft()->getRight()->getHeight()) 
     { 
      rotateRight(root); 
      recalculate(root, count); 

     } 

     else 
     { 
      rotateLeftRight(root); 
       recalculate(root, count); 
     } 
    } 
    else if(N->getRight()->getHeight()> N->getLeft()->getHeight() + 1) 
    { 
     if(N->getRight()->getRight()->getHeight() > N->getRight()->getLeft()->getHeight()) 
     { 
      rotateLeft(root); 
       recalculate(root, count); 
     } 

     else 
     { 
      rotateRightLeft(root); 
      recalculate(root, count); 
     } 
    } 
} 

вот мой поворот LeftRight

Node* BinaryTree::rotateLeftRight(Node *N) 
{ 
    Node *newNode = new Node();//declares a new Node 
    newNode = N->getLeft();//sets the node 

    N->setLeft(rotateLeft(newNode->getLeft());//sets the left subtree 
    recalculate(root);//recalculates the height 
    root->setHeight(NULL);//sets the height of the root node 
    return rotateRight(N);//retuns the tree rotated right 
} 

и вот мой поворот налево функция .:

Node* BinaryTree::rotateLeft(Node *N) 
{ 
    Node *newNode = new Node();//declares a new node 
    newNode = N->getRight();//sets the new node to the right child of N 
    N->setRight(newNode->getLeft());//sets the right of N equal to new nodes left child 
    newNode->setLeft(N);//sets the left child of the new node to N 

    return newNode;//retuns the newNode 
} 

, если у меня есть дерево 50 20 10 и 15, что я перехожу к каждой из этих функций, чтобы перебалансировать дерево?

Answer 1

Есть некоторые ошибки в коде, что вы не делали в одном вы указали другой вопрос, что вы не проверять нульарные указатели в коде:

• вы не проверить если N является NULL в начале метода

• вы не проверить в строке ниже (и в симметричном собрате), если правые узлы левых и являются NULL

  if((N->getLeft()->getHeight()) > (N->getRight()->getHeight() + 1)) 
  

Что касается самого алгоритма, это зависит от поведения функций вращения. Алгоритм, описанный в wikipedia entry, объясняет, что второй случай в ваших вложенных if (методы rotateLeftRight и rotateRightLeft) должен выполнять 2 оборота. Если ваши функции вращения соответствуют этому описанию, вы должны быть в порядке.

В случае с recalculate в другой вопрос позаботился, но в этой ситуации вам не нужно пересчитывать высоту для всего поддерева, как вы правильно сказали мне в комментариях к этому вопросу. Единственными изменяющимися узлами являются те, чьи дети были изменены. Вы должны выполнить это вычисление в каждом конкретном методе вращения, поскольку каждый случай описывает точно, какие узлы получают обновление.