Двоичные деревья, операции.
Двоичное дерево – конечное множество элементов (узлов), которое либо пусто, либо состоит из корня с двумя отдельными двоичными поддеревьями, которые называют левым и правым поддеревом корня.
Для построения двоичного дерева с n вершинами, имеющего минимальную высоту, используются следующие правила:
Если n=0, то конец;
Построить вершину
Построить левое поддерево с
вершинами;Построить правое поддерево с
вершинами.
Операции с двоичными деревьями:
Обход дерева
Учитывая рекурсивный характер правил обхода, программная их реализация наиболее просто может быть выполнена с помощью рекурсивных подпрограмм. Каждый рекурсивный вызов отвечает за обработку своего текущего поддерева. После полной обработки текущего поддерева происходит возврат к поддереву более высокого уровня, а для этого надо запоминать и в дальнейшем восстанавливать адрес корневой вершины этого поддерева. Рекурсивные вызовы позволяют выполнить это запоминание и восстановление автоматически, если описать адрес корневой вершины поддерева как формальный параметр рекурсивной подпрограммы.
К
+
B
A
аждый рекурсивный вызов прежде всего должен проверить переданный ей адрес на NULL. Если этот адрес равен NULL, то очередное обрабатываемое поддерево является пустым и никакая его обработка не нужна, поэтому просто происходит возврат из рекурсивного вызова. В противном случае в соответствии с реализуемым правилом обхода производится либо обработка вершины, либо рекурсивный вызов для обработки левого или правого поддерева.Префиксный обход – вершина, левое, правое (+ab):
p refix_walk (struct binary_tree *t)
{
if (t!=0)
{
print(t->data); //вершина
prefix_walk(t->left); // левое
prefix_walt(t->right); // правое
}
}
Инфиксный обход – левое, вершина, правое (a+b);
Постфиксный – левое, правое, вершина (ab+);
Поиск:
При использовании в целях поиска элементов данных по значению уникального ключа применяются двоичные деревья поиска дерево поиска – все вершины в правом поддереве > x (вершина), все вершины в левом поддереве < x.
N элементов можно организовать в бинарное дерево с высотой не более log2(N) , поэтому для поиска среди N элементов может потребоваться не больше log2(N) сравнений, если дерево идеально сбалансировано. Отсюда следует, что дерево – это более подходящая структура для организации поиска, чем, например, линейный список.
Ищем 29:
20
Направляемся в корень, затем в L (<20)
11
30
или R (>20) и т. д.
7
13
29
35
3
15
33
Операция включения вершины в дерево:
Операция включения элемента в дерево разбивается на три этапа: включение узла в пустое дерево, поиск корня для добавления нового узла, включение узла в левое или правое поддерево.
Добавляем 50:
20
11
3
7
30
15
13
29
35
Ищем позицию аналогичнооперации поиска, пока не
дойдем до NULL.
33
50
Удаление вершины:
Для удаления узла с указанным ключом сначала происходит его поиск. В случае, если узел найден, то он удаляется.
Если удаляемый узел не имеет потомков, то просто удаляется ссылка на него.
Если удаляемый узел имеет одного потомка, в этом случае переадресуется ссылка на этого потомка.
Если удаляемый узел имеет двух потомков, то на его место ставится самый правый потомок из левого поддерева или самый левый потомок из правого поддерева.
Удаляем 15 – ставим 14 или 16
15
13
12
19
14
17
20
16
18
21