Двоичные деревья поиска

Роман Акопов

Определение Двоичного Дерева Поиска (Binary Search Tree, BST)

Двоичным деревом поиска (ДДП) называют дерево, все вершины которого упорядочены, каждая вершина имеет не более двух потомков (назовём их левым и правым), и все вершины, кроме корня, имеют родителя. Вершины, не имеющие потомков, называются листами. Подразумевается, что каждой вершине соответствует элемент или несколько элементов, имеющие некие ключевые значения, в дальнейшем именуемые просто ключами. Обычно одной вершине соответствует один элемент, поэтому данные термины можно без потери смысла считать синонимами, хотя и надо помнить, что в некоторых реализациях это не так. В приведённых алгоритмах считается, что одной вершине соответствует только один элемент. Поэтому мы будем использовать понятия ключа вершины и данных вершины, подразумевая ключ и данные соответствующего вершине элемента. Мы так же будем понимать под вставкой вершины добавление вершины с указанным значением элемента и присвоение указателям на родителя и потомков корректных значений. Именно ключ используется во всех операциях сравнения элементов. Элемент может также содержать ассоциированные с ключом данные. На практике в качестве ключа может использоваться часть данных элемента. Ключ также может храниться как отдельное значение. ДДП позволяет выполнять следующие основные операции:

Поиск вершины по ключу.

Определение вершин с минимальным и максимальным значением ключа.

Переход к предыдущей или последующей вершине, в порядке, определяемом ключами.

Вставка вершины.

Удаление вершины.

Двоичное дерево может быть логически разбито на уровни. Корень дерева является нулевым уровнем, потомки корня – первым уровнем, их потомки – вторым, и т.д. Глубина дерева это его максимальный уровень. Понятие глубины также может быть описано в терминах пути, то есть глубина дерева есть длина самого длинного пути от корня до листа, если следовать от родительской вершины до потомка. Каждую вершину дерева можно рассматривать как корень поддерева, которое определяется данной вершиной и всеми потомками этой вершины, как прямыми, так и косвенными. Поэтому о дереве можно говорить как о рекурсивной структуре. Эффективность поиска по дереву напрямую связана с его сбалансированностью, то есть с максимальной разницей между глубиной левого и правого поддерева среди всех вершин. Имеется два крайних случая – сбалансированное бинарное дерево (где каждый уровень имеет полный набор вершин) и вырожденное дерево, где на каждый уровень приходится по одной вершине. Вырожденное дерево эквивалентно связанному списку. Время выполнения всех основных операций пропорционально глубине дерева. Таким образом, скоростные характеристики поиска в ДДП могут варьироваться от O(log2N) в случае законченного дерева до O(N) – в случае вырожденного.

ДДП может быть использовано для реализации таких абстракций, как сортированный список, словарь (набор соответствий "ключ-значение"), очередь с приоритетами и так далее.

При реализации дерева помимо значения ключа (key) и данных также хранятся три указателя: на родителя (net), левого (left) и правого (right) потомков. Если родителя или потомка нет, то указатель хранит нулевое (NULL, NIL) значение.

Свойство упорядоченности двоичного дерева поиска

Если x – это произвольная вершина в ДДП, а вершина y находится в левом поддереве вершины x, то y.key <= x.key. Если 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.key) Then nodeTemp = nodeTemp.left; // То он должен быть в его левом поддереве Else nodeTemp = nodeTemp.right; // А иначе в правом End node.nodeParent = nodeParent; If (nodeParent == NIL) Then // Если в дереве ещё нет вершин Tree.root = node; // То добавить первую Else Begin // Если ключ вершины, которую мы хотим вставить, // меньше ключа вершины, потомком которой должна стать // вставляемая вершина If (node.key < nodeParent.key) Then 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 CTree>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<CTree> { private: int data; protected: static CTreeBase<CTree> treeNil; }; //////////////////////////////////////////////////////////// CTreeBase<CTree> 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. Удаление элемента по ключу (случайные ключи)

Хорошо видно, что при увеличенном размере элемента деревья догоняют, а то и значительно обгоняют массивы. Таким образом, очевидно, что выбор структуры данных сильно зависит от предполагаемого количества элементов и их размера. Напоследок хотелось бы сказать, что правильный выбор структуры данных является одним из основных моментов, определяющих производительность программы. Поэтому подходить к выбору надо осторожно, продумав все возможные - как наиболее вероятные, так и наихудшие слу