Балансировка деревьев поиска
Трудоемкость нахождения заданного элемента в дереве поиска зависит от структуры этого дерева. Например, если ни у одной вершины нет левого сына, то дерево вырождается в линейный список, и поиск сводится к последовательному перебору вершин. В связи с этим появляется необходимость в поддержке определенной сбалансированности дерева поиска.
По определению Вирта, дерево поиска является идеально сбалансированным, если для каждой его вершины количество вершин в левом и правом поддеревьях отличается не более, чем на 1.
В процессе корректировки идеальная балансировка дерева часто нарушается. Имеется более мягкое определение: дерево сбалансированно, если высота (глубина, количество уровней) левого и правого поддеревьев любой вершины отличается не более, чем на 1. Сбалансированные деревья поиска называют АВЛ-деревьями по именам авторов Адельсон-Вельского и Ландиса. В АВЛ-деревьях необходимость в операциях балансировки появляется реже, а сами эти операции достаточно просты.
Восстановление баланса в АВЛ-деревьях достигается путем преобразований, называемых поворотами. Имеются четыре типа поворотов: LL-поворот, RR-поворот, LR-поворот и RL-поворот. Первые два из них считаются одинарными, а последние два – двойными. Это связано с количеством операций, необходимых для восстановления баланса.
Мнемонические обозначения типов поворота связаны с ситуациями нарушения баланса, возникающими в некоторой вершине в результате включения новой вершины. Если оказывается, что в этой вершине высота левого поддерева больше на 2 уровня высоты правого поддерева, то первой буквой в мнемоническом обозначении поворота будет L. Если для левого сына этой вершины высота левого поддерева остается большей, то потребуется LL-поворот. Аналогично определяются обозначения других типов поворотов.
Рассмотрим следующие примеры. Пусть имеется АВЛ-дерево
и включается элемент с ключом 4 или 7. В результате LL-поворота получится дерево
или
Если же в исходное дерево включается элемент с ключом 12 или 17, то LR-поворот приведет к дереву
или
Пусть дерево описано в виде динамической структуры с указателями Left и Right на левого и правого сыновей для каждой вершины, а указатель P показывает на вершину, в которой возникло нарушение баланса. Тогда LL-поворот выражается тремя операторами
P1:=P^.Left;
P^.Left:=P1^.Right;
P1^.Right:=P;
а LR-поворот шестью операторами
P1:=P^.Left; P2:=P1^.Right;
P1^.Right:= P2^.Left; P2^.Left:=P1;
P^.Left:=P2^.Right; P2^.Right:=P;
Рассмотрим примеры более сложных деревьев. Пусть имеется дерево
При включении элемента с ключом 1 или 3 потребуется LL-поворот в вершине с ключом 20, который в соответствии с указанными операторами приведет к дереву
или
При включении же элемента с ключом 11 или 14 потребуется LR-поворот, приводящий к дереву
или
Исключение из АВЛ-дерева несколько сложнее. Сначала исключение выполняется, как из обычного дерева поиска. Затем анализируется, есть ли нарушения баланса по направлению к корню дерева. Отличие от включения состоит в том, что балансировка может потребоваться более одного раза.
Рассмотрим в качестве примера следующее дерево.
Это дерево Фибоначчи: АВЛ-дерево заданной высоты с минимальным числом вершин. При удалении вершины с ключом 35 возникает нарушение баланса в вершине с ключом 30. LL-поворот приводит к новому нарушению баланса в корне дерева. В результате еще одного LL-поворота получается дерево
При удалении из АВЛ-дерева встречаются ситуации, когда восстановление баланса можно достигнуть как одинарным, так и двойным поворотом. Например, при удалении элемента с ключом 25 из дерева
баланс в корне дерева можно восстановить как LL-поворотом, так и LR-поворотом.
Дата добавления: 2015-08-21; просмотров: 1302;