Изменения
→Реализация с использованием информации о родителе
Бинарное дерево поиска обладает следующим свойством: если <tex>x</tex> {{---}} узел бинарного дерева с ключом <tex>k</tex>, то все узлы в левом поддереве должны иметь ключи, меньшие <tex>k</tex>, а в правом поддереве большие <tex>k</tex>.
== Операции в бинарном дереве поиска ==
Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:
'''struct''' 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{inorderTraversal}</tex> {{---}} обход узлов в отсортированном порядке,* <tex>\mathrm{preorderTraversal}</tex> {{---}} обход узлов в порядке: вершина, левое поддерево, правое поддерево,* <tex>\mathrm{postorderTraversal}</tex> {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина. '''func''' inorderTraversal(x : '''Node''' x): '''if''' x != ''null''
inorderTraversal(x.left)
'''print''' x.key
inorderTraversal(x.right)
'''print''' x.key
preorderTraversal(x.left)
preorderTraversal(x.right)
При выполнении данного обхода вершины будут выведены в следующем порядке: ''8 3 1 6 4 7 10 14 13''.
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
'''if''' k < x.key
'''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
'''return''' maximum(x.right)
=== Поиск следующего и предыдущего элемента ===
====Реализация с использованием информации о родителе====Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним предыдущий ему элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя. '''Node''' next(x : '''Node''' x): '''if''' x.right != ''null''
'''return''' minimum(x.right)
y = x.parent
'''while''' y != ''null '' '''and''' x == y.right
x = y
y = y.parent
'''return''' y
'''Node''' prev(x : '''Node''' x): '''if''' x.left != ''null''
'''return''' maximum(x.left)
y = x.parent
'''while''' y != ''null '' '''and''' x == y.left
x = y
y = y.parent
'''return''' y
Обе операции выполняются за время <tex>O(h)</tex>.
====Реализация без использования информации о родителе====
Рассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, храня текущий узел <tex>current</tex> и узел <tex>successor</tex>, последний посещенный узел, ключ которого больше <tex>x</tex>. <br>
Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла <tex>current</tex>. Если <tex>current.key \leqslant x</tex>, значит следующий за <tex>x</tex> узел находится в правом поддереве (в левом поддереве все ключи меньше <tex>current.key</tex>). Если же <tex>x < current.key</tex>, то <tex>x < next(x) \leqslant current.key</tex>, поэтому <tex>current</tex> может быть следующим для ключа <tex>x</tex>, либо следующий узел содержится в левом поддереве <tex>current</tex>. Перейдем к нужному поддереву и повторим те же самые действия.<br>
Аналогично реализуется операция поиска предыдущего элемента.
'''Node''' next(x : '''T'''):
'''Node''' current = root, successor = ''null'' <font color="green">// root {{---}} корень дерева</font>
'''while''' current != ''null''
'''if''' current.key > x
successor = current
current = current.left
'''else'''
current = current.right
'''return''' successor
=== Вставка ===
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
====Реализация с использованием информации о родителе==== '''func''' insert(x : '''Node''' x, z : '''Node''' z) : <font color="green">// x {{---}} корень поддерева, z {{---}} вставляемый элемент</font> '''while''' x != ''null'' '''if''' z.key > x.key '''if''' x.right != ''null'' insert( x = x.right, z) '''else''' z.parent = x; x.right = z; '''break''' '''elseif'''z.key < x.key '''if''' x.left != ''null'' x = x.left '''else''' z.parent = x x.left = z '''break'''====Реализация без использования информации о родителе==== '''Node''' insert(x.left: '''Node''', z: '''T'''): <font color="green">// x {{---}} корень поддерева, z {{---}} вставляемый ключ</font> '''if''' x == ''null'' '''return''' Node(z) <font color="green">// подвесим Node с key = z</font> '''elseif'''z < x.key z x.parent left = insert(x;.left, z) '''else if''' z > x.key x.left right = insert(x.right, z;) '''return''' x Время работы алгоритма для обеих реализаций {{---}} <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">// корень поддерева<tex>t</tex> {{---}} дерево, <tex>v</tex> {{---}} удаляемый элемент</font> p = v.parent <font color="green">// предок удаляемого элемента</font> '''if''' v.left == ''null'''Node''and''' v.right == ''null'' x, y <font color="green">// x первый случай: удаляемый элемент - элемент, который нужно поместить вместо yлист</font> '''if''' zp.left != = v p.left = ''null'' '''if''' p.right == v p.right = ''null'' '''else if''' v.left == ''null '''and''or''' zv.right != = ''null '' <font color="green">// если z второй случай: удаляемый элемент имеет двух детейодного потомка</font> y '''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 == v p.left = v.left '''else''' p.right = v.left v.left.parent = p '''nextelse'''(z) <font color="green">// y - третий случай: удаляемый элемент, следующий за удаляемым, x - nullимеет двух потомков</font> x successor = nullnext(v, t) v.key = successor.key '''if''' y == ysuccessor.parent.left== successor y successor.parent.left = successor.right '''if''' successor.right != ''null'' successor.right.parent = successor.parent
'''else'''
'''else'''
== Ссылки Источники информации==* [httphttps://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0 Википедия {{---}} Двоичное дерево поиска] * [https://en.wikipedia.org/wiki/Binary_search_tree Wikipedia {{---}} Binary search tree]== Литература ==1. * Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
[[Категория: Деревья поиска]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]