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

Однако идеальную сбалансированность довольно трудно поддерживать. В некоторых  случаях при добавлении или удалении элементов может потребоваться  значительная перестройка дерева, не гарантирующая логарифмической  сложности. В 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).

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

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

Рис. 2.7.

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

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

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

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

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

Рис. 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.     if₁ t = nil

7.         then₁ t ← Create_Node(k, data)

8.                  bal [ t ] ← 0

9.                  h ← TRUE

10.                 inserted ← TRUE

11.                 return t

12.   h ← FALSE

13.   if₂ k = key [ t ]

14.     then₂ inserted ← FALSE

15.              return t

16.  if₃ k < key[ t ]

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

18.              if₄ hh = TRUE

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

20.                      if₅ bal [ t ] = 1

21.                          then₅ bal [ t ] ← 0

22.                          else₅ if₆ bal [ t ] = 0

23.                                    then₆ bal [ t ]← -1

24.                                              h ← TRUE

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

26.                                    else₆ if₇ bal[left [ t ]] = -1

27.                                                then₇ t ← R ( t )

28.                                                else₇ t ← LR ( t )

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

30.            if₈ hh = TRUE

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

32.                      if₉ bal [ t ] = -1

33.                          then₉ bal [ t ] ← 0

34.                          else₉ if₁₀ bal [ t ] = 0

35.                                     then₁₀ bal [ t ] ← 1

36.                                                h ← TRUE

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

38.                                     else₁₀ if₁₁ bal[right [ t ]] = 1

39.                                                  then₁₁ t ← L ( t )

40.                                                  else₁₁ 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=log₂ n+0.25. То есть AVL - деревья ведут себя как идеально сбалансированные полные деревья.

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

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

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

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

 

Рис. 2.11. 

 

Удаление элементов также  имеет стоимость О(log₂ 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