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

Большое левое вращение.

Несколько сложнее случай, когда показатель сбалансированности в вершине, в которой произошло нарушение баланса равен -2, а показатель сбалансированности в корне левого поддерева равен 1 или 0. В этом случае применяется преобразование, называемое большим левым вращением. Как видно из рисунка 11 здесь во вращении участвуют три вершины, а не две как в случае малых вращений.

Рис. 11.

Большое правое вращение.

Большое правое вращение применяется, когда показатель сбалансированности вершины, в которой произошло нарушение баланса, равен 2, а показатель сбалансированности корня правого поддерева равен -1 или 0. Большое правое вращение симметрично большому левому и схематично изображено на рисунке 12:

Рис. 12.

Повороты необходимы, когда родительский узел P становится разбалансированным. Одинарный поворот вправо (single right rotation) происходит тогда, когда родительский узел P и его левый сын LC начинают перевешивать влево после вставки узла в позицию X. В результате такого поворота LC замещает своего родителя, который становится правым сыном. Бывшее правое поддерево узла LC (ST) присоединяется к P в качестве левого поддерева. Это сохраняет упорядоченность, так как узлы в ST больше или равны узлу LC, но меньше узла P. Поворот уравновешивает как родителя, так и его левого сына (рис. 13).

// выполнить поворот по часовой стрелке вокруг узла p

// сделать lc новой точкой вращения

template <class T>

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

{

// левое, перевешивающее поддерево узла p

AVLTreeNode<T> *lc;

// назначить lc левым поддеревом

lc = p->Left();

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

p->balanceFactor = balanced;

lc->balanceFactor = balanced;

// правое поддерево узла lc в любом случае должно оставаться справа от lc, выполнить это условие, сделав st левым поддеревом узла p

p->Left() = lc->Right();

// переместить p в правое поддерево узла lc

// сделать lc новой точкой вращения

lc->Right() = p;

p = lc;

}