188
правок
Изменения
м
'''inorderTraversal'''(x.left) '''print'''(x.key) '''inorderTraversal'''(x.right)
'''postfixTraversal'''postorderTraversal(x.left) '''postfixTraversal'''postorderTraversal(x.right) '''print'''(x.key)
'''insert'''(x.right, z)
'''insert'''(x.left, z)
Нет описания правки
=== Обход дерева поиска ===
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
* <tex>\mathrm{inorderTraversal }</tex> {{---}} обход узлов в отсортированном порядке* prefixTraversal <tex>\mathrm{preorderTraversal}</tex> {{---}} обход узлов в порядке: вершина, левое поддерево, правое поддерево* postfixTraversal <tex>\mathrm{postorderTraversal}</tex> {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина inorderTraversal('''inorderTraversalNode'''(Node x)
'''if''' x != null
Корректность данного алгоритма следует из свойств бинарного дерева поиска.
preorderTraversal('''prefixTraversalNode'''(Node x)
'''if''' x != null
'''print'''(x.key) '''prefixTraversal'''preorderTraversal(x.left) '''prefixTraversal'''preorderTraversal(x.right)
postfixTraversal('''postfixTraversalNode'''(Node x)
'''if''' x != null
Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева.
=== Поиск элемента ===
[[Файл:Bst search.png|thumb|318px|Поиск элемента 4]]
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
'''Node '''search('''(Node ''' x, '''key ''' k)
'''if''' x == null '''or''' k == x.key
'''return''' x
'''if''' k < x.key
'''return search'''search(x.left, k)
'''else'''
'''return search'''search(x.right, k)
=== Поиск минимума и максимума ===
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям <tex>left </tex> от корня дерева, пока не встретится значение <tex>null</tex>. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям. '''Node '''minimum('''(Node ''' x)
'''if''' x.left == null
'''return''' x
'''return minimum'''minimum(x.left)
'''Node '''maximum('''(Node ''' x)
'''if''' x.right == null
'''return''' x
'''return maximum'''maximum(x.right)
Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время <tex>O(h)</tex>.
=== Поиск следующего и предыдущего элемента ===
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
'''Node '''next('''(Node ''' x)
'''if''' x.right != null
'''return minimum'''minimum(x.right)
y = x.parent
'''while''' y != null '''and''' x == y.right
'''return''' y
'''Node '''prev('''(Node ''' x)
'''if''' x.left != null
'''return maximum'''maximum(x.left)
y = x.parent
'''while''' y != null '''and''' x == y.left
=== Вставка ===
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
insert('''insertNode'''(Node x, '''Node ''' z) <font color="green">// корень поддерева, вставляемый элемент</font>
'''if''' z.key > x.key
'''if''' x.right != null
'''else'''
z.parent = x;
'''else'''
'''if''' x.left != null
'''else'''
z.parent = x;
| [[Файл:Bst_del3.png|900px]]
|}
delete('''deleteNode'''(Node root, '''Node ''' z) <font color="green">//корень поддерева, удаляемый элемент</font> '''Node ''' x, y <font color="green">//x - элемент, который нужно поместить вместо y</font> '''if''' z.left != null '''and''' z.right != null <font color="green">//если z имеет двух детей</font> y = '''next'''(z) <font color="green">//y - элемент, следующий за удаляемым, x - null</font>
x = null
'''if''' y == y.parent.left
'''else'''
y.parent.right = null
z.key = y.key <font color="green">//подвешиваем y вместо z</font>
z.data = y.data
'''else if''' z.left != null '''or''' z.right != null <font color="green">//eсли z имеет одного ребенка</font> y = z <font color="green">//y - удаляемый элемент</font> '''if''' y.left != null <font color="green">//x - ребенок y</font> x = y.left
'''else'''
x = y.right
'''else''' <font color="green">//если z не имеет детей</font> y = z <font color="green">//y - удаляемый элемент, x - null</font>
x = null
'''if''' x != null <font color="green">//подвешиваем x вместо y</font> x.parent = y.parent
'''if''' y.parent == null
root = x
