Бинарное дерево поиска

Наиболее часто для работы со списками используются бинарные (имеющие степень 2) деревья (рис. 5.1).

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

Сбалансированными, или AVL -деревьями, называются деревья, для каждого узла которых высóты его поддеревьев различаются не более чем на 1.

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

При работе с бинарным деревом простейшего вида, т.е. ключами которого являются целые числа (уникальные, т.е. не повторяются), необходимо использовать структуру следующего вида:

struct Tree {

int info;

Tree *left, *right;

} *root; // root - указатель корня

В общем случае при работе с деревьями необходимо уметь:

– сформировать дерево (добавить новый элемент);

– обойти все элементы дерева (например, для просмотра или выполнения некоторой операции);

– выполнить поиск элемента с указанным значением в узле;

– удалить заданный элемент.

Формирование дерева поиска состоит из двух этапов: создание корня, являющегося листом, и добавление нового элемента (листа) в найденное место. Для этого используется функция формирования листа:

Tree* List(int inf) {

Tree *t = new Tree; // Захват памяти

t -> info = inf; // Формирование информационной части

t -> left = t -> right = NULL; // Формирование адресных частей

return t; // Возврат созданного указателя

}

1. Первоначально (root = NULL) создаем корень (первый лист дерева):

root = List (StrToInt(Edit1->Text));

2. Иначе (root!= NULL) добавляем информацию (key) в нужное место:

void Add_List(Tree *root, int key) {

Tree *prev, *t; // prev – указатель предка нового листа

bool find = true;

t = root;

while (t && find) {

prev = t;

if(key == t->info) {

find = false; // Ключ должен быть уникален

ShowMessage("Dublucate Key!");

}

else

if (key < t -> info) t = t -> left;

else t = t -> right;

}

if (find) { // Нашли нужное место

t = List(key); // Создаем новый лист

if (key < prev -> info) prev -> left = t;

else prev -> right = t;

}

}