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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

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

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

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.

 



Поделиться:


Последнее изменение этой страницы: 2020-03-14; просмотров: 1415; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 107.23.157.16 (0.024 с.)