Изменения
Нет описания правки
=== Поиск следующего и предыдущего элемента ===
====Реализация с использованием информации о родителе====
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
'''Node''' next('''Node''' x)
y = y.parent
'''return''' y
Обе операции выполняются за время <tex>O(h)</tex>.
====Реализация без использования информации о родителе====
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то начнем поиск от корня. Спускаемся вниз по дереву. Если значение узла больше значения в рассматриваемом в данный момент узле, перейдем в правое поддерево, иначе перейдем в левое поддерево. Аналогично выполняется поиск предыдущего элемента. Рекурсивные реализации обеих функций:
'''Node''' next('''Node''' x, '''Node''' t) <font color="green">// x - элемент, для которого ищем следующий, t - текущее поддерево</font>
'''if''' t != null
'''Node''' successor = next(x, t.left)
'''if''' successor == null
'''if''' t.key > x.key
'''return''' t
'''else'''
'''return''' successor
'''return''' next(x, t.right)
'''return''' null
'''Node''' prev('''Node''' x, '''Node''' t) <font color="green">// x - элемент, для которого ищем предыдущий, t - текущее поддерево</font>
'''if''' t != null
'''Node''' ancestor = prev(x, t.right)
'''if''' ancestor == null
'''if''' t.key <= x.key
'''return''' t
'''else'''
'''return''' ancestor
'''return''' prev(x, t.left)
'''return''' null
Обе операции выполняются за время <tex>O(h)</tex>.
=== Вставка ===
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
insert('''Node''' x, '''Node''' z) <font color="green">// x - корень поддерева, z - вставляемый элемент</font>
'''if''' z.key > x.key
'''if''' x.right != null
z.parent = x;
x.left = z;
Время работы алгоритма {{---}} <tex>O(h)</tex>.
=== Удаление ===
====Нерекурсивная реализация====Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на <tex>null</tex>. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент(у этого элемента не будет левого потомка) и переместить его на место удаляемого узла. Время работы алгоритма {{---}} <tex>O(h)</tex>.
{| border="1" cellpadding="5" cellspacing="0"
!Случай
'''else'''
y.parent.right = x
====Рекурсивная реализация====
При рекурсивном удаления узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:
'''Node''' delete('''Node''' root, '''Node''' z) <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
root.key = minimum(root.right).key
root.right = remove(root, root.right)
'''else'''
'''if''' root.left != null
root = t.left
'''else'''
root = t.right
'''return''' root
==См. также==
