Реализация рекурсивного алгоритма вставки в АВЛ-дерево

Дополним уже имеющуюся структуру узла бинарного дерева поиска еще одним полем (назовем его balance), которое будет служить для хранения баланса узла. Вообще-то для хранения баланса узла достаточно всего двух бит, но в реализации на С++ определим для него тип short.

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

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

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

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

Для реализации этого алгоритма добавим еще один параметр в функцию вставки — изменение высоты поддерева (в листинге это параметр d). При добавлении узла этот параметр будет принимать значение 1 (узел всегда добавляется в пустое поддерево), а при вращениях, наоборот, высота поддерева уменьшается на 1 (т.е. d=-1).

Реализация рекурсивного алгоритма вставки в АВЛ-дерево приводится в листинге 5.4. Кроме функции вставки и всех необходимых вспомогательных функций, приводится функция построения АВЛ-дерева из заданной последовательности и функция нисходящего обхода, которая строит левое скобочное представление полученного дерева (этого вполне достаточно, чтобы убедиться в том, что построенное дерево является сбалансированным).

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

#include <iostream.h>

#include <stdlib.h>

typedef int T_key; //тип ключа, может быть любым

typedef char T_data;//тип связанных данных, любой

struct item //структура элемента

{ T_key key; //ключ

T_data data; //связанные данные

};

struct node // структура узла дерева

{item data; //данные типа item

 node *left, *right; // указатели на детей

 short balance; // показатель сбалансированности

 node(item x) // конструктор, вызывается при создании узла

 {data=x;left=right=NULL;balance=0;}

};

typedef node* avlbst; //avlbst - avl binary seach tree

//Малое правое вращение:

void SmallRightRotate(avlbst root)

{ avlbst x,y; item t;

x=root; y=x->right;

t=x->data; x->data=y->data; y->data=t;

x->right=y->right;

y->right=y->left; y->left=x->left;

x->left=y;

x->balance= y->balance=0; //изменяем balance для x и y

 }

 //Большое правое вращение:

void LargeRightRotate(avlbst root)

{ avlbst x,y,z; item t;

x=root; y=x->right; z=y->left;

t=x->data;x->data=z->data; z->data=t;

y->left=z->right;

z->right=z->left; z->left=x->left;

x->left=z;

x->balance=0;

if (z->balance==0) y->balance=z->balance=0;

else

if (z->balance==-1) { y->balance=0; z->balance=1;}

else {z->balance=0; y->balance=-1;}

}

//Малое левое вращение (аналогично малому правому):

void SmallLeftRotate(avlbst root)

{ avlbst x,y; item t;

x=root; y=x->left;

t=x->data; x->data=y->data; y->data=t;

x->left=y->left;

y->left=y->right; y->right=x->right;

x->right=y;

x->balance=y->balance=0;

 }

 //Большое левое вращение (аналогично большому правому):

void LargeLeftRotate(avlbst root)

{ avlbst x,y,z; item t;

x=root; y=x->left; z=y->right;

t=x->data;x->data=z->data; z->data=t;

y->right=z->left;

z->left=z->right; z->right=x->right;

x->right=z;

x->balance=0;

 if (z->balance==0)

y->balance=z->balance=0;

 else

 if (z->balance==-1)

 { y->balance=0; z->balance=1;}

 else

 { z->balance=0; y->balance=-1;}

}

// функция определяет, какое именно вращение нужно

void rotate(avlbst root)

{ if (root->balance==2) //Правое вращение

if (root->right->balance<0) LargeRightRotate(root);

else                SmallRightRotate(root);

else //Левое вращение

    if (root->left->balance>0) LargeLeftRotate(root);

    else                SmallLeftRotate(root);

}

bool insertavl_rec(avlbst &root, item x, int &d)

{ //параметр d - изменение высоты текущего поддерева

if (!root) // дерево пусто – терминальная ветвь

{ root=new node(x); d=1;//создали узел-высота увеличилась на 1

if(root)return true; else return false;

}

// рекурсивная ветвь

if (x.key<root->data.key) // нужно двигаться влево

{ insertavl_rec(root->left,x,d); // вставка в левое поддерево

root->balance=root->balance-d; //корректируем balance у отца

if (abs(root->balance)==2) //если отец (root) разбалансирован

{ rotate(root); d--;}// вызываем нужное вращение

}                // оно уменьшило высоту дерева   

else // нужно двигаться вправо

{ insertavl_rec(root->right,x,d); // вставка в правое поддерево

root->balance=root->balance+d; //пришли справа, d прибавляется

if (abs(root->balance)==2) // при разбалансировке

{ rotate(root); d--;} // выполняем вращение

}  

}

// функция-тест строит дерево из примера (рис.5.13)

void randtree(avlbst &root)

{ item x; int a[7]={4,5,7,2,1,3,6}; int d=0;

for (int i=0;i<7; i++)

{ x.key=a[i];

x.data=rand()%26+65; // случайные заглавные латинские буквы

insertavl_rec(root,x,d);

}

}

// вывод дерева в КЛП порядке (для проверки сбалансированности)

void out(avlbst root)

{if (!root) return;

 cout<<root->data.key<<' '<<root->data.data<<"; ";

 cout<<'('; out(root->left); cout<<")(";

 out(root->right);cout<<')';

}

Сильноветвящиеся деревья

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

Допустим, узел дерева имеет два ключа — 10 и 20. Такой узел может иметь максимум три сына — первый (крайний левый) должен иметь ключи, меньшие 10, второй — от 10 до 20 (10 входит в этот диапазон), третий (крайний правый) — более или равно 20.

На практике используются различные виды сильноветвящихся деревьев. В качестве структур для поиска в оперативной памяти применяются 2-3 деревья (их узлы имеют двух или трех сыновей) и 2-3-4 деревья (узлы могут иметь еще и четырех сыновей). Для поиска во внешней памяти наиболее подходят B-деревья, которые могут ветвиться еще сильней (B — balansed). B-деревья в настоящее время являются основными структурами для поиска в базах данных.

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

В качестве примера рассмотрим структуру 2-3 дерева, в котором вся информация размещается в листьях [3]. Будем считать этот материал введением в сильноветвящиеся деревья поиска.

Деревья

Пример 2-3 дерева изображен на рис. 5.14. Поскольку внутренние узлы могут содержать два ключа, на рисунке они изображены в виде прямоугольников, а листья, содержащие только один ключ, изображены, как обычно, в виде окружностей. Свойства 2-3 деревьев можно определить так.

1. Каждый лист содержит ключ и связанные с ним данные (на рисунке показаны только ключи). В графическом представлении 2-3 дерева ключи в листьях упорядочены слева направо.

2. Каждый внутренний узел содержит один или два ключа. Узел, содержащий один ключ, имеет двух сыновей, узел, содержащий два ключа, имеет трех сыновей. 

3. Первым ключом внутреннего узла является ключ наименьшего из потомков второго сына (второй сын всегда есть, а его наименьший потомок может использоваться в качестве разделителя между первым и вторым поддеревом). Вторым ключом может являться ключ наименьшего потомка третьего сына, если третий сын есть. Тогда его наименьший потомок задает границу между вторым и третьим поддеревом.

4. Все листья располагаются на одном уровне. Исходя из этого условия, решается вопрос, сколько сыновей должен иметь каждый из внутренних узлов — два или три.

Добавим, что пустое дерево и дерево с одним корнем также являются 2-3 деревьями.

Рис.5.14. Пример 2-3 дерева

2-3-дерево с k уровнями может иметь от 2^k-1 до 3^k-1 листьев. Если в дереве n элементов, то дерево будет иметь от 1+log₃n до 1+log₂n уровней. Таким образом, длины всех путей имеют порядок O(log₂n).

Рассмотрим выполнение основных операций над 2-3 деревьями.

Поиск элемента в 2-3- дереве

Поиск выполняется аналогично поиску в бинарном дереве с той разницей, что для тех узлов, которые имеют два ключа, разветвление возможно по трем направлениям — к первому (левому), второму или третьему сыну, в зависимости от значения ключа. Например, для того, чтобы найти элемент с ключом 16 на рис.5.14, переходим от корня к его третьему сыну, а из этого узла переходим к первому сыну (он уже является листом и его ключ равен 16, поэтому поиск закончен успешно). При попытке найти ключ 18, будем двигаться по тому же самому пути, но, дойдя до листа, не обнаружим там значение 18, и поиск закончится промахом.