Реализация бинарного дерева поиска

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

Определим тип bst (binary seach tree — бинарное дерево поиска),

typedef node* bst;

который будет использоваться при определении первого параметра всех функций.

В листинге 5.3 содержится рекурсивный и нерекурсивный варианты реализации функций поиска и вставки и нерекурсивный вариант функции удаления (рекурсивный можно найти в [14]). Для полноты картины приведена функция ЛКП-обхода, которая выводит элементы дерева в порядке возрастания ключей, и функция, которая строит бинарное дерево поиска, заполненное случайными значениями, вызывая при этом функцию вставки.

Листинг 5.3. Реализация бинарного дерева поиска

#include <iostream.h>

#include <stdlib.h>

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

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

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

{ T_key key; //ключ

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

};

const item nullitem={-1};//пустой элемент возвращается при промахе поиска

struct node // узел дерева

{item data; // данные

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

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

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

};

typedef node* bst; //bst - binary seach tree

// ниже приводится реализация функций

// нерекурсивная функция поиска

item seach(bst root, T_key k)

{if (!root) return nullitem;

bst p=root;

while (p)

{ if (k==p->data.key) return p->data;

if (k<p->data.key) p=p->left;

else           p=p->right;

}

return nullitem;

}

// рекурсивный вариант функции поиска

item seach_rec(bst root, T_key k)

{ if(!root) return nullitem; // дерево пусто - промах

if (k==root->data.key) return root->data; // поиск успешен

if (k<root->data.key) return seach_rec(root->left, k);

else              return seach_rec(root->right, k);

}

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

bool insert(bst &root, item x)

{ if (!root) // дерево еще не заполнено

{ root=new node(x); if(root)return true; else return false;

}

bst p=root,parent; // parent родитель p

while (p) // находим место для вставки

{ parent=p;

if (x.key<p->data.key) p=p->left;

else               p=p->right;

}

p= new node(x); // формируем новый элемент

//вставляем его как левого или правого сына

if (x.key<parent->data.key) parent->left=p;

else                   parent->right=p;

if (p) return true; else return false;

}

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

bool insert_rec(bst &root, item x)

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

{ root=new node(x);if (root) return true; else return false;

}

if (x.key<root->data.key) return insert_rec(root->left,x);

else                 return insert_rec(root->right,x);

}

// функция удаления узла

bool remove(bst &root, T_key k)

{ if(!root) return false; // дерево пусто

bst p=root,parent=NULL;

// поиск удаляемого узла p и его родителя

while (p&&k!=p->data.key)

{ parent=p;

if (k<p->data.key) p=p->left;

else           p=p->right;

}

if (!p) return false; // обработали промах

// удаляем лист

if (!p->left&&!p->right)

if(p==root) root=NULL; //может, в дереве всего один узел

else if (parent->left==p) parent->left=NULL;

else                 parent->right=NULL;

// удаляем узел, у которого только один сын

if (p->left&&!p->right||!p->left&&p->right)

{ bst q; // запомним указатель на сына

if (p->left) q=p->left; else q=p->right;

   if(p==root) root=q; // у корня нет родителя

   else // подсоединяем сына к дедушке, удаляя родителя

   if (parent->left==p) parent->left=q;

        else            parent->right=q;

}

if (p->left&&p->right)// есть оба сына

{ //спускаемся в левое поддерево

   bst t=p->left,parent=p; //parent-родитель t

while (t->right) {parent=t;t=t->right;}

   //нашли крайнего правого сына t и его родителя parent

   p->data=t->data; //заменили данные у удаляемого узла

   // теперь удаляем крайнего правого сына t

   if (!t->left) //он лист

           parent->right=NULL;

   else      // у него есть левое поддерево

           parent->right=t->left;

   p=t; // теперь можно освобождать память для t

}

   delete p; return true; //освободили память

}

// формирование бинарного дерева поиска из n случайных элементов

void randtree(bst &root, int n)

{ item x;

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

{ x.key=rand()%1000; // случайные числа

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

insert(root,x); //или insert_rec(root,x);

}

}

// вывод дерева в порядке возрастания ключей

void out(bst root)

{if (!root) return;

 out(root->left);

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

 out(root->right);

}

Сбалансированные деревья

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

Однако есть несколько способов поддержки дерева в хорошем (хоть и не идеальном) состоянии за приемлемое время вставки и удаления. Деревья, которые постоянно поддерживаются в состоянии, близком к наилучшему, с приемлемыми временными характеристиками вставки и удаления, получили название сбалансированных. Мы рассмотрим несколько видов таких деревьев. Наиболее изученными деревьями, которые поддерживают хорошее сбалансированное состояние, являются АВЛ-деревья.

АВЛ-деревья