Как было отмечено выше, эффективность поиска с помощью ДП сильно зависит от структуры дерева: чем ближе дерево к идеально сбалансированному, тем меньше высота дерева и тем выше эффективность поиска. К сожалению, входные данные при построении дерева могут быть таковыми, что дерево начинает деформироваться влево или вправо - становится разбалансированным. В крайнем случае, дерево превращается в обычный линейный список, т.е. становится вырожденным. Отсюда следует, что процесс построения дерева должен контролироваться соответствующими алгоритмами, которые при выполнении процедур добавления или удаления могли бы выполнять перестройку дерева с целью сохранения его структуры максимально близкой к идеально сбалансированной.
Например, один и тот же входной набор числовых ключей, но поступающий в разном порядке, может приводить к существенно разным ДП.
    
|   
| ||||||||||||||||||||||||||||
| “Хорошая” входная последовательность: 20 – 10 – 30 – 15 – 25 – 5 - 40 | “Плохая” входная последовательность: 10 – 15 – 20 – 5 – 25 – 30 - 40 |
Данная проблема исследуется уже около 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)
Удаление вершин из АВЛ-дерева выполняется аналогично:
· ищется удаляемая вершина
· если требуется – определяется вершина-заменитель и выполняется обмен
· после удаления вершины пересчитываются КБ и при необходимости производится балансировка точно по таким же правилам
В отличие от добавления, при удалении возможны ситуации, когда балансировка потребуется для всех вершин на пути от удаленной вершины до корня дерева.
Практика использования АВЛ-деревьев показала, что балансировка требуется примерно в половине случаев вставки и удаления вершин.
Общий вывод: учитывая достаточно высокую трудоемкость выполнения балансировки, АВЛ-деревья следует использовать тогда, когда вставка и удаление выполняются значительно реже, чем поиск.