Изменения

Перейти к: навигация, поиск

Дерево поиска, наивная реализация

1504 байта добавлено, 16:57, 10 июня 2012
Нет описания правки
== Операции в бинарном дереве поиска ==
=== Обход дерева поиска ===
Для вывода всех ключей бинарного Есть три операции обхода узлов дерева поиска , отличающиеся порядком обхода узлов:* inorderTraversal - обход узлов в отсортированном порядке используется простой алгоритм * prefixTraversal - обход узлов в порядке: вершина, левое поддерево, правое поддерево* postfixTraversal - обход узлов в порядке: левое поддерево, правое поддерево, вершина '''inorderTraversal'''(Node x) '''if''' x != null '''inorderTraversal'''(англx. left) ''inorder tree traversal'print'''(x.key) '''inorderTraversal'''(x.right)Корректность данного алгоритма следует из свойств бинарного дерева поиска. inorderTreeWalk'''prefixTraversal'''(Node x) '''if ''' x != null inorderTreeWalk'''print'''(x.key) '''prefixTraversal'''(x.left) print'''prefixTraversal'''(x.right)  '''postfixTraversal'''(Node x) '''if''' x != null '''postfixTraversal'''(x.keyleft) inorderTreeWalk'''postfixTraversal'''(x.right)Данный алгоритм выполняет '''print'''(x.key)Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева. Корректность данного алгоритма следует из свойств бинарного дерева поиска.
=== Поиск элемента ===
[[Файл:Bst search.png|thumb|318px|Поиск элемента 4]]
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
treeSearchNode '''search'''(Node x, key k) '''if ''' x == null '''or ''' k == x.key '''return ''' x '''if ''' k < x.key '''return treeSearchsearch'''(x.left, k) '''else''' '''return treeSearchsearch'''(x.right, k)
=== Поиск минимума и максимума ===
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям left от корня дерева, пока не встретится значение null. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
treeMinimumNode '''minimum'''(Node x) '''while ''' x.left != null
x = x.left
'''return ''' x
treeMaximumNode '''maximum'''(Node x) '''while ''' x.right != null
x = x.right
'''return ''' x
Данные функции принимают корень дерева, и возвращают минимальный(максимальный) элемент в дереве. Обе процедуры выполняются за время <tex>O(h)</tex>.
=== Поиск следующего и предыдущего элемента ===
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
treeNextNode '''next'''(Node x) '''if ''' x.right != null '''return treeMinimumminimum'''(x.right)
y = x.parent
'''while ''' y != null '''and ''' x == y.right
x = y
y = y.parent
'''return ''' y
treePrevNode '''prev'''(Node x) '''if ''' x.left != null '''return treeMaximummaximum'''(x.left)
y = x.parent
'''while ''' y != null '''and ''' x == y.left
x = y
y = y.parent
'''return ''' y
Обе операции выполняются за время <tex>O(h)</tex>.
=== Вставка ===
Операция вставки работает аналогично поиску элемента, только при обнаружении нулевого указателя у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент. Приведем итеративную реализацию этого алгоритма. treeInsert'''insert'''(Node x, Node z) // корень дерева, вставляемый элемент
Node y = null
'''while ''' x != null
y = x
'''if ''' z.key > x.key
x = x.right
'''else'''
x = x.left
z.parent = y
'''if ''' z.key > y.key
y.right = z
'''else'''
y.left = z
Время работы алгоритма <tex>O(h)</tex>.
| [[Файл:Bst_del4.png‎]]
|}
treeDelete'''delete'''(Node troot, Node z) // корень дерева, удаляемый элемент Node x, y '''if ''' z.left == null '''or ''' z.right == null //y - удаляемый элемент, если тот имеет не более одного ребенка y = z '''else''' //иначе - следующий за ним y = treeNext'''next'''(z) '''if ''' y.left != null //x - ребенок y x = y.left '''else''' x = y.right '''if ''' x != null //подвешиваем x вместо y x.parent = y.parent '''if ''' y.parent == null t root = x '''else''' '''if ''' y == y.parent.left y.parent.left = x '''else''' y.parent.right = x '''if ''' y != z //если y - не удаляемый, а следующий за ним, то меняем z на y z.key = y.key z.data = y.data return y== Ссылки ==[[Упорядоченное множество]] [http://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 Двоичное дерево поиска]
== Литература ==
Yulya3102
355
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/24751»

Навигация