Упорядоченная таблица – двоичное дерево

Упорядоченную таблицу можно представить двоичным деревом, если принять, что элементы таблицы размещаются в вершинах дерева и с каждой вершиной дерева (как с элементом таблицы) связывается некоторое значение ключа. Обозначим значения ключей через k_i.

Введем следующие обозначения:

Пусть k* определяет ключ элемента, находящегося в корне дерева, Л = {k_i} – множество ключей, размещенных в вершинах левого поддерева, и П = {k_i} – множество ключей, размещенных в вершинах правого поддерева.

Тогда для таблицы, представленной двоичным деревом, устанавливаются следующие правила размещения элементов:

3. Для любого k_i Л k_i < k*;

4. Для любого k_i П k_i > k*.

Указанные соотношения применяются к любому поддереву внутри двоичного дерева. Пример упорядоченной таблицы – двоичного дерева приведен на рис. II–44.

Рис. II–33

Для того чтобы получить действительно упорядоченный по возрастанию ключей список значений элементов, нужно использовать обратный обход дерева (ЛКП); в результате его применения к дереву, представленному на рис. II–45, получим:

25, 30, 33, 35, 40, 45, 50, 55, 80.

Для того чтобы найти в таблице – дереве элемент по значению его ключа, используются сформулированные выше правила, в соответствии с которыми, если искомый ключ меньше ключа в вершине дерева, следует продолжить просмотр левого поддерева; если больше – правого. Поиск в поддереве выполняется так же, как и в дереве (в силу рекурсивности определения двоичного дерева). Алгоритм поиска элемента в двоичном дереве приведен на рис. II–45.

Рис. II–34

Здесь root->k определяет ключ элемента, root->left – указатель на левое поддерево, root->roght – указатель на правое поддерево дерева, корень которого задается указателем root.

Текст функции приводится ниже.

struct Node{

int key;

Type info;

Node *left, *right;

};

Node *search(Node *root, int k)

{

while(root){

if(root->key == k)

return root;

root = k < root->key ? root->left : root->right;

}

return NULL;

}

В силу рекурсивного определения дерева функцию поиска элемента можно также реализовать как рекурсивную; текст рекурсивной функции приводится ниже. Очевидно, что такой вариант не выигрывает по сравнению с предыдущим.

Node *recsearch(Node *root, int k)

{

if(!root)

return NULL; /* элемент с указанным ключом отсутствует */

return (root->key == k) ? root : (k < root->key) ? recsearch(root->left, k) : recsearch(root->right, k);

}

Если таблица – двоичное дерево определена как динамическая, для такой таблицы достаточно просто реализовать операцию включения в таблицу нового элемента: продвигаясь по соответствующим (в зависимости от значения ключа нового элемента) поддеревьям, находим вершину, имеющую в требуемом поле указателя на поддерево значение NULL, и к этому элементу подсоединяем новый элемент.

Операция удаления элемента существенно более сложна, так как в случае, если удаляется элемент, находящийся в промежуточной или корневой вершине дерева, требуется принятие специального решения. Одним из возможных решений является реорганизация дерева, в результате которого вершины более низкого уровня перемещаются наверх; в этом случае операция удаления элемента требует много времени. Другим решением может быть использование специального флага удаленного элемента (как в просматриваемых таблицах), но при этом очень неэффективно используется память. Конкретные алгоритмы удаления элемента здесь не рассматриваются.

Схема алгоритма включения нового элемента в упорядоченную таблицу – двоичное дерево приведена на рис. II–46.

Рис. II–35

Функцию включения нового элемента можно сократить, если:

3. использовать тип данных "указатель на указатель на ...";

4. использовать рекурсию.

Рассмотрим оба способа реализации функции.

В варианте (a) использование типа "указатель на указатель на элемент дерева" позволяет объединить идентичные операции по включению нового элемента в левое или правое поддерево. Текст функции приводится ниже. Функция возвращает NULL, если элемент не может быть включен в таблицу (элемент с таким ключом в таблице уже есть или нет памяти для построения нового элемента дерева), и указатель на новый элемент дерева, если новый элемент включен в таблицу.

struct Node{

int key;

Type info;

Node *left, *right;

};

Node *insert(Node **proot, int k, Type in)

{

Node **ptr = proot;

Node *cur;

/* поиск позиции в таблице – дереве для включения нового элемента */

while(*ptr){

if((*ptr)->key == k)

return NULL; /* элемент с таким ключом в таблице есть */

ptr = k < (*ptr)->key ? &(*ptr)->left : &(*ptr)->right;

}

/* создание нового элемента таблицы – дерева */

cur = new Node;

if(!cur)

return NULL; /* нет свободной памяти */

cur->key = k;

cur->info = dupl(in);

cur->left = cur->right = NULL;

/* нашли позицию; включаем новый элемент */

*ptr = cur;

return cur;

}

Вариант (b), в силу рекурсивности дерева, можно рассматривать следующим образом: Если дерево пусто, новый элемент становится его корнем. Если дерево не пусто, в зависимости от соотношения ключей выбирается левое или правое поддерево, которое является деревом; для него вновь вызывается функция включения.

Для рекурсивной функции создание элемента дерева должно быть выполнено вне функции, поэтому удобно использовать две функции: основная функция включения нового элемента в таблицу (insert()), которая создает новый элемент и вызывает функцию включения элемента в дерево, и рекурсивная функция включения в дерево (instree()). Тексты соответствующих функций приведены ниже.

struct Node{

int key;

Type info;

Node *left, *right;

};

/* рекурсивная функция включения нового элемента в двоичное дерево.

* Результат – NULL, если элемент с таким ключом в таблице уже есть, или

* указатель на включенный элемент.

* Так как функция включает новый элемент в корень дерева – т.е. должно

* измениться значение указателя на корень дерева, в функцию нужно

* передать указатель на указатель на корень дерева – Node **.

*/

Node *instree (Node **proot, Node *newnode)

{

Node **ptr = proot;

if(!*proot){

/* дерево пусто */

*proot = newnode;

return newnode;

}

/* выбор нужного поддерева */

if((*proot)->key == newnode->key)

return NULL; /* элемент с таким ключом в таблице – дереве есть */

ptr = (newnode->key < (*proot)->key) ?

&(*proot)->left : &(*proot)->right;

/* рекурсивный вызов функции включения нового элемента в выбранное

* поддерево */

return instree(ptr, newnode);

}

/* Функция включения нового элемента в таблицу. Результат – NULL, если

* элемент не может быть включен в таблицу, и указатель на новый элемент

* в противном случае

*/

Node *insert(Node **proot, int k, Type in)

{

Node *cur, *ptr;

/* создание нового элемента таблицы – дерева */

Node *cur = new Node;

if(!cur)

return NULL; /* нет свободной памяти */

cur->key = k;

cur->info = dupl(in);

cur->left = cur->right = NULL;

/* включение нового элемента в дерево */

if(!(ptr = instree(proot, cur))){

delInfo(cur->info);

delete cur;

}

return ptr;

}

20. Бинарные деревья поиска: вставка нового элемента. Оценки эффективности.

См. билет 19.

21. Бинарные деревья поиска: удаление элемента. Оценки эффективности.

22. Красно-черные деревья: определение, представление в памяти. Повороты. Оценка эффективности.

Бинарное дерево поиска с дополнительным полем цвета в узле:

struct Node {

int color;

int key;

Node *left, *right;

Node *parent;

};

Красно-черное бинарное дерево поиска удовлетворяет следующим свойствам:

1. Каждый узел является красным или черным

2. Корень дерева является черным

3. Каждый лист дерева (NULL) является черным

4. Если узел – красный, то оба его дочерних узла – черные

5. Для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов

Значения NULL рассматриваются как указатели на внешние узлы (листья) бинарного дерева поиска.

Количество черных узлов на пути от узла x (не считая сам узел) к листу называется черной высотой листа

Черной высотой дерева является черная высота его корня

Красно-черное дерево с n внутренними узлами имеет высоту h не более чем

2 lg (n + 1)

Черная высота корня должна составлять как минимум h / 2

Операции поиска выполняются за время Ο(h) = Ο(lg(n))

Операции вставки – удаления тоже могут быть выполнены за это время

Левый поворот.

1. Для узла x:

а) переустанавливается правое поддерево

б) переустанавливается родительский узел

2. Для узла y:

а) переустанавливается левое поддерево

б) переустанавливается родительский узел

3. Для узла p:

переустанавливается левое (или правое) поддерево

4. Для левого поддерева узла y:

переустанавливается родительский узел

Алгоритм Left_rotate(x)

x – заданный узел

y = x->right – правое поддерево узла x

Переустановить правое поддерево x (1a): x->right = y->left

Переустановить родительский узел левого поддерева y (если он есть) (4):

if y->left ≠ EList

y->left->parent = x

Переустановить родительский узел y (2б): y->parent = x->parent

Возможно, x был корнем дерева:

if x->parent = EList

root = y – новый корень дерева

else {

Переустановить левое или правое поддерево родительского узла x (3):

if x->parent->left = x

x->parent->left = y

else

x->parent->right = y

}

Переустановить левое поддерево y (2a):

y->left = x

Переустановить родительский узел для x (1б):

x->parent = y

Время выполнения – Ο(1)

Вставка в красно-черное дерево

Алгоритм RB_Insert(x):

1. Вставить узел x как в обычное бинарное дерево поиска

2. Полям left и right нового узла присвоить значение указателя на узлы-листы

3. Окрасить новый узел в красный цвет

4. Перекрасить узлы и выполнить повороты

Алгоритм RB_Insert(x)

prev = EList – родительский узел

ptr = root – текущий узел

while дерево не пусто: ptr ≠ EList {

prev = ptr – родительский узел

if x->key < ptr->key – выбор поддерева

ptr = ptr->left – левое поддерево

else

ptr = ptr->right– правое поддерево

}

x->parent = prev – родительский узел

if вставка в пустое дерево: prev = EList

root = x – новый корень дерева

else

выбрать поддерево:

if x->key < prev->key

вставить в левое поддерево: prev->left = x

else

вставить в правое поддерево: prev->right = x

Установить поля left и right нового узла дерева:

x->left = EList

x->right = EList

Покрасить узел: x->color = RED

Выполнить перекраску узлов и повороты дерева:

RB_Insert_Fixup(x)

Нарушение свойств дерева при вставке

1. Каждый узел является красным или черным

не нарушается

2. Корень дерева является черным

может быть нарушено

3. Каждый лист дерева является черным

не нарушается

4. Если узел – красный, то оба его дочерних узла – черные

может быть нарушено

5. Для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов

не нарушается

Восстановление свойств дерева

Новый узел – x

p1 = x->parent

узел p1 – красный

pp = p1->parent – черный

p2 = pp->right

(или p2 = pp->left)

Случай 1

Узел p2 – красный

Узел pp – черный

Узлы a, b, g, d, e – черные

Коррекция: перекрасить узлы p1 и p2 в черный цвет, pp – в красный

Переустановить узел x

Продолжить коррекцию дерева

Случай 2

Узел p2 – черный

Узел x – в правом поддереве узла p1

Узел pp – черный

Узлы a, b, g – черные

Коррекция:

шаг 1 – левый поворот вокруг узла p1

Переходим к случаю 3

Случай 3

Узел p2 – черный

Узел x – в левом поддереве узла p1

Узел pp – черный

Узлы a, b, g – черные

Коррекция:

шаг 1 – перекрасить узел p1 в черный цвет, узел pp – в красный цвет

шаг 2 – правый поворот вокруг узла pp

Алгоритм RB_Insert_Fixup(x)

x – вставленный узел

while родительский узел для x – красный (x->parent = RED) {

p1 = x->parent – родительский узел x

pp = p1->parent – родительский узел p1

if p1 = pp->left { #1 – начало

Узел вставляется в левое поддерево

p2 = pp->right

if p2->color = RED {

случай 1: перекрасить вершины:

p1->color = BLACK

p2->color = BLACK

pp->color = RED

x = pp

}

else if x в правом поддереве p1 (x = p1->right) {

случай 2:

x = p1

левый поворот: left_rotate(x)

p1 = x->parent

}

Случай 3:

перекрасить вершины:

p1->color = BLACK

pp->color = RED

правый поворот:

Right_rotate(pp)

} #1 – конец

else {

узел вставляется в правое поддерево:

повторить коды от #1 – начало до #1 – конец, заменив в них left на right, и наоборот

}

} – конец цикла

root->color = BLACK

Анализ эффективности

Вставка в красно-черное дерево =

• вставка в двоичное дерево – О(h)

• Коррекция красно-черного дерева

Коррекция:

итерации – для случая 1 – O(h)

для случаев 2 и 3 – максимум два поворота

h £ 2lg(n + 1), вставка – O(lg(n))

Удаление

• Удалить узел как в бинарном дереве поиска; учесть представление листьев

• Восстановить красно-черные свойства дерева

Алгоритм RB_Delete(x)

if x->left = Elist или x->right = Elist

y = x

else

y = successor(x)

if y->left ≠ Elist

p = y->left

else

p = y->right

p->parent = y->parent --- отличается!

if y->parent = EList

root = p

else

if y->parent->left = y

y->parent->left = p

else

y->parent->right = p

if y ≠ x {

x->key = y->key

копирование сопутствующих данных

}

if y->color = BLACK

RB_Delete_Fixup(p)

Успех

Нарушение свойств дерева при удалении

Если удаляется красный узел:

• никакая черная высота в дереве не изменяется

• никакие красные узлы не становятся соседними

корень остается черным

Если удаляется черный узел:

1. Каждый узел является красным или черным

не нарушается

2. Корень дерева является черным

может быть нарушено

3. Каждый лист дерева является черным

не нарушается

4. Если узел – красный, то оба его дочерних узла – черные

может быть нарушено

5. Для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов

нарушается!!!

Восстановление черной высоты вершины

У потомка – дополнительная чернота:

• «дважды черный» (атрибут color узла имеет значение BLACK)

• «красно-черный» (атрибут color узла имеет значение RED):

• восстанавливается свойство 5

• нарушается свойство 1 – значение атрибута color узла не соответствует цвету узла

Восстановление цвета узла

Переместить дополнительную черноту вверх по дереву:

1. Узел является красно-черным – сделать данный узел «единожды черным»

2. Узел является корнем дерева – убрать излишнюю черноту

Выполнить повороты и перекраску, устраняющие двойную черноту

Обозначения:

x – анализируемый узел дерева

p = x->parent – родительский узел

Пусть x = p->left

w = p->right – второй потомок узла p

x – дважды черный узел

w ≠ EList

Случай 1

Узел w – красный

Потомки w – черные

Узел p – черный

1. Обменять цвета w и p

2. Выполнить левый поворот вокруг узла p

Получим случаи 2, 3 или 4

Случай 2

Узел w черный

оба его потомка – черные

Шаг 1 – забрать черную окраску у x (станет единожды черным) и w (станет красным)

Шаг 2 – добавить дополнительный черный цвет узлу p

Шаг 3 – переустановить узел x, продолжить коррекцию дерева

Случай 3

Узел w – черный,

его левый дочерний узел – красный,

правый – черный

Шаг 1 – обменять цвета w и w->left

Шаг 2 – выполнить правый поворот вокруг w

Получим случай 4

Случай 4

Узел w – черный,

его правый дочерний узел – красный

Шаг 1 – обменять цвета у узлов w, p и правого дочернего узла w

Шаг 2 – левый поворот вокруг узла p

Шаг 3 – отнять черный цвет у узла x

RB_Delete_Fixup(x)

Обозначения:

x – анализируемый узел дерева

p = x->parent – родительский узел

w = p->right (или p->left) – второй потомок узла p

x – дважды черный узел

while продолжать итерации: x ≠ root и x->color == BLACK {

проверка, в каком поддереве лежит x:

p = x->parent

if х – в левом поддереве: x == p->left { # 1 – начало

w = p->right

анализ возможных ситуаций

if w – красый: w->color == RED { – случай 1

поменять цвета у w и p:

w->color = BLACK

p->color = RED

выполнить левый поворот вокруг p:

Left_Rotate(p)

w = p->right

}

if у w оба потомка черные: w->left->color == BLACK и w->right-color == BLACK { – случай 2

забрать черную окраску у w:

w->color = RED

переместиться вверх по дереву:

x = p

}

else {

if правый потомок w черный: w->right->color == BLACK { – случай 3

поменять цвета у w и w->left:

w->color = RED

w->left->color = BLACK

правый поворот вокруг w:

Right_Rotate(w)

w = p->right

}

– случай 4

поменять цвета:

w->color = p->color

p->color = BLACK

w->right->color = BLACK

левый поворот вокруг узла p

Left_Rotate(p)

x = root

}

} # 1 – конец

else {

повторить коды между #1 – начало и #1 – конец, заменив left на right, и наоборот

}

}

x->color = BLACK

23. Красно-черные деревья: общий алгоритм вставки нового элемента. Нарушение свойств красно-черного дерева при вставке.

24. Красно-черное дерево: восстановление свойств дерева при вставке нового элемента.

25. Красно-черное дерево: общий алгоритм удаления элемента. Нарушение свойств красно-черного дерева при удалении.

26. Красно-черное дерево: восстановление свойств дерева при удалении элемента.

27. AVL-дерево: определение, способы задания узлов AVL-дерева. Общий алгоритм вставки в AVL-дерево. Коррекция узлов.

28. Вставка нового элемента в AVL-дерево: коррекция AVL-дерева.

29. Удаление элемента из AVL-дерева: общий алгоритм. Коррекция узлов AVL-дерева.

30. Удаление элемента из AVL-дерева: коррекция дерева

31. B дерево: определение, структура узла. Поиск в В дереве.

32. Вставка нового элемента в В дерево.

33. Удаление элемента из В дерева.

34. Пирамида: определение, свойства пирамиды. Операция поддержки свойства пирамиды. Создание пирамиды.

35. Пирамидальная сортировка.

36. Очереди с приоритетами: определение, основные операции.