Проблемы использования деревьев поиска

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

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

“Хорошая” входная последовательность: 20 – 10 – 30 – 15 – 25 – 5 - 40	“Плохая” входная последовательность: 10 – 15 – 20 – 5 – 25 – 30 - 40

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

Одним из наиболее известных методов балансировки является метод, предложенный в 60-е годы советскими математиками Адельсон–Вельским и Ландисом. Они предложили вместо понятия идеально сбалансированных деревьев использовать понятие АВЛ-сбалансированных деревьев, которые хоть и уступают немного идеально сбалансированным по эффективности поиска, но зато имеют не очень сложную программную реализацию.

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

Очевидно, что любое идеально сбалансированное дерево является также и АВЛ-сбалансированным, но не наоборот.

Идеально сбалансированное и оно же АВЛ-сбалансированное	АВЛ-сбалансированное, но не идеально сбалансированное	Не АВЛ-сбалансированное (нарушение – для корня)

Для реализации алгоритмов АВЛ-балансировки в каждой вершине дерева удобно хранить так называемый коэффициент балансировки (КБ) как разность высот правого и левого поддеревьев. Для АВЛ-деревьев у всех вершин значение КБ равно –1, 0 или +1.

25 (0) 10 (0) 40 (0) 20 (0) 30 (-1)	27 (0) 22 (0) 25 (0) 10 (0) 20 (+1) 40 (0) 30 (-2)
АВЛ-сбалансированное дерево	несбалансированное дерево

Поскольку коэффициент балансировки используется для каждой вершин, удобно ввести его в структуру данных, описывающих эту вершину:

Type Tp = ^TNode;

TNode = record

Inf : <описание>;

Left, right : Tp;

Balance : shortInt;

end;

Алгоритм АВЛ-балансировки при добавлении вершины.

· выполняется поиск в дереве места для новой добавочной вершины, при этом для каждой вершины высчитывается коэффициент балансировки

· если необходимо, то выполняется добавление самой вершины с заполнением всех полей, в том числе и КБ =0 (т.к. потомков у вновь созданной вершины пока нет)

· изменяется на 1 коэффициент балансировки у родителя добавленной вершины: КБ = КБ + 1 если добавлен правый потомок, иначе КБ = КБ - 1

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

· если у какой либо вершины нарушается условие балансировки, запускается специальный алгоритм перестановки вершин, который восстанавливает АВЛ-балансировку дерева и в то же время сохраняет упорядоченную структуру дерева поиска

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

5 (0) 10 (-1) 20 (0) 15 (-1) 40 (0) 30 (-2)	5 (0) 40 (0) 20 (0) 30 (0) 10 (-1) 15 (0)
до балансировки	после балансировки

Данная ситуация является более простой и определяется следующими условиями:

· вершина с нарушенным условием балансировки деформирована влево, КБ(30) = -2

· ее левый потомок также перевешивает в левую сторону, КБ(15) = -1

Для исправления этой ситуации выполняется однократный поворот вправо:

· вершина 15 заменяет вершину 30

· левое поддерево вершины 15 не изменяется (15 – 10 – 5)

· правое поддерево вершины 15 образуется корневой вершиной 30

· у вершины 30 правое поддерево не изменяется (30 – 40)

· левое поддерево вершины 30 образуется бывшим правым потомком вершины 15, т.е. 20

Аналогично выполняется однократный поворот влево, если вершина с нарушенным условием балансировки перевешивает вправо (КБ = 2), а ее правый потомок тоже перевешивает вправо (КБ = 1).

Более сложные случаи возникают при несогласованном перевешивании корневой вершины и ее потомков (коэффициенты балансировки имеют разные знаки). Например, рассмотрим случай, когда корневая вершина поддерева с нарушенным условием перевешивает влево (КБ = -2), но ее левый потомок перевешивает вправо (КБ = 1).

23 (0) 5 (0) 17 (0) 50 (0) 10 (-1) 20 (+1) 25 (-1) 15 (+1) 40 (+1) 30 (-2)	50 (0) 23 (0) 5 (0) 40 (+1) 10 (-1) 25 (-1) 17 (0) 30 (0) 15 (-1) 20 (0)
до балансировки	после балансировки

Двукратный поворот включает в себя:

· вершина 30 заменяется вершиной 20, т.е. правым потомком левого потомка

· левый потомок вершины 20 (вершина 17) становится правым потомком вершины 15

· левое поддерево с корнем 15 без изменений остается левым поддеревом вершины 20

· правое поддерево вершины 20 начинается с вершины 30

· правое поддерево вершины 30 не меняется (30 – 40 – 50)

· левое поддерево вершины 30 образуется правым поддеревом вершины 20 (25 – 23)

Удаление вершин из АВЛ-дерева выполняется аналогично:

· ищется удаляемая вершина

· если требуется – определяется вершина-заменитель и выполняется обмен

· после удаления вершины пересчитываются КБ и при необходимости производится балансировка точно по таким же правилам

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

Практика использования АВЛ-деревьев показала, что балансировка требуется примерно в половине случаев вставки и удаления вершин.

Общий вывод: учитывая достаточно высокую трудоемкость выполнения балансировки, АВЛ-деревья следует использовать тогда, когда вставка и удаление выполняются значительно реже, чем поиск.