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

template <class T>

void AVLTree<T>::AVLInsert(AVLTreeNode<T>* &tree,

AVLTreeNode<T>* newNode, int &reviseBalanceFactor)

{

// флаг "Показатель сбалансированности был изменен"

int rebalanceCurrNode;

// встретилось пустое поддерево, пора вставлять новый узел

if (tree == NULL)

{

// вставить новый узел

tree = newNode;

// объявить новый узел сбалансированным

tree->balanceFactor = balanced;

// сообщить об изменении показателя сбалансированности

reviseBalanceFactor = 1;

}

// рекурсивно спускаться по левому поддереву, если новый узел меньше текущего

else if (newNode->data < tree->data)

{

AVLInsert(tree->Left(), newNode, rebalanceCurrNode);

// проверить, нужно ли корректировать balanceFactor

if (rebalanceCurrNode)

{

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

// условие сбалансированности; выполнить поворот (случай 3)

if (tree->balanceFactor == leftheavy)

UpdateLeftTree(tree, reviseBalanceFactor);

// вставка слева от сбалансированного узла.

// узел станет перевешивать влево (случай 1)