Реализовать программу для работы с типом данных ”Дерево”

  1. Задание

Написать программу, реализующую  структуру данных АВЛ-деревья. Программа  должна выполнять следующие функции:

    • Создание дерева.
    • Добавление узла в дерево.
    • Удаление узла из дерева.
    • Поиск узла по значению.
    • Поиск минимального по значению узла.
    • Поиск максимального по значению узла.
    • Восстановление баланса дерева.
    • Поиск упорядоченного бинарного дерева поиска максимальной высоты.
    • Вывод дерева на экран в виде рисунка.

Программа должна быть реализована  на Windows Forms в среде программирования C++ Builder 6.

  1. Теория

Одним из направлений в  разработке алгоритмов поиска данных является организация поиска данных, имеющих древовидную структуру. Анализ деревьев только с точки зрения представления данных в виде иерархической  структуры, позволяет сделать вывод  о том, что существенного выигрыша при организации поиска не получится. Сравнение ключа поиска с ключами  узлов дерева необходимо провести для  всех элементов дерева.

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

Двоичным деревом поиска (ДДП) называют дерево, все вершины  которого упорядочены, каждая вершина  имеет не более двух потомков (назовём  их левым и правым), и все вершины, кроме корня, имеют родителя. Вершины, не имеющие потомков, называются листами. Подразумевается, что каждой вершине  соответствует элемент или несколько  элементов, имеющие некие ключевые значения, в дальнейшем именуемые  просто ключами. Обычно одной вершине соответствует один элемент, поэтому данные термины можно без потери смысла считать синонимами, хотя и надо помнить, что в некоторых реализациях это не так. В приведённых алгоритмах считается, что одной вершине соответствует только один элемент. Поэтому мы будем использовать понятия ключа вершины и данных вершины, подразумевая ключ и данные соответствующего вершине элемента. Мы так же будем понимать под вставкой вершины добавление вершины с указанным значением элемента и присвоение указателям на родителя и потомков корректных значений. Именно ключ используется во всех операциях сравнения элементов. Элемент может также содержать ассоциированные с ключом данные. На практике в качестве ключа может использоваться часть данных элемента. Ключ также может храниться как отдельное значение. ДДП позволяет выполнять следующие основные операции:

  • Поиск вершины по ключу.
  • Определение вершин с минимальным и максимальным значением ключа.
  • Переход к предыдущей или последующей вершине, в порядке, определяемом ключами.
  • Вставка вершины.
  • Удаление вершины.

Двоичное дерево может  быть логически разбито на уровни. Корень дерева является нулевым уровнем, потомки корня – первым уровнем, их потомки – вторым, и т.д. Глубина  дерева это его максимальный уровень. Понятие глубины также может  быть описано в терминах пути, то есть глубина дерева есть длина самого длинного пути от корня до листа, если следовать от родительской вершины  до потомка. Каждую вершину дерева можно  рассматривать как корень поддерева, которое определяется данной вершиной и всеми потомками этой вершины, как прямыми, так и косвенными. Поэтому о дереве можно говорить как о рекурсивной структуре. Эффективность поиска по дереву напрямую связана с его сбалансированностью, то есть с максимальной разницей между  глубиной левого и правого поддерева  среди всех вершин. Имеется два  крайних случая – сбалансированное бинарное дерево (где каждый уровень  имеет полный набор вершин) и вырожденное  дерево, где на каждый уровень приходится по одной вершине. Вырожденное дерево эквивалентно связанному списку. Время  выполнения всех основных операций пропорционально  глубине дерева. Таким образом, скоростные характеристики поиска в ДДП могут  варьироваться от O(log2N) в случае законченного дерева до O(N) – в случае вырожденного.

ДДП может быть использовано для реализации таких абстракций, как сортированный список, словарь (набор соответствий "ключ-значение"), очередь с приоритетами и так  далее.

При реализации дерева помимо значения ключа (key) и данных также  хранятся три указателя: на родителя (net), левого (left) и правого (right) потомков. Если родителя или потомка нет, то указатель хранит нулевое (NULL, NIL) значение.

    1. Свойство упорядоченности  двоичного дерева поиска

Если x – это произвольная вершина в ДДП, а вершина y находится  в левом поддереве вершины x, то y.key <= x.key. Если x – это произвольная вершина ДДП, а вершина y находится  в правом поддереве вершины x, то y.key >= x.key. Из свойства следует, что  если y.key == x.key, то вершина y может находиться как в левом, так и в правом поддереве относительно вершины x.

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

Это двоичное дерево поиска:

Рис. 2.1.

А это нет:

Рис. 2.2.

    1. Способы обхода ДДП

Есть три способа обхода: Прямой (preorder), Поперечный (inorder), Обратный (postorder).

  • Прямой обход: сначала обходится данная вершина, левое поддерево данной вершины, затем правое поддерево данной вершины.
  • Поперечный обход: сначала обходится левое поддерево данной вершины, затем данная вершина, затем правое поддерево данной вершины. Вершины при этом будут следовать в неубывающем (по ключам key) порядке.
  • Обратный обход: сначала обходится левое поддерево данной вершины, затем правое, затем данная вершина.

На рисунке 3 порядок обхода вершин указан номерами, при этом предполагается, что сами вершины расположены  так, что образуют ДДП.

Рис. 2.3.

 

Наиболее часто употребляется  поперечный обход, так как во всех других способах обхода следующие друг за другом вершины не связаны никакими условиями отношения.

    1. Поиск вершины в  ДДП

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

Рекурсивно:

TreeSearch(node, key)

Begin

  // Если вершина равна NIL, то нечего в ней искать. Так же и возвращаем.

  // Это нужно для поиска по не существующим потомкам

  If (node == NIL) Then

    Return node;

  // Если нашли, то возвращаем указатель на найденную вершину.

  If (node.key == key) Then

    Return node;

  // Если ключ найденной вершины больше того, который мы ищем

  If (node.key > key) Then

    // То искать в левом поддереве

    Return TreeSearch(node.left, key);

  Else

    // Иначе в правом поддереве

    Return TreeSearch(node.right, key);

End

Итеративно:

TreeSearch(node,key)

Begin

  // Пока ещё есть вершины среди которых можно искать

  //(мы просматриваем не все, но несколько) и пока мы не нашли

  While (node != NIL) and (node.key != key) Do

  Begin

    // Если ключ найденногй вершины больше того который мы ищем

    If (node.key > key) Then

      node = node.left; // То искать в левом поддереве

    Else

      node = node.right; // А иначе в правом поддереве

    End

  Return node; // Возвратить найденное

End

    1. Поиск вершины с  минимальным и максимальным значением  ключа

Вершины с минимальным  и максимальным значением ключа  можно найти, пройдясь по левым (правым) указателям от корня (пока не достигнем NIL). Возвращаемое значение – это  указатель на вершину с минимальным (максимальным) значением ключа.

TreeMinimum(node)

Begin

  While (node.left != NIL) Do // Пока есть левый потомок

    Node = node.left; // Перейти к нему

  Return node;

End

 

TreeMaximum(node)

Begin

  While (node.right != NIL) Do // Пока есть правый потомок

    node = node.right; // Перейти к нему

  Return node;

End

    1. Добавление вершины

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

TreeInsert(Tree,node)

Begin

  nodeParent = NIL;

  nodeTemp = T.root;

  // Пока ещё есть вершины которые надо просмотреть, то

  // есть пока мы не добрались до “листочков” дерева

  While (nodeTemp != NIL) Do

  Begin

    nodeParent = nodeTemp;

    // Если ключ вершины, которую мы хотим вставить,

    // меньше ключа текущей вершины

    If (node.key < nodeTemp.key) Then

      nodeTemp = nodeTemp.left; // То он должен быть в его левом поддереве

    Else

      nodeTemp = nodeTemp.right; // А иначе в правом

  End

  node.nodeParent = nodeParent;

  If (nodeParent == NIL) Then // Если в дереве ещё нет вершин

    Tree.root = node; // То добавить первую

  Else

  Begin

    // Если ключ вершины, которую мы хотим вставить,

    // меньше ключа вершины, потомком которой должна стать

    // вставляемая вершина

    If (node.key < nodeParent.key) Then

      nodeParent.left = node; // То добавить в дерево как левого потомка

    Else

      nodeParent.right = node; // Иначе добавить в дерево как правого потомка

  End

End

    1. Удаление вершины

Проблемы возникают и  при удалении. Нам необходимо сохранить  свойство упорядоченности ДДП. При  удалении возможны три случая: у  удаляемой вершины нет потомков, у удаляемой вершины есть один потомок и у удаляемой вершины  два потомка. Если потомков нет, то вершину  можно просто удалить. Если потомок  один, то удаляемую вершину можно  “вырезать”, указав её родителю в качестве потомка единственного имеющегося потомка удаляемой вершины. Если же потомков два, требуются дополнительные действия. Нужно найти следующую  за удаляемой (по порядку ключей) вершину, скопировать её содержимое (ключ и  данные) в удаляемую вершину (она  теперь никуда не удаляется физически, хотя логически исчезает) и удалить  найденную вершину (у неё не будет  левого потомка). Сначала функция TreeDelete ищет вершину, которую надо удалить, затем переменной nodeTemp присваивается указатель на существующего потомка удаляемой вершины (или NIL, если потомков нет). Далее вершина удаляется из дерева, при этом отдельно рассматриваются случаи: когда потомков нет и когда удаляемая вершина – это корень дерева. Возвращаемое значение – это указатель на удалённую вершину. На неё уже нет никаких ссылок в самом дереве, но она всё ещё занимает память. Момент её реального удаления зависит от используемых методов распределения памяти.

TreeDelete(Tree,node)

Begin

  // Если потомков не более одного (случаи 1 и 2)

  If (node.left == NIL) or (node.right == NIL) Then

    del = node; // физически удаляем текущую вершину

  Else

    del = TreeNext(node); // Иначе следующую

  If (del.left != NIL) Then // Пытаемся найти хоть одного потомка

    nodeTemp = del.left;

  Else

    nodeTemp = del.right;

  // Если есть, родителем потомка делаем родителя

  // удаляемой вершины (случай 2)

  If (nodeTemp != NIL) Then

    nodeTemp.nodeParent = del.nodeParent;

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

  If (del.nodeParent == NIL) Then

    Tree.root = nodeTemp;

  Else

  Begin

    // Указываем родителю удаляемой вершины качестве потомка

    // потомок удаляемой вершины

    If (del.nodeParent.left == del) Then

      del.nodeParent.left = nodeTemp;

    Else

      del.nodeParent.right = nodeTemp;

  End

  If (del != node) Then // Если случай 3

  Begin

    node.key = del.key; // Скопировать ключ

    { копирование дополнительных данных }

  End

  Return del;

End

    1. Случайные деревья  поиска

Случайные деревья поиска представляют собой упорядоченные бинарные деревья поиска, при создании которых элементы (их ключи) вставляются в случайном порядке.

При создании таких деревьев используется тот же алгоритм, что  и при добавлении вершины в  бинарное дерево поиска. Будет ли созданное  дерево случайным или нет, зависит  от того, в каком порядке поступают  элементы для добавления. Примеры  различных деревьев, создаваемых  при различном порядке поступления  элементов, приведены ниже (рис. 2.4).

При поступлении элементов  в случайном порядке получаем дерево с минимальной высотой h (рис. 2.4А), при этом минимизируется время поиска элемента в дереве, которое пропорционально O(log n). При поступлении элементов в упорядоченном виде (рис. 2.4В) или в порядке с единичными сериями монотонности (рис. 2.4С) происходит построение вырожденных деревьев поиска (оно вырождено в линейный список), что нисколько не сокращает время поиска, которое составляет O(n).

 

 
Рис. 2.4. Случайные деревья поиска

    1. Сбалансированные  по высоте деревья

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

Однако идеальную сбалансированность довольно трудно поддерживать. В некоторых  случаях при добавлении или удалении элементов может потребоваться  значительная перестройка дерева, не гарантирующая логарифмической  сложности. В 1962 году два советских  математика: Г.М. Адельсон-Вельский и  Е.М. Ландис ввели менее строгое  определение сбалансированности и  доказали, что при таком определении  можно написать программы добавления и/или удаления, имеющие логарифмическую  сложность и сохраняющие дерево сбалансированным. Дерево считается сбалансированным по АВЛ (сокращения от фамилий Г.М. Адельсон-Вельский и Е.М. Ландис), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное по АВЛ дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано по АВЛ.

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

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

Пусть вершина a имеет правый потомок b. Обозначим через P левое  поддерево вершины a, через Q и R –  левое и правое поддеревья вершины b соответственно. Упорядоченность  дерева требует, чтобы P<a<Q<b<R. Точно  того же требует упорядоченность  дерева с корнем b, его левым потомком a, в котором P и Q – левое и правое поддеревья вершины a, R – правое поддерево  вершины b. Поэтому первое дерево можно  преобразовать во второе, не нарушая  упорядоченности. Такое преобразование называется малым правым вращением (рис. 2.5). Аналогично определяется симметричное ему малое левое вращение.

 
Рис. 2.5. Малое правое вращение АВЛ-дерева

 

Пусть b – правый потомок  вершины a, c – левый потомок вершины b, P – левое поддерево вершины a, Q и R – соответственно левое и  правое поддеревья вершины c, S – правое поддерево b. Тогда P<a<Q<c<R<b<S. Такой  же порядок соответствует дереву с корнем c, имеющим левый потомок a и правый потомок b, для которых P и Q – поддеревья вершины a, а R и S – поддеревья вершины b. Соответствующее преобразование будем называть большим правым вращением (рис. 2.6). Аналогично определяется симметричное ему большое левое вращение.

 
Рис. 2.6.  Большое правое вращение АВЛ-дерева

 

Схематично алгоритм добавления нового элемента в сбалансированное по АВЛ дерево будет состоять из следующих трех основных шагов.

Шаг 1. Поиск по дереву.

Шаг 2. Вставка элемента в  место, где закончился поиск, если элемент  отсутствует.

Шаг 3. Восстановление сбалансированности.

Первый шаг необходим  для того, чтобы убедиться в  отсутствии элемента в дереве, а  также найти такое место вставки, чтобы после вставки дерево осталось упорядоченным. Третий шаг представляет собой обратный проход по пути поиска: от места добавления к корню дерева. По мере продвижения по этому пути корректируются показатели сбалансированности проходимых вершин, и производится балансировка там, где это необходимо. Добавление элемента в дерево никогда  не требует более одного поворота.

Алгоритм удаления элемента из сбалансированного дерева будет выглядеть так:

Шаг 1. Поиск по дереву.

Шаг 2. Удаление элемента из дерева.

Шаг 3. Восстановление сбалансированности дерева (обратный проход).

Первый шаг необходим, чтобы найти в дереве вершину, которая должна быть удалена. Третий шаг представляет собой обратный проход от места, из которого взят элемент  для замены удаляемого, или от места, из которого удален элемент, если в  замене не было необходимости. Операция удаления может потребовать перебалансировки всех вершин вдоль обратного пути к корню дерева, т.е. порядка log n вершин. Таким образом, алгоритмы поиска, добавления и удаления элементов в сбалансированном по АВЛ дереве имеют сложность, пропорциональную O(log n).

    1. Включение нового элемента в AVL - дерево

Рассмотрим операцию включения  в сбалансированное дерево нового узла. Пусть дан узел a  с левым и правым поддеревьями L и R. Предположим, что новый узел включается в L, вызывая увеличение его высоты на 1.

Рис. 2.7.

Возможны 3 случая после включения:

1.      Если hL = hR до включения, то L и R становятся неравной высоты, но критерий сбалансированности не нарушен.

2.      Если hL < hR до включения, то L и R становятся равной высоты и сбалансированность даже  улучшается.

3.      Если hL > hR до включения, то критерий сбалансированности нарушается, и дерево нужно перестраивать.

Рассмотрим случаи нарушения  сбалансированности:

Рис. 2.8. 

 

Простые преобразования этих двух структур восстанавливают сбалансированность. В случае 1 достаточно выполнить  однократный R - поворот узла x  вправо:

Рис. 2.9.

 

В случае 2 выполняется двойной LR - поворот, эквивалентный выполнению двух последовательных поворотов узлов y и x.

Рис. 2.10 

 

Повороты узла, разбалансированного  вправо, выполняются по симметричной схеме и носят названия однократного L-поворота и двойного RL-поворота.

В общих чертах процесс включения узла в сбалансированное дерево состоит из трех этапов:

1.      Поиск места включения узла в каком-либо листе.

2.      Включение нового узла и определение нового показателя сбалансированности в месте включения.

3.      Обратный проход по пути включения и проверка сбалансированности у каждого узла на этом пути.  

Алгоритм вставки  элемента в AVL-дерево

AVL_Insert( t, k, data, h, inserted )

1.      t – корень дерева / поддерева

2.       k –ключ нового элемента

3.       data – данные нового элемента

4.      inserted – возвращаемый признак вставки

5.      h – возвращаемый признак увеличения высоты

6.     if1 t = nil

7.         then1 t ← Create_Node(k, data)

8.                  bal [ t ] ← 0

9.                  h ← TRUE

10.                 inserted ← TRUE

11.                 return t

12.   h ← FALSE

13.   if2 k = key [ t ]

14.     then2 inserted ← FALSE

15.              return t

16.  if3 k < key[ t ]

17.     then3 left [ t ] ← AVL_Insert(left [ t ] k, data, hh, ins)

18.              if4 hh = TRUE

19.                then4 выросла левая ветвь

20.                      if5 bal [ t ] = 1

21.                          then5 bal [ t ] ← 0

22.                          else5 if6 bal [ t ] = 0

23.                                    then6 bal [ t ]← -1

24.                                              h ← TRUE

25.                                             балансировка

26.                                    else6 if7 bal[left [ t ]] = -1

27.                                                then7 t ← R ( t )

28.                                                else7 t ← LR ( t )

29.     else3 right [ t ] ← AVL_Insert(right [ t ], k, data, hh, ins)

30.            if8 hh = TRUE

31.                then8  выросла правая ветвь

32.                      if9 bal [ t ] = -1

33.                          then9 bal [ t ] ← 0

34.                          else9 if10 bal [ t ] = 0

35.                                     then10 bal [ t ] ← 1

36.                                                h ← TRUE

37.                                                 балансировка

38.                                     else10 if11 bal[right [ t ]] = 1

39.                                                  then11 t ← L ( t )

40.                                                  else11 t ← RL ( t )

41.   inserted ← ins

42.   return t

 

Алгоритм R - поворота узла t:

R ( t )

1.     x← left [ t ]

2.     left [ t ] ← right[x]

3.     right[x] ← t

4.     if bal[x] = -1

5.         then bal [ t ] ← bal[x] ← 0

6.         else bal [ t ] ← -1

7.                 bal[x] ← 1

8.     return x 

 

Алгоритм LR - поворота узла t:

LR ( t )

1.     x ← left [ t ]

2.     y ← right [ x ]

3.     right [ x ] ← left [ y ]

4.     left [ y ] ← x

5.     left [ t ] ← right [ y ]

6.     right [ y ] ← t

7.     if  bal [ y ] = -1

8.          then  bal [ t ] ← 1

9.                    bal [ x ] ← 0

10. if  bal [ y ] = 0

11.      then  bal [ t ] ← bal [x ] ← 0

12. if  bal [ y ] = 1

13.      then  bal [ t ] ← 0

14.               bal [ x ] ← -1

15. bal [ y ] ← 0

16. return y

 

Математический анализ этого  алгоритма сложен. Эмпирические проверки этого алгоритма показывают, что  ожидаемая высота сбалансированного  дерева равна h=log2 n+0.25. То есть AVL - деревья ведут себя как идеально сбалансированные полные деревья.

Однако, затраты на балансировку AVL - дерева значительны. Балансировка необходима приблизительно 1 раз на два включения и однократный  и двукратный повороты равновероятны.

Из-за сложности операций балансировки AVL – деревья рекомендуется  использовать в случае, если число  операций поиска значительно превышает  число операций включения и удаления.

    1. Удаление элемента из AVL - дерева

При удалении узлов из AVL – дерева операция балансировки в основном остается такой же, что и при включении и заключается в однократном или двукратном повороте. При этом булевская переменная h, возвращаемая операцией удаления означает уменьшение высоты поддерева. При  восходящем пересчете критерия сбалансированности выполняется балансировка тех узлов, у которых критерий стал равным +2 или -2. Балансировка выполняется с помощью тех же  L - , R - , RL -  и LR - поворотов. 

 

Рис. 2.11. 

 

Удаление элементов также  имеет стоимость О(log2 n). Но если включение может вызвать один поворот, удаление может потребовать повороты в каждом узле пути поиска при обратном ходе рекурсии. Но эмпирические проверки показали, что если при включении выполняется один поворот на каждые два включения, то при удалении один поворот приходится на 5 удалений.

Рекурсивный алгоритм удаления элемента из AVL-дерева

AVL_Delete (t, k, h, deleted)

1.   t – корень дерева / поддерева

2.    k –ключ удаляемого элемента

3.   h – возвращаемый признак уменьшения высоты

4.   deleted – возвращаемый признак удаления

5.  h←FALSE

6.  if t = nil

7.   then deleted ← FALSE

8.            return nil

9.  if k < key [ t ]

10.   then left [ t ] ← AVL_Delete( left [ t ], k, hh, del )

11.            if hh = TRUE

12.                 then if bal [ t ] = -1

13.                             then bal [ t ] ← 0;

14.                                      h ← TRUE

15.                             else if bal [ t ] = 0

16.                                       then bal [ t ] ← 1

17.                                       else  if bal[right [ t ]] = 0

18.                                                    then t ← L( t )

19.                                                    else   h ← TRUE

20.                                                             if bal[right [ t ]] = 1

21.                                                                then t ← L( t )

22.                                                                else t ← RL( t )

23.            deleted ← del

24.            return t

Реализовать программу для работы с типом данных ”Дерево”