Функция баланса дерева AVL не может установить новую высоту после балансировки

Я пытался реализовать дерево AVL в C ++, и я считаю, что я запрограммировал все правильно, за исключением одной строки. Структура программы следующая.

    struct AvlNode
{
int key;
int height;
AvlNode *left;
AvlNode *right;
AvlNode(int key1, int height1 = 0, AvlNode *left1 = NULL, AvlNode *right1 = NULL)
{
key = key1;
height = height1;
left = left1;
right = right1;
}
};

class AvlTree
{
private:
AvlNode * root;
void destroySubTree(AvlNode * v);//destroy a subtree rooted at v
void displayPreOrder(AvlNode *);//pre-order traversal
void displayInOrder(AvlNode *);//in-order traversal
void displayPostOrder(AvlNode *);//post-order traversal
void remove(AvlNode * &, int);//remove
void insert(AvlNode * &, int);//insert
void balance(AvlNode * &); //make the tree balanced after each insert/remove
void rightRotate(AvlNode * &);//right rotation
void leftRotate(AvlNode * &);//left rotation
void doubleLeftRightRotate(AvlNode * &);//left right double rotation
void doubleRightLeftRotate(AvlNode * &);//right left double rotation

public:
AvlTree() { root = NULL; }
~AvlTree() { destroySubTree(root); }
AvlNode * search(int);
void displayPreOrder() { displayPreOrder(root); }
void displayInOrder() { displayInOrder(root); }
void displayPostOrder() { displayPostOrder(root); }
void insert(int x) { insert(root, x); }//insert a new key x
void remove(int x) { remove(root, x); }//remove a key x
int getHeight(AvlNode * v);//return the height of node v
int getTreeHeight() { return getHeight(root); }//return the height of the tree
int getRoot() { return root->key; }//return the root
int max(int x, int y);
};

Таким образом, у меня возникает проблема с методом баланса, который заключается в следующем:

void AvlTree::balance(AvlNode * & v)
{
if (v == NULL)
{
return;
}
if ((getHeight(v->left) - getHeight(v->right)) > 1)
{
if (getHeight(v->left->left) >= getHeight(v->left->right))
rightRotate(v);
else
doubleLeftRightRotate(v);
}
if ((getHeight(v->right) - getHeight(v->left)) > 1)
{
if (getHeight(v->right->left) >= getHeight(v->right->right))
doubleRightLeftRotate(v);
else
leftRotate(v);
}
v->height = 1 + max(getHeight(v->left), getHeight(v->right));
}

Последняя строка метода — то, где компилятор волнуется на меня. При запуске программы Visual Studio сообщает, что source.exe перестал работать. Это потому, что я не могу напрямую назначить высоту узла, как я пытался? Если нет, что может быть потенциальным решением этой проблемы здесь? Я пробовал много разных способов установить высоту узла после балансировки, но это просто не позволит. Спасибо за помощь в продвижении!

Когда я запускаю программу в отладчике, она останавливается на первой строке метода rightRotate:

void AvlTree::rightRotate(AvlNode * & k2)
{
AvlNode * k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = 1 + max(getHeight(k2->left), getHeight(k2->right));
k1->height = 1 + max(getHeight(k1->left), k2->height);
k2 = k1;
}

0

Решение

Задача ещё не решена.

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