Двоичные деревья поиска
Роман Акопов
Определение Двоичного Дерева Поиска (Binary Search
Tree, BST)
Двоичным деревом поиска (ДДП) называют дерево, все
вершины которого упорядочены, каждая вершина имеет не более двух потомков
(назовём их левым и правым), и все вершины, кроме корня, имеют родителя.
Вершины, не имеющие потомков, называются листами. Подразумевается, что каждой
вершине соответствует элемент или несколько элементов, имеющие некие ключевые
значения, в дальнейшем именуемые просто ключами. Обычно одной вершине
соответствует один элемент, поэтому данные термины можно без потери смысла
считать синонимами, хотя и надо помнить, что в некоторых реализациях это не
так. В приведённых алгоритмах считается, что одной вершине соответствует только
один элемент. Поэтому мы будем использовать понятия ключа вершины и данных
вершины, подразумевая ключ и данные соответствующего вершине элемента. Мы так
же будем понимать под вставкой вершины добавление вершины с указанным значением
элемента и присвоение указателям на родителя и потомков корректных значений.
Именно ключ используется во всех операциях сравнения элементов. Элемент может
также содержать ассоциированные с ключом данные. На практике в качестве ключа
может использоваться часть данных элемента. Ключ также может храниться как
отдельное значение. ДДП позволяет выполнять следующие основные операции:
Поиск вершины по ключу.
Определение вершин с минимальным и максимальным
значением ключа.
Переход к предыдущей или последующей вершине, в
порядке, определяемом ключами.
Вставка вершины.
Удаление вершины.
Двоичное дерево может быть логически разбито на
уровни. Корень дерева является нулевым уровнем, потомки корня – первым уровнем,
их потомки – вторым, и т.д. Глубина дерева это его максимальный уровень.
Понятие глубины также может быть описано в терминах пути, то есть глубина
дерева есть длина самого длинного пути от корня до листа, если следовать от
родительской вершины до потомка. Каждую вершину дерева можно рассматривать как
корень поддерева, которое определяется данной вершиной и всеми потомками этой
вершины, как прямыми, так и косвенными. Поэтому о дереве можно говорить как о
рекурсивной структуре. Эффективность поиска по дереву напрямую связана с его
сбалансированностью, то есть с максимальной разницей между глубиной левого и
правого поддерева среди всех вершин. Имеется два крайних случая –
сбалансированное бинарное дерево (где каждый уровень имеет полный набор вершин)
и вырожденное дерево, где на каждый уровень приходится по одной вершине.
Вырожденное дерево эквивалентно связанному списку. Время выполнения всех
основных операций пропорционально глубине дерева. Таким образом, скоростные
характеристики поиска в ДДП могут варьироваться от O(log2N) в случае законченного
дерева до O(N) – в случае вырожденного.
ДДП может быть использовано для реализации таких
абстракций, как сортированный список, словарь (набор соответствий
"ключ-значение"), очередь с приоритетами и так далее.
При реализации дерева помимо значения ключа (key) и
данных также хранятся три указателя: на родителя (net), левого (left) и правого
(right) потомков. Если родителя или потомка нет, то указатель хранит нулевое
(NULL, NIL) значение.
Свойство упорядоченности двоичного дерева поиска
Если x – это произвольная вершина в ДДП, а вершина y
находится в левом поддереве вершины x, то y.key = x.key. Из свойства следует, что если y.key == x.key, то вершина
y может находиться как в левом, так и в правом поддереве относительно вершины
x.
Необходимо помнить, что при наличии нескольких вершин
с одинаковыми значениями ключа некоторые алгоритмы не будут работать правильно.
Например, алгоритм поиска будет всегда возвращать указатель только на одну
вершину. Эту проблему можно решить, храня элементы с одинаковыми ключами в
одной и той же вершине в виде списка. В таком случае мы будем хранить в одной
вершине несколько элементов, но данный случай в статье не рассматривается.
Это двоичное дерево поиска:
Рисунок 1.
А это нет:
Рисунок 2.
Способы обхода ДДП
Есть три способа обхода: Прямой (preorder), Поперечный
(inorder), Обратный (postorder).
Прямой обход: сначала обходится данная вершина, левое
поддерево данной вершины, затем правое поддерево данной вершины.
Поперечный обход: сначала обходится левое поддерево
данной вершины, затем данная вершина, затем правое поддерево данной вершины.
Вершины при этом будут следовать в неубывающем (по ключам key) порядке.
Обратный обход: сначала обходится левое поддерево
данной вершины, затем правое, затем данная вершина.
На рисунке 3 порядок обхода вершин указан номерами,
при этом предполагается, что сами вершины расположены так, что образуют ДДП.
Рисунок 3.
Наиболее часто употребляется поперечный обход, так как
во всех других способах обхода следующие друг за другом вершины не связаны
никакими условиями отношения.
Поиск вершины в ДДП
Идея поиска проста. Алгоритм поиска в ДДП по своей
природе рекурсивен. При его описании проще всего использовать понятие
поддерева. Поиск начинается с корня дерева, который принимается за корень
текущего поддерева, и его ключ сравнивается с искомым. Если они равны, то,
очевидно, поиск закончен. Если ключ, который мы ищем, оказался больше текущего,
то, очевидно, что нужная вершина находится в правом поддереве, иначе – в левом.
Далее эта операция повторяется для правого или левого поддерева. В условном
коде это можно описать так:
Рекурсивно:
TreeSearch(node, key)
Begin
// Если вершина равна NIL, то нечего в ней
искать. Так же и возвращаем.
// Это нужно для поиска по не существующим
потомкам
If (node == NIL) Then
Return node;
// Если нашли, то возвращаем указатель на найденную вершину.
If (node.key == key) Then
Return node;
// Если ключ найденной вершины больше того, который мы ищем
If (node.key > key) Then
// То искать в левом поддереве
Return TreeSearch(node.left, key);
Else
// Иначе в правом поддереве
Return
TreeSearch(node.right, key);
End
ПРИМЕЧАНИЕ
В прилагаемом исходном
коде, написанном на паскале-подобном языке, все параметры передаются по значению.
nodeParent, nodeTemp и node – это указатели на вершины, а Tree – само дерево,
имеющее поле root, указатель на корень дерева.
Итеративно:
TreeSearch(node,key)
Begin
// Пока ещё есть вершины среди которых
можно искать
//(мы просматриваем не все, но несколько) и
пока мы не нашли
While (node != NIL) and (node.key != key) Do
Begin
// Если ключ найденногй вершины больше
того который мы ищем
If (node.key > key) Then
node = node.left; // То искать в левом
поддереве
Else
node = node.right; // А иначе в правом
поддереве
End
Return node; // Возвратить найденное
End
Поиск вершины с минимальным и максимальным значением
ключа
Вершины с минимальным и максимальным значением ключа
можно найти, пройдясь по левым (правым) указателям от корня (пока не достигнем
NIL). Возвращаемое значение – это указатель на вершину с минимальным
(максимальным) значением ключа.
TreeMinimum(node)
Begin
While (node.left != NIL) Do // Пока есть левый потомок
Node = node.left; // Перейти к нему
Return node;
End
TreeMaximum(node)
Begin
While (node.right != NIL) Do
// Пока есть правый потомок
node = node.right; // Перейти к нему
Return node;
End
Нахождение следующей и предыдущей вершины в ДДП
Чтобы найти предыдущую и следующую вершину, надо снова
вспомнить свойство упорядоченности. Рассмотрим это на примере функции TreeNext.
Она учитывает два случая. Если правое поддерево не пусто, то вершина из правого
поддерева с минимальным значением ключа и будет следующей. Если же правое
поддерево пусто, тогда мы идём вверх, пока не найдём вершину, являющуюся левым
потомком своего родителя. Этот родитель (если он есть) и будет следующей
вершиной. Возвращаемое значение – это указатель на вершину с следующим
(предыдущим) значеним ключа или NIL, если такой вершины нет.
TreeNext(node)
Begin
// Если правое поддерево не пусто, то
возвратить
// вершину с минимальным значением ключа из
правого поддерева
If (node.right != NIL) Then
Return
TreeMinimum(node.right);
nodeParent = node.nodeParent;
// Перебирать родителей, пока не найдена
вершина,
// являющаяся левым потомком своего
родителя
// или пока не закончатся родители.
While (nodeParent != NIL) and (node ==
nodeParent.right) Do
Begin
node = nodeParent;
nodeParent =
nodeParent.nodeParent;
End
// Возвратить родителя вершины, являющегося
левым потомком своего родителя
Return nodeParent;
End
TreePrevious(node)
Begin
If (node.left != NIL) Then
// Если левое поддерево не пусто, то возвратить
// вершину из левого поддерева с
максимальным значением ключа
Return
TreeMaximum(node.left);
nodeParent = node.nodeParent;
// Перебирать родителей, пока не найдём вершину, являющуюся
// правым потомком своего родителя или пока
не закончатся родители
While (nodeParent != NIL) and (node ==
nodeParent.left) Do
Begin
node = nodeParent;
nodeParent =
nodeParent.nodeParent;
End
// Возвратить родителя вершины являющегося
его правым потомком
Return nodeParent;
End
Добавление вершины
Добавление вершины в ДДП сопряжено с некоторыми
проблемами. После добавления ДДП должно сохранить свойство упорядоченности, а
это значит, что вершину, куда попало добавлять нельзя. Поэтому, прежде чем
вставлять вершину, необходимо подобрать для неё подходящее место, то есть такое
место, после вставки в которое, дерево сохранит своё свойство упорядоченности.
Говоря другими словами, нам нужно место после вершины с наибольшим ключом из
всех меньших данного.
TreeInsert(Tree,node)
Begin
nodeParent = NIL;
nodeTemp = T.root;
// Пока ещё есть вершины которые надо
просмотреть, то
// есть пока мы не добрались до “листочков”
дерева
While (nodeTemp != NIL) Do
Begin
nodeParent = nodeTemp;
// Если ключ вершины, которую мы хотим вставить,
// меньше ключа текущей вершины
If (node.key
nodeTemp = nodeTemp.left; // То он
должен быть в его левом поддереве
Else
nodeTemp = nodeTemp.right; // А иначе в
правом
End
node.nodeParent = nodeParent;
If (nodeParent == NIL) Then //
Если в дереве ещё нет вершин
Tree.root = node; // То добавить первую
Else
Begin
// Если ключ вершины, которую мы хотим
вставить,
// меньше ключа вершины, потомком которой
должна стать
// вставляемая вершина
If (node.key
nodeParent.left = node; // То добавить в дерево как
левого потомка
Else
nodeParent.right = node; // Иначе
добавить в дерево как правого потомка
End
End
Удаление вершины
Проблемы возникают и при удалении. Нам необходимо
сохранить свойство упорядоченности ДДП. При удалении возможны три случая: у
удаляемой вершины нет потомков, у удаляемой вершины есть один потомок и у
удаляемой вершины два потомка. Если потомков нет, то вершину можно просто
удалить. Если потомок один, то удаляемую вершину можно “вырезать”, указав её
родителю в качестве потомка единственного имеющегося потомка удаляемой вершины.
Если же потомков два, требуются дополнительные действия. Нужно найти следующую
за удаляемой (по порядку ключей) вершину, скопировать её содержимое (ключ и
данные) в удаляемую вершину (она теперь никуда не удаляется физически, хотя
логически исчезает) и удалить найденную вершину (у неё не будет левого
потомка). Сначала функция TreeDelete ищет вершину, которую надо удалить, затем
переменной nodeTemp присваивается указатель на существующего потомка удаляемой
вершины (или NIL, если потомков нет). Далее вершина удаляется из дерева, при
этом отдельно рассматриваются случаи: когда потомков нет и когда удаляемая
вершина – это корень дерева. Возвращаемое значение – это указатель на удалённую
вершину. На неё уже нет никаких ссылок в самом дереве, но она всё ещё занимает
память. Момент её реального удаления зависит от используемых методов
распределения памяти.
TreeDelete(Tree,node)
Begin
// Если потомков не более одного (случаи 1
и 2)
If (node.left == NIL) or (node.right == NIL)
Then
del = node; // физически удаляем текущую вершину
Else
del = TreeNext(node); // Иначе следующую
If (del.left != NIL) Then // Пытаемся найти хоть одного потомка
nodeTemp = del.left;
Else
nodeTemp = del.right;
// Если есть, родителем потомка делаем родителя
// удаляемой вершины (случай 2)
If (nodeTemp != NIL) Then
nodeTemp.nodeParent =
del.nodeParent;
// Если удаляем корень дерева, надо указать новый корень дерева
If (del.nodeParent == NIL) Then
Tree.root = nodeTemp;
Else
Begin
// Указываем родителю удаляемой вершины
качестве потомка
// потомок удаляемой вершины
If (del.nodeParent.left ==
del) Then
del.nodeParent.left =
nodeTemp;
Else
del.nodeParent.right =
nodeTemp;
End
If (del != node) Then // Если случай 3
Begin
node.key = del.key; // Скопировать ключ
{ копирование дополнительных данных }
End
Return del;
End
NIL, NULL и маленькие хитрости
Нередко алгоритмы, просто выглядящие на бумаге,
становятся нагромождением сплошных конструкций if в реальной программе. Почему?
Ответ очевиден: многие алгоритмы для работы с деревьями предполагают, что
(NIL).parent == (NIL).left == (NIL).right == NIL. Вроде всё ясно и даже
логично, но ведь во многих языках программирования NIL/NULL – это ноль. А
обращение по нулевому адресу памяти чревато нехорошими вещами. Что же делать?
Ведь мало того, что все эти if тормозят программу, в них легко запутаться!
Решение просто: мы не будем использовать NIL! Действительно, алгоритмам
совершенно всё равно, какое численное значение имеет NIL, главное, чтобы адрес
любой реальной вершины в дереве не был ему равен. Поэтому вместо NIL мы будем
использовать адрес переменной, проинициализированной особым образом. Я покажу
это на языке С++, но думаю, этот пример можно будет перевести и на другие
языки, хотя там, скорее всего, нет шаблонов, и придется пожертвовать
типобезопасностью.
template class CTreeBase
{
protected:
CTree * lpCParent;
CTree * lpCLeft;
CTree * lpCRight;
public:
CTreeBase(CTreeBase *
lpCParentInit, CTreeBase * lpCLeftInit,
CTreeBase * lpCRightInit)
{
lpCParent = (CTree
*)lpCParentInit;
lpCLeft = (CTree *)lpCLeftInit;
lpCRight = (CTree *)lpCRightInit;
}
};
/////////////////////////////////////
class CTree : public CTreeBase
{
private:
int data;
protected:
static CTreeBase
treeNil;
};
////////////////////////////////////////////////////////////
CTreeBase CTree::treeNil(&treeNil, &treeNil,
&treeNil);
Теперь везде в классе CTree можно использовать
переменную treeNil. Преимущества очевидны. Потратив каких-то двенадцать (3 *
sizeof(CTree *)) байт памяти, мы упростили разработку и ускорили выполнение
программы.
Основная проблема использования ДДП
Основной проблемой использования ДДП является то, что
методы вставки и удаления вершин, гарантируя сохранение свойства
упорядоченности, совершенно не способствуют оптимизации основных операций над
ДДП. Например, если вставить в ДДП последовательность возрастающих или
убывающих чисел, оно превратится, по сути, в двусвязный список, а основные операции
будут занимать время, пропорциональное количеству вершин, а не его логарифму.
Таким образом, для получения производительности
порядка O(log2N) нужно, чтобы дерево имело как можно более высокую
сбалансированность (то есть имело возможно меньшую высоту). Обычно выделяются
несколько типов сбалансированности. Полная сбалансированность, это когда для
каждой вершины дерева количества вершин в левом и правом поддеревьях
различаются не более чем на 1. К сожалению, такой сбалансированности трудно
добиться на практике. Поэтому на практике используются менее жесткие виды
сбалансированности. Например, русскими математиками Г. М. Адельсон-Вельским и
Е.М.Ландисом были разработаны принципы АВЛ деревьев. В АВЛ деревьях для каждой
вершины дерева глубины обоих поддеревьев различаются не более чем на 1. Еще
одним “продвинутым” видом деревьев является так называемые красно-чёрные
деревья. АВЛ деревья обеспечивают более высокую сбалансированность дерева, но
затраты на их поддержание выше. Поскольку на практике разница в сбалансированности
между этими двумя видами деревьев не высока, чаще используются красно-чёрные
деревья.
Красно-чёрные деревья (Red-Black Tree, RB-Tree)
Итак, одним из способов решения основной проблемы
использования ДДП являются красно-чёрные деревья. Красно-чёрные (название
исторически связано с игральными картами, поскольку из них легко делать простые
модели) деревья (КЧД) – это ДДП, каждая вершина которых хранит ещё одно
дополнительное логическое поле (color), обозначающее цвет: красный или чёрный.
Фактически, в КЧД гарантируется, что уровни любых двух листьев отличаются не
более, чем в два раза. Этого условия оказывается достаточно, чтобы обеспечить
скоростные характеристики поиска, близкие к O(log2N). При вставке/замене
производятся дополнительные действия по балансировке дерева, которые не могут
не замедлить работу с деревом. При описании алгоритмов мы будем считать, что
NIL – это указатель на фиктивную вершину, и операции (NIL).left, (NIL).right,
(NIL).color имеют смысл. Мы также будем полагать, что каждая вершина имеет двух
потомков, и лишь NIL не имеет потомков. Таким образом, каждая вершина
становится внутренней (имеющей потомков, пусть и фиктивных), а листьями будут
лишь фиктивные вершины NIL.
Свойства КЧД
Каждая вершина может быть либо красной, либо чёрной.
Бесцветных вершин, или вершин другого цвета быть не может.
Каждый лист (NIL) имеет чёрный цвет.
Если вершина красная, то оба её потомка – чёрные.
Все пути от корня к листьям содержат одинаковое число
чёрных вершин.
Пример КЧД с учётом наших положений приведен на
рисунке 4. Учтите, что вершина 9 могла быть и красной, но в дальнейшем мы будем
рассматривать только те деревья, у которых корень чёрный. Мы это сделаем для
того, чтобы потомки корня могли иметь любой цвет.
Рисунок 4.
Вращения
Операции вставки и удаления вершин в КЧД могут
нарушать свойства КЧД. Чтобы восстановить эти свойства, надо будет
перекрашивать некоторые вершины и менять структуру дерева. Для изменения
структуры используются операции, называемые вращением. Возвращая КЧД его
свойства, вращения так же восстанавливают сбалансированность дерева. Вращения
бывают левые и правые, их суть показана на рисунке 5.
Рисунок 5.
Как видно, вращения, перемещая вершины, не нарушают
свойства упорядоченности.
В процедуре RBTLeftRotate предполагается, что
node.right != NIL. В процедуре RBTRightRotate предполагается, что node.left !=
NIL.
RBTLeftRotate(Tree,node)
Begin
nodeTemp = node.right;
node.right = nodeTemp.left;
If (nodeTemp.left != NIL) Then
nodeTemp.left.nodeParent =
node;
nodeTemp.nodeParent =
node.nodeParent;
If (node.nodeParent == NIL)
Then
Tree.root = nodeTemp;
Else
Begin
If (node ==
node.nodeParent.left) Then
node.nodeParent.left =
nodeTemp;
Else
node.nodeParent.right =
nodeTemp;
End
nodeTemp.left = node;
node.nodeParent = nodeTemp;
End
RBTRightRotate(Tree,node)
Begin
nodeTemp = node.left;
node.left = nodeTemp.right;
If (nodeTemp.right != NIL)
Then
nodeTemp.right.nodeParent =
node;
nodeTemp.nodeParent =
node.nodeParent;
If (node.nodeParent == NIL)
Then
Tree.root = nodeTemp;
Else
Begin
If (node ==
node.nodeParent.right) Then
node.nodeParent.right =
nodeTemp;
Else
node.nodeParent.left =
nodeTemp;
End
nodeTemp.right = node;
node.nodeParent = nodeTemp;
End
Добавление вершины в КЧД
Чтобы добавить вершину в КЧД, мы применяем процедуру
TreeInsert для ДДП, красим вершину в красный цвет, а затем восстанавливаем
свойства КЧД. Для этого мы перекрашиваем некоторые вершины и производим
вращения.
1 RBTInsert(Tree,node)
2 Begin
3 TreeInsert(Tree,node);
4 node.color = RED;
5 While (node != Tree.root) and
(node.nodeParent.color == RED) Do
6 Begin
7 If (node.nodeParent == node.nodeParent.nodeParent.left)
Then
8 Begin
9 nodeTemp =
node.nodeParent.nodeParent.right;
10 If (nodeTemp.color ==
RED) Then
11 Begin
12 node.nodeParent.color
= BLACK;
13 nodeTemp.color =
BLACK;
14
node.nodeParent.nodeParent.color = RED;
15 node =
node.nodeParent.nodeParent;
16 End
17 Else
18 Begin
19 If (node ==
node.nodeParent.right) Then
20 Begin
21 node =
node.nodeParent;
22 RBTLeftRorate(Tree,node);
23 End
24 node.nodeParent.color
= BLACK;
25
node.nodeParent.nodeParent.color = RED;
26
RBTRightRotate(Tree,node.nodeParent.nodeParent);
27 End
28 End
29 Else
30 Begin
31 nodeTemp =
node.nodeParent.nodeParent.left;
32 If (nodeTemp.color ==
RED) Then
33 Begin
34 node.nodeParent.color
= BLACK;
35 nodeTemp.color =
BLACK;
36
node.nodeParent.nodeParent.color = RED;
37 node =
node.nodeParent.nodeParent;
38 End
39 Else
40 Begin
41 If (node ==
node.nodeParent.left) Then
42 Begin
43 node =
node.nodeParent;
44
RBTRightRorate(Tree,node);
45 End
46 node.nodeParent.color = BLACK;
47
node.nodeParent.nodeParent.color = RED;
48
RBTLeftRotate(Tree,node.nodeParent.nodeParent);
49 End
50 End
51 End
52 Tree.root.color = BLACK;
53 End
Функция RBTInsert не так сложна, как кажется на первый
взгляд. Рассмотрим её подробнее. После строк 3-4 выполняются все свойства КЧД,
кроме, возможно, одного: у новой красной вершины может быть красный родитель.
Такая ситуация (красная вершина имеет красного родителя) может сохраниться
после любого числа итераций цикла. Внутри цикла рассматриваются 6 различных
случаев, но три из них (строки 8-28) симметричны трём другим (строки 30-50),
различие лишь в том, является ли родитель вершины node правым или левым
потомком своего родителя (случаи разделяются в строке 7). Поэтому мы рассмотрим
подробно только первые три случая (строки 8-28). Предположим, что во всех
рассматриваемых КЧД корень чёрный, и будем поддерживать это свойство (строка
52). Поэтому в строке 5 node.nodeParent (красного цвета) не может быть корнем,
и node.nodeParent.nodeParent != NIL. Операции внутри цикла начинаются с
нахождения nodeTemp, “дяди” node, то есть вершины, имеющей того же родителя,
что и node.nodeParent. Если nodeTemp – красная вершина, то имеет место случай
1, если черная, то 2 или 3. Во всех случаях вершина node.nodeParent.nodeParent
– чёрная, так как пара node, node.nodeParent была единственным нарушением
свойств КЧД.
Случай 1 (строки 12-15 и 34-37) показан на рисунке 6.
Является ли вершина node правым или левым потомком своего родителя, значения не
имеет.
Рисунок 6.
Обе вершины (node и nodeTemp) – красные, а вершина
node.nodeParent.nodeParent – чёрная. Перекрасим node.nodeParent и nodeTemp в
чёрный цвет, а node.nodeParent.nodeParent – в красный. При этом число чёрных
вершин на любом пути от корня к листьям остаётся прежним. Нарушение свойств КЧД
возможно лишь в одном месте: вершина node.nodeParent.nodeParent может иметь
красного родителя, поэтому надо продолжить выполнение цикла, присвоив node
значение node.nodeParent.nodeParent.
В случаях 2 и 3 вершина nodeTemp – чёрная. Различаются
случаи, когда вершина node является правым или левым потомком своего родителя.
Если правым, то это случай 2 (строки 20-23 и 41-45). В этом случае производится
левое вращение, которое сводит случай 2 к случаю 3, когда node является левым
потомком своего родителя. Так как node и node.nodeParent – красные, после
вращения количество чёрных вершин на путях от корня к листьям остается прежним.
Рисунок 7.
Осталось рассмотреть случай 3: красная вершина node является
левым потомком красной вершины node.nodeParent, которая, в свою очередь,
является левым потомком node.nodeParent.nodeParent, правым потомком которой
является nodeTemp. В этом случае достаточно произвести правое вращение и
перекрасить две вершины. Цикл окончится, так как вершина node.nodeParent будет
после этого чёрной.
Удаление вершины из КЧД
Удаление вершины немного сложнее добавления. Мы будем
считать, что (NIL).color == BLACK, и будем считать операцию взятия цвета у
указателя, равного NIL, допустимой операцией. Также мы будем считать допустимым
присваивание (NIL).nodeParent, и будем считать данное присваивание имеющим
результат. То есть при взятии значения (NIL).nodeParent мы получим ранее
записанное значение. Функция RBTDelete подобна TreeDelete, но, удалив вершину,
она вызывает процедуру RTBDeleteFixUp для восстановления свойств КЧД.
RBTDelete(Tree,node)
Begin
If (node.left == NIL) or
(node.right == NIL) Then
nodeParent = node;
Else
nodeParent = TreeNext(node);
If (nodeParent.left != NIL)
Then
nodeTemp = nodeParent.left;
Else
nodeTemp = nodeParent.right;
nodeTemp.nodeParent =
nodeParent.nodeParent;
If (nodeTemp.nodeParent ==
NIL) Then
Tree.root = nodeTemp;
Else
Begin
If
(nodeParent.nodeParent.left == nodeParent) Then
nodeParent.nodeParent.left
= nodeTemp;
Else
nodeParent.nodeParent.right = nodeTemp;
End
If (nodeParent != node) Then
Begin
node.key = nodeParent.key;
node.color = nodeParent.color;
{ копирование дополнительных данных }
End
If (nodeParent.color == BLACK)
Then
RBTDeleteFixUp(Tree,nodeTemp);
Return nodeParent;
End
Рассмотрим, как процедура RBTDeleteFixUp
восстанавливает свойства КЧД. Очевидно, что если удалили красную вершину, то,
поскольку оба ее потомка чёрные, красная вершина не станет родителем красного
потомка. Если же удалили чёрную вершину, то как минимум на одном из путей от
корня к листьям количество чёрных вершин уменьшилось. К тому же красная вершина
могла стать потомком красного родителя.
1 RTBDeleteFixUp(Tree,node)
2 Begin
3 While (node != Tree.root) and (node.color
== BLACK) Do
4 Begin
5 If (node == node.nodeParent.left)
6 Begin
7 nodeTemp = node.nodeParent.right;
8 If (nodeTemp.color == RED) Then
9 Begin
10 nodeTemp.color =
BLACK;
11
nodeTemp.nodeParent.color = RED;
12
RBTLeftRotate(Tree,node.nodeParent);
13 nodeTemp =
node.nodeParent.right;
14 End
15 If (nodeTemp.left.color
== BLACK) and (nodeTemp.right.color == BLACK) Then
16 Begin
17 nodeTemp.color = RED;
18 nodeTemp =
nodeTemp.nodeParent;
19 End
20 Else
21 Begin
22 If
(nodeTemp.right.color == BLACK) Then
23 Begin
24 nodeTemp.left.color
= BLACK;
25 nodeTemp.color =
RED;
26
RBTRightRotate(Tree,nodeTemp)
27 nodeTemp =
node.nodeParent.right;
28 End
29 nodeTemp.color =
node.nodeParent.color;
30 node.color.nodeParent
= BLACK;
31 nodeTemp.right.color
= BLACK;
32
RBTLeftRotate(Tree,node.nodeParent);
33 node = Tree.root;
34 End
35 End
36 Else
37 Begin
38 nodeTemp =
node.nodeParent.left;
39 If (nodeTemp.color == RED) Then
40 Begin
41 nodeTemp.color =
BLACK;
42
nodeTemp.nodeParent.color = RED;
43
RBTRightRotate(Tree,node.nodeParent);
44 nodeTemp =
node.nodeParent.left;
45 End
46 If (nodeTemp.right.color
== BLACK) and (nodeTemp.left.color == BLACK) Then
47 Begin
48 nodeTemp.color = RED;
49 nodeTemp =
nodeTemp.nodeParent;
50 End
51 Else
52 Begin
53 If
(nodeTemp.left.color == BLACK) Then
54 Begin
55
nodeTemp.right.color = BLACK;
56 nodeTemp.color =
RED;
57
RBTLeftRotate(Tree,nodeTemp)
58 nodeTemp =
node.nodeParent.left;
59 End
60 nodeTemp.color =
node.nodeParent.color;
61 node.color.nodeParent
= BLACK;
62 nodeTemp.left.color =
BLACK;
63
RBTRightRotate(Tree,node.nodeParent);
64 node = Tree.root;
65 End
66 End
67 End
68 node.color = BLACK;
69 End
Процедура RBTDeleteFixUp применяется к дереву, которое
обладает свойствами КЧД, если учесть дополнительную единицу черноты в вершине
node (она теперь дважды чёрная, это чисто логическое понятие, и оно нигде
фактически не сохраняется и логического типа для хранения цвета вам всегда будет
достаточно) и превращает его в настоящее КЧД.
Что такое дважды чёрная вершина? Это определение может
запутать. Формально вершина называется дважды чёрной, дабы отразить тот факт,
что при подсчёте чёрных вершин на пути от корня до листа эта вершина считается
за две черных. Если чёрная вершина была удалена, её черноту так просто
выкидывать нельзя. Она на счету. Поэтому временно черноту удалённой вершины
передали вершине node. В задачу процедуры RBTDeleteFixUp входит распределение
этой лишней черноты. Они или будет передана красной вершине (и та станет
чёрной) или после перестановок других чёрных вершин (дабы изменить их
количество на пути от корня к листьям) будет просто выкинута.
В цикле (строки 3-67) дерево изменяется, и значение
переменной node тоже изменяется, но сформулированное свойство остаётся верным.
Цикл завершается, если:
node указывает на красную вершину, тогда мы красим её
в чёрный цвет (строка 68).
node указывает на корень дерева, тогда лишняя чернота
может быть просто удалена.
Могло оказаться, что внутри тела цикла удается
выполнить несколько вращений и перекрасить несколько вершин, так что дважды
чёрная вершина исчезает. В этом случае присваивание node = Tree.root (строки 33
и 64) позволяет выйти из цикла.
Внутри цикла node указывает на дважды чёрную вершину,
а nodeTemp – на её брата (другую вершину с тем же родителем). Поскольку вершина
node дважды чёрная, nodeTemp не может быть NIL, поскольку в этом случае вдоль
одного пути от node.nodeParent было бы больше чёрных вершин, чем вдоль другого.
Четыре возможных случая показаны на рисунке ниже. Зелёным и синим, помечены
вершины, цвет которых не играет роли, то есть может быть как черным, так и
красным, но сохраняется в процессе преобразований.
Рисунок 8
Убедитесь, что преобразования не нарушают свойство 4
КЧД (помните, что вершина node считается за две чёрные, и что в поддеревьях a -
f изначально не равное количество чёрных вершин).
Случай 1 (строки 9-14 и 40-45) имеет место, когда
вершина nodeTemp красная (в этом случае node.nodeParent чёрная). Так как оба
потомка вершины nodeTemp чёрные мы можем поменять цвета nodeTemp и
node.nodeParent и произвести левое вращение вокруг node.nodeParent не нарушая
свойств КЧД. Вершина node остается дважды чёрной, а её новый брат – чёрным, так
что мы свели дело к одному из случаев 2-4.
Случай 2 (строки 16-19 и 47-50). Вершина nodeTemp –
чёрная, и оба её потомка тоже чёрные. В этом случае мы можем снять лишнюю
чёрноту с node (теперь она единожды чёрная), перекрасить nodeTemp, сделав ёё
красной (оба её потомка чёрные, так что это допустимо) и добавить черноту
родителю node. Заметим, что если мы попали в случай 2 из случая 1, то вершина
node.nodeParent – красная. Сделав её чёрной (добавление чёрного к красной
вершине делает её чёрной), мы завершим цикл.
Случай 3 (строки 23 – 28 и 53 - 59) Вершина nodeTemp
чёрная, её левый потомок красный, а правый чёрный. Мы можем поменять цвета
nodeTemp и её левого потомка и потом применить правое вращение так, что
свойства КЧД будут сохранены. Новым братом node будет теперь чёрная вершина с
красным правым потомком, и случай 3 сводится к случаю четыре.
Случай 4 (строки 29 – 33 и 60 - 64) Вершина nodeTemp
чёрная, правый потомок красный. Меняя некоторые цвета (не все из них нам
известны, но это нам не мешает) и, производя левое вращение вокруг
node.nodeParent, мы можем удалить лишнюю черноту у node, не нарушая свойств
КЧД. присваивание node = Tree.root выводит нас из цикла.
Сравнительные характеристики скорости работы различных
структур данных
Чтобы всё сказанное до этого не казалось пустой
болтовнёй, я в качестве заключения приведу сравнительные характеристики
скорости работы различных структур данных (деревьев и массивов). Для измерения
времени была использована функция WinAPI QueryPerfomanceCounter. Время
пересчитано в микросекунды. В скобках приведена конечная глубина дерева.
Тестирование проводилось на процессоре Intel Celeron Tualatin 1000MHz с 384Мб оперативной
памяти. В качестве ключа использовалось число типа int (32-х битное целое со
знаком), а в качестве данных число типа float (4-х байтное вещественное).
Количество элементов
ДДП
КЧД
Постоянно сортированный
массив
Несортированный массив
Массив с постсортировкой
1000
4943
(1000)
535
(17)
193
32
73
2000
20571
(2000)
1127
(19)
402
89
152
3000
65819
(3000)
1856
(20)
621
98
305
4000
82321
(4000)
2601
(21)
862
189
327
5000
126941
(5000)
3328
(22)
1153
192
461
6000
183554
(6000)
4184
(22)
1391
363
652
7000
255561
(7000)
4880
(23)
1641
452
789
8000
501360
(8000)
5479
(23)
1905
567
874
9000
1113230
(9000)
6253
(24)
2154
590
1059
10000
1871090
(10000)
7174
(24)
2419
662
1180
Таблица 1. Добавление элемента (возрастающие ключи)
Количество элементов
ДДП
КЧД
Постоянно
сортированный массив
Несортированный массив
Массив с постсортировкой
1000
4243
108
136
1354
134
2000
19295
250
289
5401
286
3000
71271
391
448
25373
441
4000
79819
560
615
23861
607
5000
124468
759
787
38862
776
6000
180029
956
954
55303
941
7000
246745
1199
1165
75570
1111
8000
487187
1412
1307
98729
1330
9000
1062128
1906
1494
134470
1474
10000
1807235
2068
1719
154774
1688
Таблица 2. Поиск элемента (возрастающие ключи).
Количество элементов
ДДП
КЧД
Постоянно сортированный
массив
Несортированный массив
Массив с постсортировкой
1000
308
419
2077
2047
2080
2000
639
876
13422
8046
8179
3000
1001
1372
25092
30902
18407
4000
1380
1831
32572
32473
32651
5000
1680
2286
50846
51001
50962
6000
2105
2891
73321
73114
73202
7000
2569
3514
99578
100059
99801
8000
3025
4384
129833
129897
130054
9000
3484
5033
164846
194361
164264
10000
4050
5690
203207
202979
202738
Таблица 3. Удаление элемента по ключу (возрастающие
ключи).
Количество элементов
ДДП
КЧД
Постоянно сортированный
массив
Несортированный массив
Массив с постсортировкой
1000
547
(25)
548
(13)
1800
34
362
2000
1133
(25)
1171
(14)
5534
70
734
3000
1723
(28)
1905
(14)
12065
150
1174
4000
2891
(28)
2985
(15)
20867
223
1626
5000
3604
(28)
4024
(15)
32927
248
1962
6000
4336
(29)
4970
(15)
44720
373
2537
7000
5196
(29)
5794
(16)
60723
443
2977
8000
6051
(30)
6972
(16)
77482
511
3485
9000
6994
(30)
7519
(16)
104219
590
3821
10000
9544
(31)
10303
(16)
118760
584
4408
Таблица 4. Добавление элемента (случайные ключи)
Количество элементов
ДДП
КЧД
Постоянно сортированный
массив
Несортированный массив
Массив с постсортировкой
1000
181
136
159
1354
155
2000
406
307
347
5412
339
3000
653
494
551
12927
538
4000
925
702
765
23936
747
5000
1223
949
1024
37861
962
6000
1532
1142
1216
55124
1185
7000
1893
1494
1453
75628
1403
8000
2477
1833
1679
98802
1631
9000
2943
2390
1994
125570
1858
10000
3395
2937
2228
154791
2108
Таблица 5. Поиск элемента (случайные ключи)
Количество элементов
ДДП
КЧД
Постоянно сортированный
массив
Несортированный массив
Массив с постсортировкой
1000
469
517
1149
2014
1195
2000
995
1079
4381
8054
4387
3000
1557
1756
9673
18191
9639
4000
2272
2424
17071
32451
17105
5000
3070
3019
27380
50665
26954
6000
3528
3618
39294
72996
39227
7000
4322
4542
53255
99402
53309
8000
5299
5531
71406
129964
70766
9000
6180
6553
89583
164943
89935
10000
7527
7797
112190
202993
111439
Таблица 6. Удаление элемента по ключу (случайные
ключи)
Постоянно сортированный массив – это массив, в который
элементы вставляются так, что бы он сохранял свойство упорядоченности. Массив с
постсортировкой – это массив, в который сначала вставляются все элементы, а
потом он сортируется алгоритмом быстрой сортировки. Данные таблицы, безусловно,
не являются истиной в последней инстанции, но позволят вам прикинуть, какая из
структур данных будет наиболее производительна в вашей программе, учитывая
предполагаемую вероятность операций вставки, удаления и поиска. Так, например,
массив с постсортировкой является весьма привлекательным по производительности,
но совершенно не подходит для комплексных работ, так как предполагает
фиксированный порядок действий – сначала только добавление элементов, а после
использование полученной информации. Другие структуры данных лишены этого
недостатка. Для большого числа (порядка 10 000) случайных элементов время
поиска в ДДП и КЧД становится практически одинаковым. Как следствие, можно
реализовать более простые алгоритмы, исходя из некоторых свойств входных
данных. С другой стороны, в крайнем случае (возрастающие элементы) ДДП отстают
от КЧД на несколько порядков. Постоянно сортированный массив является абсолютным
победителем по скорости, но не имеет естественной поддержки отношений
родитель-ребёнок. Если они вам нужны, придётся реализовывать их поддержку
самостоятельно. Также надо всегда помнить, что при количестве элементов порядка
тысячи, асимптотические показатели скорости ещё не вполне вступили в силу и
теоретически более быстрые структуры данных на практике могут оказаться более
медленными. Так, например, скорость поиска в КЧД и массиве с пресортировкой до
5000-7000 практически одинакова. Так же надо заметить, что тестирование
производилось на объектах относительно малого размера (8 байт), сравнимого с
размером указателя (4 байта). Все виды массивов сортированных подразумевают
весьма интенсивное копирование элементов, в то время как деревья работают с
указателями. При размере элемента, на порядки превышающем размеры указателя,
акценты сместятся весьма значительно. Например, ниже приведены результаты
испытания с ключом типа int (32-x битное целое) и битовыми данными размером в
256 байт.
Количество элементов
ДДП
КЧД
Постоянно сортированный
массив
Не сортированный массив
Массив с постсортировкой
1000
5868
(1000)
1663
(17)
1430
1154
1035
2000
140888
(2000)
3694
(19)
3476
2460
2808
3000
368748
(3000)
5815
(20)
5372
3848
4382
4000
721328
(4000)
7271
(21)
7274
5175
6035
5000
1208373
(5000)
9349
(22)
9247
6670
7619
6000
1752135
(6000)
11395
(22)
11046
7778
9168
7000
2501167
(7000)
13503
(23)
13327
9378
10764
8000
3334948
(8000)
15753
(23)
18222
12560
15267
9000
4266560
(9000)
21600
(24)
20564
15391
17430
10000
5421499
(10000)
24105
(24)
24064
17152
19341
Таблица 7. Добавление элемента (возрастающие ключи)
Количество элементов
ДДП
КЧД
Постоянно сортированный массив
Не сортированный массив
Массив с постсортировкой
1000
4289
132
242
1621
230
2000
134074
303
605
6903
530
3000
359985
457
961
24268
806
4000
706129
787
1336
27610
1121
5000
1183405
959
1736
44660
1516
6000
1730699
1116
2138
69068
1841
7000
2462759
1344
2494
103158
2251
8000
3293519
1565
2871
159274
2617
9000
4215750
1840
3284
278697
2923
10000
5361524
2060
3698
513268
3303
Таблица 8. Поиск элемента (возрастающие ключи)
Количество элементов
ДДП
КЧД
Постоянно сортированный
массив
Не сортированный массив
Массив с постсортировкой
1000
502
583
115640
131837
186703
2000
1181
1152
1604342
1574484
1592896
3000
1602
1580
4616940
4653355
4604626
4000
2075
2537
8966113
8999484
8978279
5000
2689
3007
14848795
14851393
14822206
6000
3574
3836
21572736
21473162
21676597
7000
4129
4432
30384061
29938188
30409709
8000
4898
5424
39013182
39342862
39341616
9000
5086
6368
50197296
49946077
50320092
10000
6279
6372
63020912
62049584
62564125
Таблица 9. Удаление элемента по ключу (возрастающие
ключи)
Количество элементов
ДДП
КЧД
Постоянно сортированный
массив
Не сортированный массив
Массив с постсортировкой
1000
1903
(24)
2072
(12)
57991
1418
5448
2000
4532
(25)
4739
(14)
479463
3107
13907
3000
7747
(26)
7819
(15)
1727433
4992
22440
4000
10348
(29)
10664
(15)
3616654
6733
33905
5000
13064
(29)
13652
(16)
6141684
8314
43768
6000
16530
(31)
16713
(16)
9214638
10191
53619
7000
19305
(31)
19642
(16)
12981887
11904
61301
8000
23140
(32)
23329
(16)
17388765
13785
75968
9000
26051
(32)
26378
(16)
21935279
15335
92007
10000
29450
(32)
29448
(16)
27053495
17075
90155
Таблица 10. Добавление элемента (случайные ключи)
Количество элементов
ДДП
КЧД
Постоянно сортированный
массив
Не сортированный массив
Массив с постсортировкой
1000
185
150
266
1613
274
2000
695
359
719
6974
724
3000
1044
586
1193
15561
1245
4000
2186
823
1694
27675
1703
5000
2701
1106
2234
44905
2314
6000
3898
1496
2874
71549
2871
7000
4883
1889
3464
109554
3371
8000
4186
2183
4060
165605
4077
9000
6760
2771
4696
281860
4622
10000
7291
3201
5372
514893
5384
Таблица 11. Поиск элемента (случайные ключи)
Количество элементов
ДДП
КЧД
Постоянно сортированный
массив
Не сортированный массив
Массив с постсортировкой
1000
1235
1115
54929
111088
62794
2000
3042
2978
557875
1596298
558580
3000
4641
4703
1837401
4730623
1841029
4000
7531
6494
3830510
9008129
3833983
5000
9497
8788
6675616
14599142
6626964
6000
12018
10922
10270460
21832592
10315160
7000
14605
14376
14808484
29779691
14618091
8000
15876
16070
19927348
39932636
19946118
9000
20043
19079
25347571
49928153
25384886
10000
22117
21860
32049086
61766884
32072537
Таблица 12. Удаление элемента по ключу (случайные
ключи)
Хорошо видно, что при увеличенном размере элемента
деревья догоняют, а то и значительно обгоняют массивы. Таким образом, очевидно,
что выбор структуры данных сильно зависит от предполагаемого количества
элементов и их размера. Напоследок хотелось бы сказать, что правильный выбор
структуры данных является одним из основных моментов, определяющих
производительность программы. Поэтому подходить к выбору надо осторожно,
продумав все возможные - как наиболее вероятные, так и наихудшие случаи.
Список литературы
Для подготовки данной работы были использованы
материалы с сайта http://www.rsdn.ru/