Вращения (Повороты) АВЛ - деревьев .

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 9Следующая ⇒

▷ Похожие статьи

При операциях добавления и удаления может произойти нарушение сбалансированности дерева. В этом случае потребуются некоторые преобразования, не нарушающие упорядоченности дерева и способствующие лучшей сбалансированности.

Рассмотрим такие преобразования.

В каждой вершине дерева помимо значения элемента будем хранить показатель сбалансированности в данной вершине. Показатель сбалансированности - разница между высотами правого и левого поддеревьев.

PTree = ^TTree;

TTree = record

Item: T; {элемент дерева}

Left, Right: PTree; {указатели на поддеревья}

Balance: ShortInt; {показатель сбалансированности}

end;

В сбалансированном дереве показатели сбалансированности всех вершин лежат в пределах от -1 до 1. При операциях добавления/удаления могут появляться вершины с показателями сбалансированности -2 и 2.

Малое левое вращение.

Пусть показатель сбалансированности вершины, в которой произошло нарушение баланса, равен -2, а показатель сбалансированности корня левого поддерева равен -1. Тогда восстановить сбалансированность такого поддерева можно следующим преобразованием, называемым малым левым вращением (рис. 9.):

Рис. 9.

На приведенном рисунке прямоугольниками обозначены поддеревья. Рядом с поддеревьями указана их высота. Поддеревья помечены арабскими цифрами. Кружочками обозначены вершины. Цифра рядом с вершиной - показатель сбалансированности в данной вершине. Буква внутри кружка - условное обозначение вершины. Как видно из рисунка после малого левого вращения показатель сбалансированности вершины, в которой было нарушение баланса, становится равным нулю.

Малое правое вращение.

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

Рис. 10.

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

Несколько сложнее случай, когда показатель сбалансированности в вершине, в которой произошло нарушение баланса равен -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;

}

Рис. 13

Рис. 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;

 }

 np->balanceFactor = balanced;

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

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

 np->Left() = lc;

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

 np->Right() = p;

 p = np;

}

Двойной поворот иллюстрируется на дереве, изображенном на рисунке 17. Попытка вставить узел 25 разбалансирует корневой узел 50. В этом случае узел 20 (LC) приобретает слишком высокое правое поддерево и требуется двойной поворот.

Новым родительским узлом (NP) становится узел 40. Старый родительский узел становится его правым сыном и присоединяет к себе узел 45, который также переходит с левой стороны дерева.

Рис. 17.

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология