25. Сбалансированное дерево поиска (AVL-дерево). Процедуры поиска, включения и исключения элементов для AVL-дерева. Временная сложность этих процедур

 

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

                На рис 3.1, а представлено идеально сбалансированное дерево, а на рис. 3.1, б - сбалансированное.

 

                Рис. 3.1.

                Очевидно, что идеально сбалансированное дерево будет одновременно и сбалансированным.

 

                Сбалансированное дерево поиска получило название AVL-дерева в честь его создателей Г.М.Адельсон-Вельского и Е.М.Ландиса.

                Средняя длина пути поиска в AVL-дереве практически совпадает с длиной в идеально сбалансированном дереве, тогда как поддерживать AVL-деревья намного легче.

                AVL-дерево можно определить и рекурсивно:

                1. Граничное условие: дерево с одной вершиной - это AVL-дерево высоты 0.

                2. Рекурсивное условие: AVL-дерево высотой h (h>0) получается путем присоединения к новому корню двух AVL-деревьев, причем высота одного из них должна быть равна h-1, тогда как другому позволяется иметь высоту на единицу меньше, т.е. h-2.

§ 3.1. Нахождение элемента по ключу в AVL-дереве ничем не отличается от аналогичной процедуры в обычном дереве поиска

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

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

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

                1. У ЛПД вершины V недопустимо выросла левая ветвь. Эту ситуацию иллюстрирует рис. 3.2, а, на котором “добавленная” в результате включения новой вершины высота изображена заштрихованным прямоугольником. В данном случае необходимо произвести  однократный LL-поворот, схема которого показана на рис. 3.2, б.

                а                                                                                            б

                Рис. 3.2. Однократный LL-поворот.

                2. У ЛПД вершины V недопустимо выросла правая ветвь. Эту ситуацию иллюстрирует рис. 3.3, а, на котором “добавленная” в результате включения новой вершины высота изображена заштрихованными прямоугольниками. Следует указать, что новая вершина добавлена или в дерево b, или в дерево g, а не в оба дерева одновременно: сразу после добавления одной из этих вершин потребуется балансировка. Оба эти случая иллюстрируются одним рисунком только потому, что для них обоих необходим  двукратный LR-поворот, схема которого показана на рис. 3.3, б.

                а                                                                                            б

 

                Рис. 3.3. Двукратный LR-поворот.

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

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

                Удобнее в каждой вершине AVL-дерева хранить ее показатель сбалансированности balance, под которым понимают разность между высотой ее левого и правого поддеревьев. Очевидно, что показатель сбалансированности каждой вершины AVL-дерева может принимать следующие значения: -1, 0, 1.

                Таким образом, процесс включения новой вершины в AVL-дерево состоит из трех последовательно выполняемых частей:

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

                II. Включение новой вершины с показателем сбалансированности, равным нулю.

                III. “Отступление” по пути поиска (возможно, до самого корня) и корректировка в каждой встретившейся вершине показателя сбалансированности. Если значение balance в вершине примет недопустимое значение (-2 или 2), то балансировка.

                Остановимся на п.III подробнее.

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

1.     p^.balance = +1 при hЛПД < h ППД

2.     p^.balance = 0 при hЛПД = h ППД

3.     p^.balance = -1 при hЛПД > h ППД .

                После добавления нового элемента в первом случае предыдущая несбалансированность в V уравновешивается: p^.balance = 0, во втором случае левое поддерево станет допустимо перевешивать: p^.balance = -1, а вот в третьем случае показатель сбалансированности примет недопустимое значение: p^.balance = -2, что сигнализирует о необходимости вызова процедуры балансировки.

                Вид балансировки определяется показателем сбалансированности левого потомка W вершины V. Пусть вершина W расположена по адресу pl. Тогда если pl^.balance = -1, то необходимо выполнить однократный LL-поворот (рис. 3.2), а если pl^.balance = +1, то двукратный LR-поворот (рис. 3.3). Заметим, что ситуация, когда pl^.balance = 0, невозможна по той же причине, по которой нельзя включить сразу два новых элемента - и в дерево b, в дерево g.

                Операция по балансировке состоит из последовательных переписываний ссылок и исправления показателей сбалансированности соответствующих вершин.

                Пример. Однократный LL-поворот производит следующая последовательность операторов:

                               ...

                p^.left:=pl^.right;               {* дерево b “цепляется” к вершине V слева *}

                pl^.right:=p;                         {* вершина V “цепляется” к вершине W справа *}

                p^.balance:=0;                    {* показатель сбал-ти вершины V равен нулю *}

                p:=pl;                                    {* предок вершины V ссылается теперь на вершину W *}

                p^.balance:=0;                    {* показатель сбал-ти вершины W равен нулю *}

                               ...

                Если недопустимо перевешивает правое поддерево вершины V, то выполняют либо однократный RR-поворот, либо двукратный RL-поворот в зависимости от показателя сбалансированности правого потомка вершины V. Процедура RR-поворота получается из процедуры LL-поворота путем перемены местами ссылок left и right, а также перемены местами показателей сбалансированности -1 и 1. Процедура RL-поворота получается из процедуры LR-поворота по тому же принципу.

                Экспериментальные данные подтверждают, что в среднем примерно на два включения приходится одна балансировка. Сложность операции балансировки предполагает, что AVL-деревья следует использовать только тогда, когда поиск информации осуществляется значительно чаще, чем ее включение.

 

§ 3.3. Исключение элемента из AVL-дерева

                Удаление концевых вершин и вершин с одним потомком осуществляется без труда (см. § 2.3). Если же от исключаемой вершины “отходят” два поддерева, то, как и в случае дерева поиска, она заменяется на самую правую вершину ее левого поддерева.

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

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

                Рис. 3.4.

 

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

 

§ 3.4. Оценка сложности при работе с AVL-деревом

                Экспериментальные проверки показывают, что высота AVL-дерева приблизительно составляет log (n), где n - количество вершин. Практически AVL-деревья ведут себя так же, как и идеально сбалансированные, хотя поддерживать их намного проще.

                Высота AVL-дерева и определяет максимальную сложность процедур поиска, включения и удаления элементов, которая составляет, таким образом, O (log (n)).