Изменения
→Реализация с использованием информации о родителе
Бинарное дерево поиска обладает следующим свойством: если <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> '''while''' x != ''null'' '''if''' z.key > x.key '''if''' x.right != null ''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 '''insertelse'''( z.parent = x x.left= z '''break'''====Реализация без использования информации о родителе==== '''Node''' insert(x : '''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.left key x.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">//x первый случай: удаляемый элемент - элемент, который нужно поместить вместо yлист</font> '''if''' p.left == v p.left = ''null'' '''if''' p.right == v p.right = ''null'' '''else if''' zv.left != = ''null '''and''or''' zv.right != = ''null '' <font color="green">//если z второй случай: удаляемый элемент имеет двух детейодного потомка</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 y v.left.parent = p '''nextelse'''(z) <font color="green">//y - третий случай: удаляемый элементимеет двух потомков</font> successor = next(v, следующий за удаляемым, x - nullt) x v.key = nullsuccessor.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
[[Категория: Деревья поиска]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]