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

Рис. 14.

Попытка вставить узел 5 в изображенное на рисунке 14 АВЛ - дерево нарушает АВЛ - условие для узла 30. Одновременно левое поддерево узла 15 (LC) становится перегруженным.

Для переупорядочения узлов вызывается процедура SingleRotateRight. В результате родительский узел (30) становится сбалансированным, а узел 10 перевешивающим влево. Двойной поворот вправо (double right rotation) нужен тогда, когда родительский узел (P) становится перевешивающим влево, а его левый сын (LC) перевешивающим вправо. NP – корень правого перевешивающего поддерева узла LC. Тогда в результате поворота узел NP замещает родительский узел. На рисунках 15 и 16 показаны случаи вставки нового узла в качестве сына узла NP. В обоих случаях NP становится родительским узлом, а бывший родитель P становится правым сыном NP.

На рисунке 15 мы видим сдвиг узла X1, после того как он был вставлен в левое поддерево узла NP. На рисунке 16 изображено перемещение узла X2 после его вставки в правое поддерево NP.

Рис. 15.

Рис. 16

// двойной поворот вправо вокруг узла p

template <class T>

void AVLTree<T>::DoubleRotateRight (AVLTreeNode<T>* &p)

{

// два поддерева, подлежащих повороту

AVLTreeNode<T> *lc, *np;

// узел lc <= узел np < узел p

lc = p->Left(); // левый сын узла p

np = lc->Right(); // правый сын узла lc

// обновить показатели сбалансированности в узлах p, lc и np

if (np->balanceFactor == rightheavy)

{

p->balanceFactor = balanced;

lc->balanceFactor = rightheavy;

}

else

{

p->balanceFactor = rightheavy;

lc->balanceFactor = balanced;

}