Курсовая работа: Реализация АВЛ–деревьев через классы объектно–ориентированного программирования

{

tree->balanceFactor = rightheavy;

reviseBalanceFactor = 1;

}

// вставка справа от узла, перевешивающего влево

// узел станет сбалансированным (случай 2)

else

{

tree->balanceFactor = balanced;

reviseBalanceFactor = 0;

}

}

else

// перебалансировка не требуется. не опрашивать предыдущие узлы

reviseBalanceFactor = 0;

}

Рис. 8.

Метод AVLInsert распознает случай 3, когда нарушается АВЛ - условие. Для выполнения перебалансировки используются методы UpdateLeftTree и UpdateRightTree. Они выполняют одинарный или двойной поворот для уравновешивания узла, а затем сбрасывают флаг reviseBalanceFactor. Перед тем, как обсудить специфические детали поворотов, приведем код функции UpdateLeftTree.

template <class T>

void AVLTree<T>::UpdateLeftTree(AVLTreeNode<T>* &p,

int reviseBalanceFactor)

{

AVLTreeNode<T> *lc;

lc = p->Left();

// перевешивает левое поддерево?

if (lc->balanceFactor == leftheavy)

{

SingleRotateRight(p); // однократный поворот