188
правок
Изменения
Нет описания правки
Бинарное дерево поиска обладает следующим свойством: если <tex>x</tex> {{---}} узел бинарного дерева с ключом <tex>k</tex>, то все узлы в левом поддереве должны иметь ключи, меньшие <tex>k</tex>, а в правом поддереве большие <tex>k</tex>.
== Операции в бинарном дереве поиска ==
Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:
'''Node''':
'''T''' key <font color="green">// ключ узла</font>
'''Node''' left <font color="green">// указатель на левого потомка</font>
'''Node''' right <font color="green">// указатель на правого потомка</font>
'''Node''' parent <font color="green">// указатель на предка</font>
=== Обход дерева поиска ===
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
* <tex>\mathrm{preorderTraversal}</tex> {{---}} обход узлов в порядке: вершина, левое поддерево, правое поддерево,
* <tex>\mathrm{postorderTraversal}</tex> {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина.
'''func''' inorderTraversal(x : '''Node''' x):
'''if''' x != ''null''
inorderTraversal(x.left)
При выполнении данного обхода вершины будут выведены в следующем порядке: ''1 3 4 6 7 8 10 13 14''.
'''func''' preorderTraversal(x : '''Node''' x)
'''if''' x != ''null''
'''print''' x.key
При выполнении данного обхода вершины будут выведены в следующем порядке: ''8 3 1 6 4 7 10 14 13''.
'''func''' postorderTraversal(x : '''Node''' x)
'''if''' x != ''null''
postorderTraversal(x.left)
postorderTraversal(x.right)
'''print''' x.key
При выполнении данного обхода вершины будут выведены в следующем порядке: ''1 4 7 6 3 13 14 10 8 ''.
Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева.
=== Поиск элемента ===
[[Файл:Bst search.png|thumbframe|right|318px|Поиск элемента 4]]
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
<div style="width: 65%"> '''Node''' search(x : '''Node''' x, k : '''keyT''' k):
'''if''' x == ''null'' '''or''' k == x.key
'''return''' x
'''else'''
'''return''' search(x.right, k)
</div>
=== Поиск минимума и максимума ===
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям <tex>left</tex> от корня дерева, пока не встретится значение <tex>null</tex>. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
'''Node''' minimum(x : '''Node''' x):
'''if''' x.left == ''null''
'''return''' x
'''return''' minimum(x.left)
'''Node''' maximum(x : '''Node''' x):
'''if''' x.right == ''null''
'''return''' x
====Реализация с использованием информации о родителе====
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
'''Node''' next(x : '''Node''' x):
'''if''' x.right != ''null''
'''return''' minimum(x.right)
'''return''' y
'''Node''' prev(x : '''Node''' x):
'''if''' x.left != ''null''
'''return''' maximum(x.left)
====Реализация без использования информации о родителе====
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то начнем поиск от корня. Спускаемся вниз по дереву. Если значение узла больше значения в рассматриваемом в данный момент узле, перейдем в правое поддерево, иначе перейдем в левое поддерево. Аналогично выполняется поиск предыдущего элемента. Рекурсивные реализации обеих функций:
'''Node''' next(x : '''Node''' x, t : '''Node''' t) : <font color="green">// x {{--- }} элемент, для которого ищем следующий, t {{--- }} текущее поддерево</font>
'''if''' t != ''null''
'''Node''' successor = next(x, t.left)
'''return''' ''null''
'''Node''' prev(x : '''Node''' x, t : '''Node''' t) : <font color="green">// x {{--- }} элемент, для которого ищем предыдущий, t {{--- }} текущее поддерево</font>
'''if''' t != ''null''
'''Node''' ancestor = prev(x, t.right)
=== Вставка ===
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
====Реализация с использованием информации о родителе==== '''func''' insert(x : '''Node''' x, z : '''Node''' z) : <font color="green">// x {{- --}} корень поддерева, z {{--- }} вставляемый элемент</font>
'''if''' z.key > x.key
'''if''' x.right != ''null''
z.parent = x
x.left = z
====Реализация без использования информации о родителе====
'''func''' insert(x : '''Node''', z : '''Node'''): <font color="green">// x {{---}} корень поддерева, z {{---}} вставляемый элемент</font>
'''if''' z.key <= x.key
'''if''' x.left == ''null''
x.left = z
'''else'''
insert(x.left, z)
'''else'''
'''if''' x.right == ''null''
x.right = z
'''else'''
insert(x.right, z)
Время работы алгоритма для обеих реализаций {{---}} <tex>O(h)</tex>.
=== Удаление ===
====Нерекурсивная реализация====
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на <tex>null</tex>. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка) и переместить , его правого потомка подвесить на место удаляемого узланайденного элемента, а удаляемый узел заменить найденным узлом. Таким образом, свойство бинарного дерева поиска не будет нарушено. Время работы алгоритма {{---}} <tex>O(h)</tex>.
{| border="1" cellpadding="5" cellspacing="0"
!Случай
| [[Файл:Bst_del3.png|900px]]
|}
'''func''' delete(t : '''Node''' root, v : '''Node''' z) : <font color="green">// корень поддерева, дерево и удаляемый элемент</font> '''Node''' x, y p = v.parent <font color="green">// x - элемент, который нужно поместить вместо yпредок удаляемого элемента</font> '''if''' zv.left !== ''null'' '''and''' zv.right !== ''null'' <font color="green">// если z имеет двух детейпервый случай: удаляемый элемент - лист</font> y = '''nextif'''(z) <font colorp.left =="green">// y - элемент, следующий за удаляемым, x - null</font>v x p.left = ''null'' '''if''' y p.right == y.parent.leftv y p.parent.left right = ''null'' '''else''' y '''if''' v.parentleft == ''null'' '''or''' v.right == ''null'' z.key = y.key <font color="green">// подвешиваем y вместо zвторой случай: удаляемый элемент имеет одного потомка</font> z.data = y.data '''else if''' zv.left !== ''null'' '''orif''' zp.left == v p.left = v.right != '''else'null'' <font color p.right ="green">// eсли z имеет одного ребенка</font>v.right y v.right.parent = z <font color="green">// y - удаляемый элемент</font>p '''else''' '''if''' yp.left != ''null'' <font color="green">// x - ребенок y</font>v x p.left = yv.left '''else''' x p.right = yv.rightleft v.left.parent = p '''else''' <font color="green">// если z не третий случай: удаляемый элемент имеет детейдвух потомков</font> y successor = z <font color="green">// y - удаляемый элементnext(v, x - null</font>t) x v.key = ''null''successor.key '''if''' x !successor.parent.left = ''null'' <font color="green">// подвешиваем x вместо y</font>successor x successor.parent .left = ysuccessor.parent right '''if''' ysuccessor.parent =right != ''null'' root successor.right.parent = xsuccessor.parent '''else''' successor.parent.right = successor.right '''if''' y == ysuccessor.parent.left y.parent.left right != x '''else'null'' y successor.right.parent= successor.right = xparent
====Рекурсивная реализация====
При рекурсивном удаления узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:
'''Node''' delete(root : '''Node''' root, z : '''Node''' z) : <font color="green">// корень поддерева, удаляемый элемент</font>
'''if''' root == ''null''
'''return''' root
