Изменения

* <tex>\mathrm{postorderTraversal}</tex> {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина

inorderTraversal('''Node''' x)

inorderTraversal(x.left)

'''print''' x.key

Корректность данного алгоритма следует из свойств бинарного дерева поиска.

preorderTraversal('''Node''' x)

'''print''' x.key

preorderTraversal(x.left)

preorderTraversal(x.right)

postorderTraversal(x.left)

postorderTraversal(x.right)

Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева.

=== Поиск элемента ===

Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.

'''Node''' search('''Node''' x, '''key''' k)

'''return''' x

'''if''' k < x.key

Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям <tex>left</tex> от корня дерева, пока не встретится значение <tex>null</tex>. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.

'''Node''' minimum('''Node''' x)

'''return''' x

'''return''' minimum(x.left)

'''Node''' maximum('''Node''' x)

'''return''' x

'''return''' maximum(x.right)

Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.

'''Node''' next('''Node''' x)

'''return''' minimum(x.right)

y = x.parent

x = y

y = y.parent

'''Node''' prev('''Node''' x)

'''return''' maximum(x.left)

y = x.parent

x = y

y = y.parent

Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то начнем поиск от корня. Спускаемся вниз по дереву. Если значение узла больше значения в рассматриваемом в данный момент узле, перейдем в правое поддерево, иначе перейдем в левое поддерево. Аналогично выполняется поиск предыдущего элемента. Рекурсивные реализации обеих функций:

'''Node''' next('''Node''' x, '''Node''' t) <font color="green">// x - элемент, для которого ищем следующий, t - текущее поддерево</font>

'''Node''' successor = next(x, t.left)

'''if''' t.key > x.key

'''return''' t

'''return''' successor

'''return''' next(x, t.right)

'''Node''' prev('''Node''' x, '''Node''' t) <font color="green">// x - элемент, для которого ищем предыдущий, t - текущее поддерево</font>

'''Node''' ancestor = prev(x, t.right)

'''if''' t.key <= x.key

'''return''' t

'''return''' ancestor

'''return''' prev(x, t.left)

Обе операции выполняются за время <tex>O(h)</tex>.

=== Вставка ===

insert('''Node''' x, '''Node''' z) <font color="green">// x - корень поддерева, z - вставляемый элемент</font>

'''if''' z.key > x.key

insert(x.right, z)

'''else'''

'''else'''

insert(x.left, z)

'''else'''

Время работы алгоритма {{---}} <tex>O(h)</tex>.

delete('''Node''' root, '''Node''' z) <font color="green">// корень поддерева, удаляемый элемент</font>

'''Node''' x, y <font color="green">// x - элемент, который нужно поместить вместо y</font>

y = '''next'''(z) <font color="green">// y - элемент, следующий за удаляемым, x - null</font>

'''if''' y == y.parent.left

'''else'''

z.key = y.key <font color="green">// подвешиваем y вместо z</font>

z.data = y.data

y = z <font color="green">// y - удаляемый элемент</font>

x = y.left

'''else'''

'''else''' <font color="green">// если z не имеет детей</font>

y = z <font color="green">// y - удаляемый элемент, x - null</font>

x.parent = y.parent

root = x

'''else'''

Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:

'''Node''' delete('''Node''' root, '''Node''' z) <font color="green">// корень поддерева, удаляемый элемент</font>

'''return''' root

'''if''' z.key < root.key

'''else if''' z.key > root.key

root.right = remove(root.right, z)

root.key = minimum(root.right).key

root.right = remove(root, root.right)

'''else'''

root = t.left

'''else'''

* [[Поисковые структуры данных]]

* [[Рандомизированное бинарное дерево поиска]]

==Источники информации==

[[Категория: Деревья поиска]]

[[Категория: Дискретная математика и алгоритмы]]