Изменения
→Реализация с использованием информации о родителе
[[Файл:Binary_search_tree.svg.png|right|300px|thumb|Бинарное дерево поиска из 9 элементов]]'''Бинарное дерево поиска ''' (англ. ''binary search tree, BST)''' ) {{--- }} структура данных для работы с [[Упорядоченное множество|упорядоченными множествами]].Бинарное дерево поиска обладает следующим свойством: если <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> {{- --}} обход узлов в отсортированном порядке,* prefixTraversal <tex>\mathrm{preorderTraversal}</tex> {{- --}} обход узлов в порядке: вершина, левое поддерево, правое поддерево,* postfixTraversal <tex>\mathrm{postorderTraversal}</tex> {{--- }} обход узлов в порядке: левое поддерево, правое поддерево, вершина. '''func'''inorderTraversal(x : '''(Node x'''): '''if''' x != ''null'' '''inorderTraversal'''(x.left) '''print'''(x.key) '''inorderTraversal'''(x.right)Корректность При выполнении данного алгоритма следует из свойств бинарного дерева поискаобхода вершины будут выведены в следующем порядке: ''1 3 4 6 7 8 10 13 14''. '''prefixTraversalfunc'''preorderTraversal(x : '''Node x''') '''if''' x != ''null'' '''print'''x.key preorderTraversal(x.keyleft) preorderTraversal(x.right)При выполнении данного обхода вершины будут выведены в следующем порядке: ''8 3 1 6 4 7 10 14 13''. '''func''' postorderTraversal(x : '''Node''') '''if'''prefixTraversalx != ''null'' postorderTraversal(x.left) postorderTraversal(x.right) '''prefixTraversalprint'''(x.rightkeyПри выполнении данного обхода вершины будут выведены в следующем порядке: ''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''', key k: '''T'''): '''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)</div>
=== Поиск минимума и максимума ===
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям <tex>left </tex> от корня дерева, пока не встретится значение <tex>null</tex>. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям. '''Node '''minimum(x : '''(Node x'''): '''if''' x.left == ''null''
'''return''' x
'''return minimum'''minimum(x.left)
'''Node '''maximum(x : '''(Node x'''): '''if''' x.right == ''null''
'''return''' x
'''return maximum'''maximum(x.right)
Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время <tex>O(h)</tex>.
=== Поиск следующего и предыдущего элемента ===
====Реализация с использованием информации о родителе====Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним предыдущий ему элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя. '''Node '''next(x : '''(Node x'''): '''if''' x.right != ''null'' '''return minimum'''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'''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> Node y '''while''' x != ''null'' '''if''' z.key > x.key '''whileif''' x .right != ''null'' x = x.right '''else''' y z.parent = x x.right = z '''break''' '''else if''' z.key > < x.key '''if''' x.left != ''null'' x = x.rightleft '''else''' z.parent = x = x.left= z '''break'''====Реализация без использования информации о родителе==== '''Node''' insert(x : '''Node''', z.parent : '''T'''): <font color= y"green">// x {{---}} корень поддерева, z {{---}} вставляемый ключ</font> '''if''' x == ''null'' '''return''' Node(z.) <font color="green">// подвесим Node с key = z</font> y '''else if''' z < x.key yx.right left = insert(x.left, z) '''elseif'''z > x.key yx.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> Node x, y '''if''' v.left == ''null'' '''and''' v.right == ''null'' <font color="green">// первый случай: удаляемый элемент - лист</font> '''if''' p.left == v p.left = ''null'' '''if''' p.right == v p.right = ''null'' '''else if''' zv.left == ''null '' '''or''' zv.right == ''null '' <font color="green">//y - второй случай: удаляемый элемент, если тот имеет не более одного ребенкапотомка</font> '''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 '''else''' <font color="green">// третий случай: удаляемый элемент имеет двух потомков</font> y successor = next(v, t) v.key = successor.key '''if''' successor.parent.left == successor successor.parent.left = successor.right '''if''' successor.right != ''null'' successor.right.parent = successor.parent '''else''' successor.parent.right = successor.left '''if''' successor.left != ''null'' successor.right.parent = successor.parent ====Рекурсивная реализация====При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить '''этот''' минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z </tex>: '''Node''' delete(root : '''Node''', z : '''elseT''' ): <font color="green">//корень поддерева, удаляемый ключ</иначе - следующий за нимfont> '''if''' root == ''null'' '''return''' root '''if''' z < root.key y root.left = delete(root.left, z) '''nextelse if'''z > root.key root.right = delete(root.right, z) '''else if''' yroot.left != ''null //x - ребенок y'' '''and''' root.right != ''null'' root.key = minimum(root.right).key x root.right = ydelete(root.right, root.left key)
'''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
[[Категория: Деревья поиска]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]