treenode — Перебалансировка дерева AVL в переполнении стека

Я работаю над деревом 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);
}
}
}

вот мой поворот влево

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, что я передаю каждой из этих функций, чтобы сбалансировать дерево?

1

Решение

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

  • Вы не проверяете, если N является NULL в начале метода
  • Вы не проверяете в строке ниже (и в ее симметричном родственнике), если левый и правый узлы NULL

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

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

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

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]