Изменения

Перейти к: навигация, поиск

Дерево поиска, наивная реализация

593 байта убрано, 19:17, 31 мая 2015
Нет описания правки
Обе операции выполняются за время <tex>O(h)</tex>.
====Реализация без использования информации о родителе====
Если у узла есть правое поддеревоРассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддеревахраня текущий узел <tex>current</tex> и узел <tex>parent</tex> - последний посещенный узел, то начнем поиск от корняключ которого больше <tex>x</tex>. Спускаемся вниз по дереву. Если значение , как в алгоритме поиска узла больше значения , обновляя <tex>parent</tex> при переходе к левому потомку (если мы перешли к правому потомку, значит, что ключ в рассматриваемом в данный момент предыдущем узлеменьше <tex>x</tex>). Таким образом, перейдем в правое поддеревомы обойдем всё дерево и найдем элемент с минимальным ключем, иначе перейдем в левое поддеревобольшем <tex>x</tex>. Аналогично выполняется поиск реализуется операция поиска предыдущего элемента. Реализации обеих функций: '''Node''' next(root : '''Node''', x : '''NodeT'''): <font color="green">// x {{---}} элемент, для которого ищем следующий, root {{---}} корень дерева</font> '''if''' x.right != null '''return''' minimum(x.right) '''Node''' successor current = ''null'' '''while''' root !, parent = ''null'' '''if''' x.value < root.value successor = root root = root.left '''else if''' x.value > root.value root = root.right '''else''' break '''return''' successor  '''Node''' prev(root : '''Node''', x : '''Node'''): <font color="green">// x {{---}} элемент, для которого ищем следующий, root {{---}} корень дерева</font> '''if''' x.left != null '''return''' maximum(x.left) '''Node''' ancestor = ''null'' '''while''' root current != ''null'' '''if''' xcurrent.value key > root.valuex ancestor parent = rootcurrent root current = rootcurrent.rightleft '''else if''' x.value < root.value root current = rootcurrent.left '''else''' breakright '''return''' ancestorparentОбе операции выполняются за время <tex>O(h)</tex>.
=== Вставка ===
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
====Реализация с использованием информации о родителе====
'''func''' insert(x : '''Node''', z : '''NodeT'''): <font color="green">// x {{---}} корень поддерева, z {{---}} вставляемый элементключ</font> '''if''' z.key > x.key
'''if''' x.right != ''null''
insert(x.right, z)
'''else'''
z'''Node''' y y.parent = x y.key = z x.right = zy '''elseif'''z < x.key
'''if''' x.left != ''null''
insert(x.left, z)
'''else'''
z'''Node''' y y.parent = x y.key = z x.left = zy
====Реализация без использования информации о родителе====
'''func''' insert(x : '''Node''', z : '''NodeT'''): <font color="green">// x {{---}} корень поддерева, z {{---}} вставляемый элементключ</font> '''if''' z.key <= x.key '''if''' x.left == ''null'' x.left = Node(z) <font color="green">// подвесим Node с key = z</font> '''elseif'''z < x.key
insert(x.left, z)
'''else''' '''if''' z > x.right == ''null'' x.right = z '''else'''key
insert(x.right, z)
'''if''' p.right == v
p.right = ''null''
'''else''' '''if''' v.left == ''null'' '''or''' v.right == ''null'' <font color="green">// второй случай: удаляемый элемент имеет одного потомка</font> '''if''' v.left == ''null'' '''if''' p.left == v p.left = v.right '''else''' p.right = v.right v.right.parent = p
'''else'''
'''if''' p.left =right = v p.left = v.left '''else''' p.right = v.left v.leftright.parent = p '''else''' <font color="green">// третий случай: удаляемый элемент имеет двух потомков</font> successor = next(v, t) v.key = successor.key '''if''' successor.parentp.left == successorv successor.parentp.left = successorv.right '''if''' successor.right != ''null'' successor.right.parent = successor.parentleft
'''else'''
p.right = v.left v.left.parent = p '''else''' <font color="green">// третий случай: удаляемый элемент имеет двух потомков</font> successor = next(v, t) v.key = successor.key '''if''' successor.parent.left == successor successor.parent.left = successor.right '''if''' successor.right != ''null'' successor.right.parent = successor.parent '''else''' successor.parent.right = successor.right '''if''' successor.right != ''null'' successor.right.parent = successor.parent
====Рекурсивная реализация====
При рекурсивном удаления узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:
'''Node''' delete(root : '''Node''', z : '''NodeT'''): <font color="green">// корень поддерева, удаляемый элементключ</font>
'''if''' root == ''null''
'''return''' root
'''if''' z.key < root.key
root.left = remove(root.left, z)
'''else if''' z.key > root.key
root.right = remove(root.right, z)
'''else if''' root.left != ''null'' '''and''' root.right != ''null''
Kiryukhinv
188
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/47123»

Навигация