7. Бинарные (двоичные) деревья поиска
 

Бинарные деревья чаще всего применяются для представления множеств данных, элементы которых ищутся по уникальному, только им присущему ключу. Если бинарное дерево организовано таким образом, что для каждого узла t_i, все ключи в левом поддереве меньше ключа t_i, а ключи в правом поддереве больше ключа t_i, то это дерево называется бинарным деревом поиска. В дереве поиска можно найти место каждого ключа, двигаясь начиная от корня и переходя на левое или правое поддерево каждого узла в зависимости от значения ключа. Таким образом, места элементов в дереве определяются как значениями ключей, так и последовательностью их поступления. Определяющим фактором является значение ключа, от последовательности поступления элементов зависит степень сбалансированности дерева. При случайном распределении клю¬чей в исходной последовательности получается почти сбалансированное дерево. Если же исходная последовательность упорядочена по возрастанию или убыванию ключей, то дерево вырождается в последовательный список. Высота такого дерева равна числу элементов дерева, уменьшенному на 1.

Создание дерева поиска заключается в следующем. Первый элемент образует корень дерева. Для последующих элементов осуществляется поиск места включения по ветвям дерева до тех пор, пока не будет найден подходящий узел с нулевым указателем, туда и подключается элемент. Для каждого узла запрашивается динамическая память, ее адрес заносится в указатель узла-предка, данные элемента помещаются в узел, и обнуляются левый и правый указатели нового узла. Дерево поиска, построенное из последовательности ключей
9,17,20,16,12,21,6,3,11,4,19,14,13,1,5,2,8,18,7,10,15, имеет вид, приведенный на рис.

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