Загрузка...
Учебная работа. Реферат: Двоичные деревья поиска
Роман Акопов
Определение Двоичного Дерева Поиска (Binary Search Tree, BST)
Двоичным деревом поиска (ДДП) именуют дерево, все верхушки которого упорядочены, любая верхушка имеет не наиболее 2-ух потомков (назовём их левым и правым), и все верхушки, не считая корня, имеют родителя. Верхушки, не имеющие потомков, именуются листами. Предполагается, что каждой верхушке соответствует элемент либо несколько частей, имеющие некоторые главные значения, в предстоящем называемые просто ключами. Обычно одной верхушке соответствует один элемент, потому данные определения можно без утраты смысла считать синонимами, хотя и нужно держать в голове, что в неких реализациях это не так. В приведённых методах считается, что одной верхушке соответствует лишь один элемент. Потому мы будем употреблять понятия ключа верхушки и данных верхушки, подразумевая ключ и данные соответственного верхушке элемента. Мы так же будем осознавать под вставкой верхушки добавление верхушки с обозначенным значением элемента и присвоение указателям на родителя и потомков корректных значений. Конкретно ключ употребляется во всех операциях сопоставления частей. Элемент может также содержать ассоциированные с ключом данные. На практике в качестве ключа может употребляться часть данных элемента. Ключ также может храниться как отдельное
Поиск верхушки по ключу.
Определение вершин с наименьшим и наибольшим значением ключа.
Переход к предшествующей либо следующей верхушке, в порядке, определяемом ключами.
Вставка верхушки.
Удаление верхушки.
Двоичное дерево быть может логически разбито на уровни. Корень дерева является нулевым уровнем, потомки корня – первым уровнем, их потомки – вторым, и т.д. Глубина дерева это его наибольший уровень. понятие глубины также быть может описано в определениях пути, другими словами глубина дерева есть длина самого длинноватого пути от корня до листа, если следовать от родительской верхушки до потомка. Каждую верхушку дерева можно разглядывать как корень поддерева, которое определяется данной верхушкой и всеми потомками данной верхушки, как прямыми, так и косвенными. Потому о дереве можно гласить как о рекурсивной структуре. Эффективность поиска по дереву впрямую связана с его сбалансированностью, другими словами с наибольшей различием меж глубиной левого и правого поддерева посреди всех вершин. Имеется два последних варианта – равновесное бинарное дерево (где любой уровень имеет полный набор вершин) и вырожденное дерево, где на любой уровень приходится по одной верхушке. Вырожденное дерево эквивалентно связанному списку. время выполнения всех главных операций пропорционально глубине дерева. Таковым образом, скоростные свойства поиска в ДДП могут варьироваться от 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. Она учитывает два варианта. Если правое поддерево не пусто, то верхушка из правого поддерева с наименьшим значением ключа и будет последующей. Если же правое поддерево пусто, тогда мы идём ввысь, пока не найдём верхушку, являющуюся левым потомком собственного родителя. Этот родитель (если он есть) и будет последующей верхушкой. Возвращаемое
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-го (случаи 1 и 2)
If (node.left == NIL) or (node.right == NIL) Then
del = node; // на физическом уровне удаляем текущую верхушку
Else
del = TreeNext(node); // По другому последующую
If (del.left != NIL) Then // Пытаемся отыскать хоть 1-го потомка
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! Вправду, методам совсем всё равно, какое численное адресок переменной, проинициализированной особенным образом. Я покажу это на языке С++, но думаю, этот пример можно будет перевести и на остальные языки, хотя там, быстрее всего, нет шаблонов, и придется пожертвовать типобезопасностью.
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. Еще одним “продвинутым” видом деревьев является так именуемые красно-чёрные деревья. АВЛ деревья обеспечивают наиболее высшую сбалансированность дерева, но Издержки на их поддержание выше. Так как на практике разница в сбалансированности меж этими 2-мя видами деревьев не высока, почаще употребляются красно-чёрные деревья.
Красно
—
чёрные
деревья
(Red-Black Tree, RB-Tree)
Итак, одним из методов решения главный задачи использования ДДП являются красно-чёрные деревья. Красно-чёрные (заглавие исторически соединено с игральными картами, так как из их просто созодать обыкновенные модели) деревья (КЧД) – это ДДП, любая верхушка которых хранит ещё одно доп логическое поле (color), обозначающее цвет: красноватый либо чёрный. Практически, в КЧД гарантируется, что уровни всех 2-ух листьев различаются не наиболее, чем вдвое. Этого условия оказывается довольно, чтоб обеспечить скоростные свойства поиска, близкие к O(log2N). При вставке/подмене выполняются доп деяния по балансировке дерева, которые не могут не замедлить работу с деревом. При описании алгоритмов мы будем считать, что NIL – это указатель на фиктивную верхушку, и операции (NIL).left, (NIL).right, (NIL).color имеют смысл. Мы также будем считать, что любая верхушка имеет 2-ух потомков, и только 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 не так сложна, как кажется на 1-ый взор. Разглядим её подробнее. Опосля строк 3-4 производятся все характеристики КЧД, не считая, может быть, 1-го: у новейшей красноватой верхушки быть может красноватый родитель . Таковая ситуация (красноватая верхушка имеет красноватого родителя) может сохраниться опосля хоть какого числа итераций цикла. Снутри цикла рассматриваются 6 разных случаев, но три из их (строчки 8-28) симметричны трём иным (строчки 30-50), различие только в том, является ли родитель верхушки node правым либо левым потомком собственного родителя (случаи делятся в строке 7). Потому мы разглядим тщательно лишь 1-ые три варианта (строчки 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
В вариантах 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(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 показывает на красноватую верхушку, тогда мы красим её в чёрный цвет (строчка 68).
node показывает на корень дерева, тогда лишняя чернота быть может просто удалена.
Могло оказаться, что снутри тела цикла удается выполнить несколько вращений и перекрасить несколько вершин, так что два раза чёрная верхушка исчезает. В этом случае присваивание node = Tree.root (строчки 33 и 64) дозволяет выйти из цикла.
Снутри цикла node показывает на два раза чёрную верхушку, а nodeTemp – на её брата (другую верхушку с этим же родителем). Так как верхушка node два раза чёрная, nodeTemp не быть может NIL, так как в этом случае вдоль 1-го пути от 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. Удаление элемента по ключу (случайные ключи)
Отлично видно, что при увеличенном размере элемента деревья догоняют, а то и существенно опереждают массивы. Таковым образом, разумеется, что выбор структуры данных очень зависит от предполагаемого количества частей и их размера. В итоге хотелось бы сказать, что верный выбор структуры данных является одним из главных моментов, определяющих производительность программки. Потому подступать к выбору нужно осторожно, продумав все вероятные — как более возможные, так и наихудшие случаи.
]]>