Дополнительные вопросы обработки деревьев. 
Графы

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

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

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

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

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

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

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

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

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

Type Tp = ^TNode;

TNode = record

Inf: ;

Left, right: Tp;

Balance: shortInt;

end;

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

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

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

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

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

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

• · вершина 15 заменяет вершину 30
• · левое поддерево вершины 15 не изменяется (15−10−5)
• · правое поддерево вершины 15 образуется корневой вершиной 30
• · у вершины 30 правое поддерево не изменяется (30−40)
• · левое поддерево вершины 30 образуется бывшим правым потомком вершины 15, т. е. 20.

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

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

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

• · вершина 30 заменяется вершиной 20, т. е. правым потомком левого потомка
• · левый потомок вершины 20 (вершина 17) становится правым потомком вершины 15
• · левое поддерево с корнем 15 без изменений остается левым поддеревом вершины 20
• · правое поддерево вершины 20 начинается с вершины 30
• · правое поддерево вершины 30 не меняется (30−40−50)
• · левое поддерево вершины 30 образуется правым поддеревом вершины 20 (25−23)

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

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

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

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

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