AVL-деревья

Описание Константы leftheavy, balanced и rightheavy используются в операциях вставки/удаления для описания показателя сбалансированности узла. Метод GetAVLTreeNode управляет выделением памяти для экземпляра класса. По умолчанию balanceFactor нового узла равен нулю. clip0073Рис. 5. В этом классе заново определяется функция CopyTree для использования с конструктором копирования и перегруженным оператором присвоения. Несмотря на то, что алгоритм идентичен алгоритму для функции CopyTree класса BinSTree, новая версия корректно создает расширенные объекты типа AVLTreeNode при построении нового дерева. Функции AVLInsert и AVLDelete реализуют методы Insert и Delete, соответственно. Они используют скрытые методы наподобие SingleRotateLeft. Открытые методы Insert и Delete объявлены виртуальными и подменяют соответствующие функции базового класса. Остальные операции наследуются от класса BinSTree. Код, приведенный ниже, создает деревья, приведенные на рисунке 5. После удаления из AVL-дерева (В) элемента 3 AVL-дерево принимает вид, изображенный на рисунке 5 (С). Цифра после двоеточия означает фактор сбалансированности.

AVLTree < int > avltree; // AVLTree-список целых чисел
BinSTree < int > bintree; // BinSTree-список целых чисел
for (int i = 1; i <= 5; i + +)
 {
 bintree.Insert(i); // создать дерево А
 avltree.Insert(i); // создать дерево В
}

avltree.Delete(3); // удалить 3 из AVL-дерева
// дерево (С) есть дерево (В) без удаленного узла 3.

Распределение памяти для AVLTree
Класс AVLTree образован от класса BinSTree и наследует большинство его операций. Для создания расширенных объектов типа AVLTreeNode мы разработали отдельные методы выделения памяти и копирования.

// разместить в памяти объект типа AVLTreeNode. прервать программу,

// если во время выделения памяти произошла ошибка

template < class T >

 AVLTreeNode < T > * AVLTree < T > : : GetAVLTreeNode(const T item,

  AVLTreeNode < T > * lptr, AVLTreeNode < T > * rptr)

 {

  AVLTreeNode<T> *p;

  p = new AVLTreeNode<T> (item, lptr, rptr);

  if (p == NULL)

  {

  cerr <lt; "Ошибка выделения памяти!" lt;lt; endl;

  exit(1);

  }


 return p;

 }

Для удаления узлов AVL-дерева достаточно методов базового класса. Метод DeleteTree из класса BinSTree задействует виртуальный деструктор класса TreeNode.
Метод Insert класса AVLTree
Преимущество AVL-деревьев состоит в их сбалансированности, которая поддерживается соответствующими алгоритмами вставки/удаления. Опишем метод Insert для класса AVLTree. При реализации метода Insert для запоминания элемента используется рекурсивная функция AVLInsert. Сначала приведем код метода Insert на С++, а затем сосредоточим внимание на рекурсивном методе AVLInsert, реализующем алгоритм Адельсона-Вельского и Ландиса.
template < class T >

 void AVLTreelt;

Tgt;

: : Insert(const T item)

{

 // объявить указатель AVL-дерева, используя метод

 // базового класса GetRoot.

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

 AVLTreeNodelt;Tgt; *treeRoot = (AVLTreeNodelt;Tgt; *)GetRoot(),

 *newNode;

 // флаг, используемый функцией AVLInsert для перебалансировки узлов

 int reviseBalanceFactor = 0;

 // создать новый узел AVL-дерева с нулевыми полями указателей

 newNode = GetAVLTreeNode(item, NULL, NULL);

 // вызвать рекурсивную процедуру для фактической вставки элемента

 AVLInsert(treeRoot, newNode, reviseBalancefactor);

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

 root = treeRoot;

 current = newNode;

 size++;

}

Ядром алгоритма вставки является рекурсивный метод AVLInsert. Как и его аналог в классе BinSTree, этот метод осуществляет прохождение левого поддерева, если item меньше данного узла, и правого поддерева, если item больше или равен данному узлу. При сканировании левого или правого поддерева некоторого узла анализируется флаг revisebalanceFactor, который является признаком изменения любого параметра balanceFactor в поддереве. Если он установлен, то нужно проверить, сохранилась ли AVL-сбалансированность всего дерева. Если в результате вставки нового узла она оказалась нарушенной, то мы обязаны восстановить равновесие. Данный алгоритм рассматривается на ряде примеров.
Алгоритм AVL-вставки
Процесс вставки почти такой же, что и для бинарного дерева поиска. Осуществляется рекурсивный спуск по левым и правым сыновьям, пока не встретится пустое поддерево, а затем производится пробная вставка нового узла в этом месте. В течение этого процесса мы посещаем каждый узел на пути поиска от корневого к новому элементу.
Поскольку процесс рекурсивный, обработка узлов ведется в обратном порядке. При этом показатель сбалансированности родительского узла можно скорректировать после изучения эффекта от добавления нового элемента в одно из поддеревьев. Необходимость корректировки определяется для каждого узла, входящего в поисковый маршрут. Есть три возможных ситуации. В двух первых случаях узел сохраняет сбалансированность и реорганизация поддеревьев не требуется. Нужно лишь скорректировать показатель сбалансированности данного узла. В третьем случае разбалансировка дерева требует одинарного или двойного поворотов узлов.
Случай 1. Узел на поисковом маршруте изначально является сбалансированным (balanceFactor = 0). После вставки в поддерево нового элемента узел стал перевешивать влево или вправо в зависимости от того, в какое поддерево была произведена вставка. Если элемент вставлен в левое поддерево, показателю сбалансированности присваивается -1, а если в правое, то 1. Например, на пути 40-50-60 каждый узел сбалансирован. После вставки узла 55 показатели сбалансированности изменяются (рисунок 6).
clip0074Рис. 6.
Случай 2. Одно из поддеревьев узла перевешивает, и новый узел вставляется в более легкое поддерево. Узел становится сбалансированным. Сравните, например, состояния дерева до и после вставки узла 55 (рисунок 7).
Случай 3. Одно из поддеревьев узла перевешивает, и новый узел помещается в более тяжелое поддерево. Тем самым нарушается условие сбалансированности, так как balanceFactor выходит за пределы -1..1. Чтобы восстановить равновесие, нужно выполнить поворот.
clip0075Рис. 7.
Рассмотрим пример. Предположим, дерево разбалансировалось слева и мы восстанавливаем равновесие, вызывая одну из функций поворота вправо. Разбалансировка справа влечет за собой симметричные действия.
Сказанное иллюстрируется рисунком 8. При разработке алгоритма поворота мы включили дополнительные детали.
Метод AVLInsert
Продвигаясь вдоль некоторого пути для вставки нового узла, рекурсивный метод AVLInsert распознает все три указанных выше случая корректировки. При нарушении условия сбалансированности восстановление равновесия &;#1086;существляется с помощью функций UpdateLeftTree и UpdateRightTree.
template < class T >

 void AVLTreelt;

Tgt;

: : AVLInsert(AVLTreeNodelt; Tgt; * tree,

 AVLTreeNodelt; Tgt; * newNode, int reviseBalanceFactor)

{

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

 int rebalanceCurrNode;

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

 if (tree == NULL)

 {

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

  tree = newNode;

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

  tree-gt;balanceFactor = balanced;

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

  reviseBalanceFactor = 1;

 }


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

else if (newNode - gt; data lt; tree - gt; data)

 {

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

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

 if (rebalanceCurrNode)

 {

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

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

  if (tree-gt;balanceFactor == leftheavy)

  UpdateLeftTree(tree, reviseBalanceFactor);

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

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

  else if (tree-gt;balanceFactor == balanced)

  {

  tree-gt;balanceFactor = leftheavy;

  reviseBalanceFactor = 1;

  }


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

  // узел станет сбалансированным (случай 2)

else

 {

  tree-gt;balanceFactor = balanced;

  reviseBalanceFactor = 0;

 }


 }

else

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

 reviseBalanceFactor = 0;

 }

  // иначе рекурсивно спускаться по правому поддереву

else if (newNode - gt; data lt; tree - gt; data)

 {

 AVLInsert(tree-gt;Right(), newNode, rebalanceCurrNode);

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

 if (rebalanceCurrNode)

 {

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

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

  if (tree-gt;balanceFactor == rightheavy)

  UpdateRightTree(tree, reviseBalanceFactor);

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

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

  else if (tree-gt;balanceFactor == balanced)

  {

  tree-gt;balanceFactor = rightheavy;

  reviseBalanceFactor = 1;

  }


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

  // узел станет сбалансированным (случай 2)

else

 {

  tree-gt;balanceFactor = balanced;

  reviseBalanceFactor = 0;

 }


 }

else

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

 reviseBalanceFactor = 0;

 }

  }

clip0076Рис. 8. Метод AVLInsert распознает случай 3, когда нарушается AVL-условие. Для выполнения перебалансировки используются методы UpdateLeftTree и UpdateRightTree. Они выполняют одинарный или двойной поворот для уравновешивания узла, а затем сбрасывают флаг reviseBalanceFactor. Перед тем, как обсудить специфические детали поворотов, приведем код функции UpdateLeftTree.

template < class T >
 void AVLTreelt;
Tgt;
: : UpdateLeftTree(AVLTreeNodelt; Tgt; * p,
 int reviseBalanceFactor)
{
 AVLTreeNodelt;Tgt; *lc;
 lc = p-gt;Left();
 // перевешивает левое поддерево?
 if (lc-gt;balanceFactor == leftheavy)
 {
  SingleRotateRight(p); // однократный поворот
  reviseBalanceFactor = 0;
 }

 // перевешивает правое поддерево?
else if (lc - gt; balanceFactor = = rightheavy)
 {
 // выполнить двойной поворот
 DoubleRotateRight(p);
 // теперь корень уравновешен
 reviseBalanceFactor = 0;
}

}

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

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

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

template < class T >

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

 {

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

  AVLTreeNode<T> *lc;

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

  lc = p->Left();

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

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

  p-gt;balanceFactor = balanced;

  lc-gt;balanceFactor = balanced;

  // правое поддерево узла lc в любом случае должно оставаться справа

  // от lc. выполнить это условие, сделав st левым поддеревом узла p

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

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

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

  lc-gt;Right() = p;

  p = lc;

 }

clip0077Рис. 9.
clip0078Рис. 10.
Попытка вставить узел 5 в изображенное на рисунке 10 AVL-дерево нарушает AVL-условие для узла 30. Одновременно левое поддерево узла 15 (LC) становится перегруженным. Для переупорядочения узлов вызывается процедура SingleRotateRight. В результате родительский узел (30) становится сбалансированным, а узел 10 перевешивающим влево.
Двойной поворот вправо (double rigyn rotation) нужен тогда, когда родительский узел (P) становится перевешивающим влево, а его левый сын (LC) перевешивающим вправо. NP – корень правого перевешивающего поддерева узла LC. Тогда в результате поворота узел NP замещает родительский узел. На рисунках 11 и 12 показаны случаи вставки нового узла в качестве сына узла NP. В обоих случаях NP становится родительским узлом, а бывший родитель P становится правым сыном NP.
На рисунке 11 мы видим сдвиг узла X1, после того как он был вставлен в левое поддерево узла NP. На рисунке 12 изображено перемещение узла X2 после его вставки в правое поддерево NP.
clip0079Рис. 11.
clip0080Рис. 12.
// двойной поворот вправо вокруг узла 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;

 }

Отправить комментарий

Проверка
Антиспам проверка
Image CAPTCHA
...