У меня труднее всего пытаться выяснить, как сбалансировать дерево AVL для моего класса. У меня есть вставка с этим:
Node* Tree::insert(int d)
{
cout << "base insert\t" << d << endl;
if (head == NULL)
return (head = new Node(d));
else
return insert(head, d);
}
Node* Tree::insert(Node*& current, int d)
{
cout << "insert\t" << d << endl;
if (current == NULL)
current = new Node(d);
else if (d < current->data) {
insert(current->lchild, d);
if (height(current->lchild) - height(current->rchild)) {
if (d < current->lchild->getData())
rotateLeftOnce(current);
else
rotateLeftTwice(current);
}
}
else if (d > current->getData()) {
insert(current->rchild, d);
if (height(current->rchild) - height(current->lchild)) {
if (d > current->rchild->getData())
rotateRightOnce(current);
else
rotateRightTwice(current);
}
}
return current;
}
Мой план состоял в том, чтобы вызвать уравновешивание(), чтобы проверить, нужно ли балансировать дерево, а затем балансировать по мере необходимости. Проблема в том, что я даже не могу понять, как пройти дерево, чтобы найти правильный неуравновешенный node. Я знаю, как рекурсивно пересекать дерево, но я не могу перевести этот алгоритм на поиск самого низкого неуравновешенного node. У меня также возникла проблема с написанием итерационного алгоритма. Любая помощь будет оценена по достоинству.:)