Двоичные деревья поиска Двоичное дерево поиска – это, как следует из названия – двоичное дерево. Это дерево может быть представлено как связанная структура данных, каждый узел этой структуры – объект, содержащий ключ (key), и указатели left, right, p (левый ребенок, правый ребенок и родитель), если ребенка или родителя нет, то записывается NIL. Ключи хранятся с соблюдением свойства упорядоченности. Если вершина y находится в левом поддереве вершины x, key[y]>=key[x], если в правом, то key[y]>=key[x].

Двоичные деревья поиска

Печать всех ключей, входящих в дерево T c корнем root[T] INORDER-TREE-WALK(x) 1 if x != NIL 2 then INORDER-TREE-WALK (left[x]) 3 print key[x] 4 INORDER-TREE-WALK (right[x])

Поиск в двоичном дереве TREE-SEARCH (x, k) 1 if x = NIL or k = key[x] 2 then return x 3 if k < key[x] 4 then return TREE- SEARCH (left[x], k) 5 else return TREE- SEARCH (right[x], k) ITERATIVE-TREE- SEARCH (x,k) 1 while x != NIL and k!= key[x] 2 do if k < key[x] 3 then x = left[x] 4 else x = right[x] 5 return x

Минимум и максимум TREE-MINIMUM (x) 1 while left[x] != NIL 2 do x = left[x] 3 return x TREE-MAXIMUM(x) 1 while right[x] !=NIL 2 do x = right[x] 3 return x

Следующий элемент TREE SUCCESSOR(x) 1 if right[x] != NIL 2 then return TREE-MINIMUM(right[x]) 3 y = p[x] 4 while y != NIL and x = right[y] 5 do x = y 6 y = p[y] 7 return y

Добавление элемента TREE-INSERT(T,z) 1 y NIL 2 x root[T] 3 while x NIL 4 do y x 5 if key[z] < key[x] 6 then x left[x] 7 else x right[x] 8 p[z] y 9 if y = NIL 10 then root[T] z 11 else if key[z] < key[y] 12 then left[y] z 13 else right[y] z

Добавление элемента с ключом 13

Удаление элемента TREE-DELETE(T, z) 1 if left[z] = NIL or right[z] = NIL 2 then y z 3 else y TREE- SUCCESSOR(z) 4 if left[y] NIL 5 then x left[y] 6 else x right[y] 7 if x NIL 8 then p[x] p[y] 9 if p[y] = NIL 10 then root[T] x 11 else if y = left[p[y]] 12 then left[p[y]] x 13 else right[p[y]] x 14 if y z 15 then key[z] key[y] 16 If y has other fields, copy them, too. 17 return y

Удаление вершины z из двоичного дерева