Дерево поиска, наивная реализация — различия между версиями
(→Задачи о бинарном дереве поиска: 3) |
(→Проверка того, что заданное дерево является деревом поиска: 2) |
||
Строка 208: | Строка 208: | ||
'''if''' v.left != ''null'' | '''if''' v.left != ''null'' | ||
'''if''' v.left.key > v.key '''or''' v.left.key < min | '''if''' v.left.key > v.key '''or''' v.left.key < min | ||
− | '''return''' false | + | '''return''' ''false'' |
'''else''' check(v.left, min, v.key) | '''else''' check(v.left, min, v.key) | ||
'''if''' v.right.key < v.key '''or''' v.right.key > max | '''if''' v.right.key < v.key '''or''' v.right.key > max | ||
− | '''return''' false | + | '''return''' ''false'' |
'''else''' check(v.right, v.key, max) | '''else''' check(v.right, v.key, max) | ||
− | '''return''' true | + | '''return''' ''true'' |
===Поиск максимального поддерева, являющегося BST, в заданном двоичном дереве=== | ===Поиск максимального поддерева, являющегося BST, в заданном двоичном дереве=== |
Версия 11:23, 9 января 2017
Бинарное дерево поиска обладает следующим свойством: если
— узел бинарного дерева с ключом , то все узлы в левом поддереве должны иметь ключи, меньшие , а в правом поддереве большие .Содержание
Операции в бинарном дереве поиска
Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:
struct Node: T key // ключ узла Node left // указатель на левого потомка Node right // указатель на правого потомка Node parent // указатель на предка
Обход дерева поиска
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
- — обход узлов в отсортированном порядке,
- — обход узлов в порядке: вершина, левое поддерево, правое поддерево,
- — обход узлов в порядке: левое поддерево, правое поддерево, вершина.
func inorderTraversal(x : Node): if x != null inorderTraversal(x.left) print x.key inorderTraversal(x.right)
При выполнении данного обхода вершины будут выведены в следующем порядке: 1 3 4 6 7 8 10 13 14.
func preorderTraversal(x : Node) if x != null print x.key preorderTraversal(x.left) preorderTraversal(x.right)
При выполнении данного обхода вершины будут выведены в следующем порядке: 8 3 1 6 4 7 10 14 13.
func postorderTraversal(x : Node) if x != null postorderTraversal(x.left) postorderTraversal(x.right) print x.key
При выполнении данного обхода вершины будут выведены в следующем порядке: 1 4 7 6 3 13 14 10 8.
Данные алгоритмы выполняют обход за время
, поскольку процедура вызывается ровно два раза для каждого узла дерева.Поиск элемента
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы
, где — высота дерева.Node search(x : Node, k : T): if x == null or k == x.key return x if k < x.key return search(x.left, k) else return search(x.right, k)
Поиск минимума и максимума
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям
от корня дерева, пока не встретится значение . Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.Node minimum(x : Node): if x.left == null return x return minimum(x.left)
Node maximum(x : Node): if x.right == null return x return maximum(x.right)
Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время
.Поиск следующего и предыдущего элемента
Реализация с использованием информации о родителе
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
Node next(x : Node): 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): 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
Обе операции выполняются за время
.Реализация без использования информации о родителе
Рассмотрим поиск следующего элемента для некоторого ключа
Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла . Если , значит следующий за узел находится в правом поддереве (в левом поддереве все ключи меньше ). Если же , то , поэтому может быть следующим для ключа , либо следующий узел содержится в левом поддереве . Перейдем к нужному поддереву и повторим те же самые действия.
Аналогично реализуется операция поиска предыдущего элемента.
Node next(x : T): Node current = root, successor = null // root — корень дерева while current != null if current.key > x successor = current current = current.left else current = current.right return successor
Вставка
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
Реализация с использованием информации о родителе
func insert(x : Node, z : Node): // x — корень поддерева, z — вставляемый элемент while x != null if z.key > x.key if x.right != null x = x.right else z.parent = x x.right = z break else if z.key < x.key if x.left != null x = x.left else z.parent = x x.left = z break
Реализация без использования информации о родителе
Node insert(x : Node, z : T): // x — корень поддерева, z — вставляемый ключ if x == null return Node(z) // подвесим Node с key = z else if z < x.key x.left = insert(x.left, z) else if z > x.key x.right = insert(x.right, z) return x
Время работы алгоритма для обеих реализаций —
.Удаление
Нерекурсивная реализация
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на
. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка), его правого потомка подвесить на место найденного элемента, а удаляемый узел заменить найденным узлом. Таким образом, свойство бинарного дерева поиска не будет нарушено. Данная реализация удаления не увеличивает высоту дерева. Время работы алгоритма — .Случай | Иллюстрация |
---|---|
Удаление листа | ![]() |
Удаление узла с одним дочерним узлом | ![]() |
Удаление узла с двумя дочерними узлами | ![]() |
func delete(t : Node, v : Node): //— дерево, — удаляемый элемент p = v.parent // предок удаляемого элемента if v.left == null and v.right == null // первый случай: удаляемый элемент - лист if p.left == v p.left = null if p.right == v p.right = null else if v.left == null or v.right == null // второй случай: удаляемый элемент имеет одного потомка 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 // третий случай: удаляемый элемент имеет двух потомков 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.right if successor.right != null successor.right.parent = successor.parent
Рекурсивная реализация
При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма —
. Рекурсивная функция, возвращающая дерево с удаленным элементом :Node delete(root : Node, z : T): // корень поддерева, удаляемый ключ if root == null return root if z < root.key root.left = delete(root.left, z) else if z > root.key root.right = delete(root.right, z) else if root.left != null and root.right != null root.key = minimum(root.right).key root.right = delete(root.right, root.right.key) else if root.left != null root = root.left else root = root.right return root
Задачи о бинарном дереве поиска
Проверка того, что заданное дерево является деревом поиска
Задача: |
Определить, является ли заданное двоичное дерево деревом поиска. |
Для того чтобы решить эту задачу, применим обход в глубину. Запустим от корня рекурсивную логическую функцию, которая выведет , если дерево является BST и в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение . Если же, дойдя до листьев, функция не встретит на своём пути такие вершины, она вернёт значение .
bool check(v : Node, min: integer, max: integer): //min и max — минимально и максимально допустимые значения в вершинах поддерева. if v.left != null if v.left.key > v.key or v.left.key < min return false else check(v.left, min, v.key) if v.right.key < v.key or v.right.key > max return false else check(v.right, v.key, max) return true
Поиск максимального поддерева, являющегося BST, в заданном двоичном дереве
Задача: |
Найти в данном дереве максимальное из поддеревьев поиска. |
Будем рассматривать каждую вершину дерева, предполагая, что она может являться корнем максимального поддерева поиска. Найдём для каждой из них количество всех вершин, которые могут находиться в таком поддереве. Максимальный из результатов, получаемых на каждом шаге, будем запоминать. Вместе с максимумом будем запоминать и соответствующую ему вершину. После того, как мы обошли всё дерево и нашли корень дерева поиска с наибольшим количеством вершин, запускаем процедуру, выводящую все вершины на экран.
Node root() maxdp = -1 maxroot = null for u in Tree // Здесь Tree — заданное двоичное дерево. dp = dfs(u,, ) if dp > maxdp maxdp = dp maxroot = u return maxroot
Функция
позволяет найти для каждой вершин максимально возможное количество узлов поддерева. На вход функции подаются сама анализируемая вершина и левая и правая границы интервала, в которой могут находиться значения в её поддереве. Начальные значения двух последних аргументов равны и соответственно, где — очень большое число, т.е. ни один ключ дерева не превосходит его по модулю.В основе функции также лежит обход в глубину. Рекурсивная функция обходит всех существующих детей вершины, поданной на вход, и, если ребёнок не нарушает условия дерева поиска, она добавляет его в поддерево и анализирует его потомков. В этом случае роль будет разыгрывать ребёнок, удовлетворяющий условию дерева поиска. Если он был левым сыном, то максимально возможному значению присваивается число, стоящее в его родителе, а минимальное возможное значение не изменяется. Наоборот, если он был правым сыном, увеличиваем минимум, а максимум оставляем тем же. В случае, когда левый или правый сын не удовлетворяет условию дерева поиска, этот узел не включается в искомое поддерево и дальше не рассматривается.
Функция возвращает значение переменной
, где записано количество вершин поддерева.int dfs(v: Node, max: T, min: T) res = 1 if v.left != null if v.left.key < v.key and v.left.key > max res += dfs(v.left, v.left.key, min) if v.right != null if v.right.key > v.key and v.right.key < min res += dfs(v.left, max, v.left.key) return res
Наконец, рассмотрим процедуру
, выводящую вершины максимального дерева поиска. Она также будет принимать на вход вершину и две границы, позволяющие включить только те вершины, которые удовлетворяют определению дерева поиска.func dfsPrint(v: Node, max: T, min: T) print v.key if v.left != null if v.left.key < v.key and v.left.key > max dfsPrint(v.left, v.left.key, min) if v.right != null if v.right.key > v.key and v.right.key < min dfsPrint(v.left, max, v.left.key)
Заметим, что выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будет выведено вершин. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына.
Разберём алгоритм на примере последовательности для приведённого выше дерева. Она выглядит так: 8 2 1 4 3 5. Сначала в корень записывается 8. Затем его левым сыном становится вершина с номером 2, а её левым сыном — 1. Следующее значение — 4 — уже нарушает убывающую подпоследовательность. Подберём для него вершину, где лежит значение, меньшее его, причём такая вершина максимальна (в противном случае он будет превосходить и прародителя, находясь в его левом поддереве, а это противоречит определению дерева поиска). Это узел с числом 2. Сделаем его правым сыном рассматриваемую вершину. Затем снова дадим левых потомков последней добавленной вершине, опять же, пока не найдём ключ, нарушающий порядок убывания. В нашем случае в дерево дописывается 3. Для следующего значения снова ищем родителя, для которого он станет правым сыном. Это значение равно 4. Добавляем 5 как правого сына для вершины 4. Итак, мы построили дерево.
См. также
Источники информации
- Википедия — Двоичное дерево поиска
- Wikipedia — Binary search tree
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4