Дерево поиска, наивная реализация — различия между версиями
м |
|||
| Строка 8: | Строка 8: | ||
* <tex>\mathrm{postorderTraversal}</tex> {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина | * <tex>\mathrm{postorderTraversal}</tex> {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина | ||
inorderTraversal('''Node''' x) | inorderTraversal('''Node''' x) | ||
| − | '''if''' x != null | + | '''if''' x != ''null'' |
inorderTraversal(x.left) | inorderTraversal(x.left) | ||
'''print''' x.key | '''print''' x.key | ||
| Строка 14: | Строка 14: | ||
Корректность данного алгоритма следует из свойств бинарного дерева поиска. | Корректность данного алгоритма следует из свойств бинарного дерева поиска. | ||
preorderTraversal('''Node''' x) | preorderTraversal('''Node''' x) | ||
| − | '''if''' x != null | + | '''if''' x != ''null'' |
'''print''' x.key | '''print''' x.key | ||
preorderTraversal(x.left) | preorderTraversal(x.left) | ||
preorderTraversal(x.right) | preorderTraversal(x.right) | ||
| − | + | postorderTraversal('''Node''' x) | |
| − | '''if''' x != null | + | '''if''' x != ''null'' |
postorderTraversal(x.left) | postorderTraversal(x.left) | ||
postorderTraversal(x.right) | postorderTraversal(x.right) | ||
| Строка 26: | Строка 26: | ||
Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева. | Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева. | ||
=== Поиск элемента === | === Поиск элемента === | ||
| − | [[Файл:Bst search.png|thumb|318px|Поиск элемента 4]] | + | [[Файл:Bst search.png|thumb|right|318px|Поиск элемента 4]] |
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева. | Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева. | ||
'''Node''' search('''Node''' x, '''key''' k) | '''Node''' search('''Node''' x, '''key''' k) | ||
| − | '''if''' x == null '''or''' k == x.key | + | '''if''' x == ''null'' '''or''' k == x.key |
'''return''' x | '''return''' x | ||
'''if''' k < x.key | '''if''' k < x.key | ||
| Строка 39: | Строка 39: | ||
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям <tex>left</tex> от корня дерева, пока не встретится значение <tex>null</tex>. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям. | Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям <tex>left</tex> от корня дерева, пока не встретится значение <tex>null</tex>. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям. | ||
'''Node''' minimum('''Node''' x) | '''Node''' minimum('''Node''' x) | ||
| − | '''if''' x.left == null | + | '''if''' x.left == ''null'' |
'''return''' x | '''return''' x | ||
'''return''' minimum(x.left) | '''return''' minimum(x.left) | ||
'''Node''' maximum('''Node''' x) | '''Node''' maximum('''Node''' x) | ||
| − | '''if''' x.right == null | + | '''if''' x.right == ''null'' |
'''return''' x | '''return''' x | ||
'''return''' maximum(x.right) | '''return''' maximum(x.right) | ||
| Строка 53: | Строка 53: | ||
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя. | Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя. | ||
'''Node''' next('''Node''' x) | '''Node''' next('''Node''' x) | ||
| − | '''if''' x.right != null | + | '''if''' x.right != ''null'' |
'''return''' minimum(x.right) | '''return''' minimum(x.right) | ||
y = x.parent | y = x.parent | ||
| − | '''while''' y != null '''and''' x == y.right | + | '''while''' y != ''null'' '''and''' x == y.right |
x = y | x = y | ||
y = y.parent | y = y.parent | ||
| Строка 62: | Строка 62: | ||
'''Node''' prev('''Node''' x) | '''Node''' prev('''Node''' x) | ||
| − | '''if''' x.left != null | + | '''if''' x.left != ''null'' |
'''return''' maximum(x.left) | '''return''' maximum(x.left) | ||
y = x.parent | y = x.parent | ||
| − | '''while''' y != null '''and''' x == y.left | + | '''while''' y != ''null'' '''and''' x == y.left |
x = y | x = y | ||
y = y.parent | y = y.parent | ||
| Строка 73: | Строка 73: | ||
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то начнем поиск от корня. Спускаемся вниз по дереву. Если значение узла больше значения в рассматриваемом в данный момент узле, перейдем в правое поддерево, иначе перейдем в левое поддерево. Аналогично выполняется поиск предыдущего элемента. Рекурсивные реализации обеих функций: | Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то начнем поиск от корня. Спускаемся вниз по дереву. Если значение узла больше значения в рассматриваемом в данный момент узле, перейдем в правое поддерево, иначе перейдем в левое поддерево. Аналогично выполняется поиск предыдущего элемента. Рекурсивные реализации обеих функций: | ||
'''Node''' next('''Node''' x, '''Node''' t) <font color="green">// x - элемент, для которого ищем следующий, t - текущее поддерево</font> | '''Node''' next('''Node''' x, '''Node''' t) <font color="green">// x - элемент, для которого ищем следующий, t - текущее поддерево</font> | ||
| − | '''if''' t != null | + | '''if''' t != ''null'' |
'''Node''' successor = next(x, t.left) | '''Node''' successor = next(x, t.left) | ||
| − | '''if''' successor == null | + | '''if''' successor == ''null'' |
'''if''' t.key > x.key | '''if''' t.key > x.key | ||
'''return''' t | '''return''' t | ||
| Строка 81: | Строка 81: | ||
'''return''' successor | '''return''' successor | ||
'''return''' next(x, t.right) | '''return''' next(x, t.right) | ||
| − | '''return''' null | + | '''return''' ''null'' |
'''Node''' prev('''Node''' x, '''Node''' t) <font color="green">// x - элемент, для которого ищем предыдущий, t - текущее поддерево</font> | '''Node''' prev('''Node''' x, '''Node''' t) <font color="green">// x - элемент, для которого ищем предыдущий, t - текущее поддерево</font> | ||
| − | '''if''' t != null | + | '''if''' t != ''null'' |
'''Node''' ancestor = prev(x, t.right) | '''Node''' ancestor = prev(x, t.right) | ||
| − | '''if''' ancestor == null | + | '''if''' ancestor == ''null'' |
'''if''' t.key <= x.key | '''if''' t.key <= x.key | ||
'''return''' t | '''return''' t | ||
| Строка 92: | Строка 92: | ||
'''return''' ancestor | '''return''' ancestor | ||
'''return''' prev(x, t.left) | '''return''' prev(x, t.left) | ||
| − | '''return''' null | + | '''return''' ''null'' |
Обе операции выполняются за время <tex>O(h)</tex>. | Обе операции выполняются за время <tex>O(h)</tex>. | ||
=== Вставка === | === Вставка === | ||
| Строка 98: | Строка 98: | ||
insert('''Node''' x, '''Node''' z) <font color="green">// x - корень поддерева, z - вставляемый элемент</font> | insert('''Node''' x, '''Node''' z) <font color="green">// x - корень поддерева, z - вставляемый элемент</font> | ||
'''if''' z.key > x.key | '''if''' z.key > x.key | ||
| − | '''if''' x.right != null | + | '''if''' x.right != ''null'' |
insert(x.right, z) | insert(x.right, z) | ||
'''else''' | '''else''' | ||
| − | z.parent = x | + | z.parent = x |
| − | x.right = z | + | x.right = z |
'''else''' | '''else''' | ||
| − | '''if''' x.left != null | + | '''if''' x.left != ''null'' |
insert(x.left, z) | insert(x.left, z) | ||
'''else''' | '''else''' | ||
| − | z.parent = x | + | z.parent = x |
| − | x.left = z | + | x.left = z |
Время работы алгоритма {{---}} <tex>O(h)</tex>. | Время работы алгоритма {{---}} <tex>O(h)</tex>. | ||
| Строка 130: | Строка 130: | ||
delete('''Node''' root, '''Node''' z) <font color="green">// корень поддерева, удаляемый элемент</font> | delete('''Node''' root, '''Node''' z) <font color="green">// корень поддерева, удаляемый элемент</font> | ||
'''Node''' x, y <font color="green">// x - элемент, который нужно поместить вместо y</font> | '''Node''' x, y <font color="green">// x - элемент, который нужно поместить вместо y</font> | ||
| − | '''if''' z.left != null '''and''' z.right != null <font color="green">// если z имеет двух детей</font> | + | '''if''' z.left != ''null'' '''and''' z.right != ''null'' <font color="green">// если z имеет двух детей</font> |
y = '''next'''(z) <font color="green">// y - элемент, следующий за удаляемым, x - null</font> | y = '''next'''(z) <font color="green">// y - элемент, следующий за удаляемым, x - null</font> | ||
| − | x = null | + | x = ''null'' |
'''if''' y == y.parent.left | '''if''' y == y.parent.left | ||
| − | y.parent.left = null | + | y.parent.left = ''null'' |
'''else''' | '''else''' | ||
| − | y.parent.right = null | + | y.parent.right = ''null'' |
z.key = y.key <font color="green">// подвешиваем y вместо z</font> | z.key = y.key <font color="green">// подвешиваем y вместо z</font> | ||
z.data = y.data | z.data = y.data | ||
| − | '''else if''' z.left != null '''or''' z.right != null <font color="green">// eсли z имеет одного ребенка</font> | + | '''else if''' z.left != ''null'' '''or''' z.right != ''null'' <font color="green">// eсли z имеет одного ребенка</font> |
y = z <font color="green">// y - удаляемый элемент</font> | y = z <font color="green">// y - удаляемый элемент</font> | ||
| − | '''if''' y.left != null <font color="green">// x - ребенок y</font> | + | '''if''' y.left != ''null'' <font color="green">// x - ребенок y</font> |
x = y.left | x = y.left | ||
'''else''' | '''else''' | ||
| Строка 147: | Строка 147: | ||
'''else''' <font color="green">// если z не имеет детей</font> | '''else''' <font color="green">// если z не имеет детей</font> | ||
y = z <font color="green">// y - удаляемый элемент, x - null</font> | y = z <font color="green">// y - удаляемый элемент, x - null</font> | ||
| − | x = null | + | x = ''null'' |
| − | '''if''' x != null <font color="green">// подвешиваем x вместо y</font> | + | '''if''' x != ''null'' <font color="green">// подвешиваем x вместо y</font> |
x.parent = y.parent | x.parent = y.parent | ||
| − | '''if''' y.parent == null | + | '''if''' y.parent == ''null'' |
root = x | root = x | ||
'''else''' | '''else''' | ||
| Строка 161: | Строка 161: | ||
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>: | Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>: | ||
'''Node''' delete('''Node''' root, '''Node''' z) <font color="green">// корень поддерева, удаляемый элемент</font> | '''Node''' delete('''Node''' root, '''Node''' z) <font color="green">// корень поддерева, удаляемый элемент</font> | ||
| − | '''if''' root == null | + | '''if''' root == ''null'' |
'''return''' root | '''return''' root | ||
'''if''' z.key < root.key | '''if''' z.key < root.key | ||
| Строка 167: | Строка 167: | ||
'''else if''' z.key > root.key | '''else if''' z.key > root.key | ||
root.right = remove(root.right, z) | root.right = remove(root.right, z) | ||
| − | '''else if''' root.left != null '''and''' root.right != null | + | '''else if''' root.left != ''null'' '''and''' root.right != ''null'' |
root.key = minimum(root.right).key | root.key = minimum(root.right).key | ||
root.right = remove(root, root.right) | root.right = remove(root, root.right) | ||
'''else''' | '''else''' | ||
| − | '''if''' root.left != null | + | '''if''' root.left != ''null'' |
root = t.left | root = t.left | ||
'''else''' | '''else''' | ||
| Строка 180: | Строка 180: | ||
* [[Поисковые структуры данных]] | * [[Поисковые структуры данных]] | ||
* [[Рандомизированное бинарное дерево поиска]] | * [[Рандомизированное бинарное дерево поиска]] | ||
| + | * [[Красно-черное дерево]] | ||
==Источники информации== | ==Источники информации== | ||
| Строка 188: | Строка 189: | ||
[[Категория: Деревья поиска]] | [[Категория: Деревья поиска]] | ||
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
| + | [[Категория: Структуры данных]] | ||
Версия 22:13, 24 мая 2015
Бинарное дерево поиска (англ. binary search tree, BST) — структура данных для работы с упорядоченными множествами.
Бинарное дерево поиска обладает следующим свойством: если — узел бинарного дерева с ключом , то все узлы в левом поддереве должны иметь ключи, меньшие , а в правом поддереве большие .
Содержание
Операции в бинарном дереве поиска
Обход дерева поиска
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
- — обход узлов в отсортированном порядке
- — обход узлов в порядке: вершина, левое поддерево, правое поддерево
- — обход узлов в порядке: левое поддерево, правое поддерево, вершина
inorderTraversal(Node x)
if x != null
inorderTraversal(x.left)
print x.key
inorderTraversal(x.right)
Корректность данного алгоритма следует из свойств бинарного дерева поиска.
preorderTraversal(Node x)
if x != null
print x.key
preorderTraversal(x.left)
preorderTraversal(x.right)
postorderTraversal(Node x)
if x != null
postorderTraversal(x.left)
postorderTraversal(x.right)
print x.key
Данные алгоритмы выполняют обход за время , поскольку процедура вызывается ровно два раза для каждого узла дерева.
Поиск элемента
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы , где — высота дерева.
Node search(Node x, key k)
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(Node x)
if x.left == null
return x
return minimum(x.left)
Node maximum(Node x)
if x.right == null
return x
return maximum(x.right)
Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время .
Поиск следующего и предыдущего элемента
Реализация с использованием информации о родителе
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
Node next(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(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
Обе операции выполняются за время .
Реализация без использования информации о родителе
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то начнем поиск от корня. Спускаемся вниз по дереву. Если значение узла больше значения в рассматриваемом в данный момент узле, перейдем в правое поддерево, иначе перейдем в левое поддерево. Аналогично выполняется поиск предыдущего элемента. Рекурсивные реализации обеих функций:
Node next(Node x, Node t) // x - элемент, для которого ищем следующий, t - текущее поддерево
if t != null
Node successor = next(x, t.left)
if successor == null
if t.key > x.key
return t
else
return successor
return next(x, t.right)
return null
Node prev(Node x, Node t) // x - элемент, для которого ищем предыдущий, t - текущее поддерево
if t != null
Node ancestor = prev(x, t.right)
if ancestor == null
if t.key <= x.key
return t
else
return ancestor
return prev(x, t.left)
return null
Обе операции выполняются за время .
Вставка
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
insert(Node x, Node z) // x - корень поддерева, z - вставляемый элемент
if z.key > x.key
if x.right != null
insert(x.right, z)
else
z.parent = x
x.right = z
else
if x.left != null
insert(x.left, z)
else
z.parent = x
x.left = z
Время работы алгоритма — .
Удаление
Нерекурсивная реализация
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на . Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка) и переместить его на место удаляемого узла. Время работы алгоритма — .
| Случай | Иллюстрация |
|---|---|
| Удаление листа | 
|
| Удаление узла с одним дочерним узлом | 
|
| Удаление узла с двумя дочерними узлами | 
|
delete(Node root, Node z) // корень поддерева, удаляемый элемент
Node x, y // x - элемент, который нужно поместить вместо y
if z.left != null and z.right != null // если z имеет двух детей
y = next(z) // y - элемент, следующий за удаляемым, x - null
x = null
if y == y.parent.left
y.parent.left = null
else
y.parent.right = null
z.key = y.key // подвешиваем y вместо z
z.data = y.data
else if z.left != null or z.right != null // eсли z имеет одного ребенка
y = z // y - удаляемый элемент
if y.left != null // x - ребенок y
x = y.left
else
x = y.right
else // если z не имеет детей
y = z // y - удаляемый элемент, x - null
x = null
if x != null // подвешиваем x вместо y
x.parent = y.parent
if y.parent == null
root = x
else
if y == y.parent.left
y.parent.left = x
else
y.parent.right = x
Рекурсивная реализация
При рекурсивном удаления узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма — . Рекурсивная функция, возвращающая дерево с удаленным элементом :
Node delete(Node root, Node z) // корень поддерева, удаляемый элемент
if root == null
return root
if z.key < root.key
root.left = remove(root.left, z)
else if z.key > root.key
root.right = remove(root.right, z)
else if root.left != null and root.right != null
root.key = minimum(root.right).key
root.right = remove(root, root.right)
else
if root.left != null
root = t.left
else
root = t.right
return root
См. также
Источники информации
- Википедия — Двоичное дерево поиска
- Wikipedia — Binary search tree
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
