Высота красно черные деревья

30. Красно – черные деревья. Свойства. Вращение. Высота красно – черного дерева.

Красно-черные деревья пред­ставляют собой одну из множества «сбалансированных» схем деревьев поиска, ко­торые гарантируют время выполнения операций над динамическим множеством O(log₂n) даже в наихудшем случае.

Красно-черное дерево (red-black tree) — это двоичное дерево поиска, вершины которого разделены на красные (red) и черные (black). Таким образом каждая вершина хранит один дополнительный бит — её цвет.

При этом выполняются определённые требования, которые гарантируют, что глубины любых двух листьев отличаются не более чем в два раза.

Каждая вершина красно-черного дерева имеет поля color (цвет), key (ключ), left (левый ребенок), right (правый ребенок) и p (родитель). Если у вершины отсутствует ребенок или родитель, то соответствующее поле содержит NIL.

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

1. каждая вершина — либо черная, либо красная ;
2. корень дерева является черным;
3. каждый лист (NIL) — чёрный ;
4. если вершина красная, оба её ребенка чёрные ;
5. все пути, идущие вниз от корня к листьям, содержат одинаковое количество чёрных вершин.

Повороты

Операции над деревом поиска Tree_Insert и Tree_Delete, будучи приме­нены к красно-черному дереву с n ключами, выполняются за время O(log₂n). Поскольку они изменяют дерево, в результате их работы могут нарушаться крас­но-черные свойства. Для восстановления этих свойств мы должны изменить цвета некоторых узлов дерева, а также структу­ру его указателей. Изменения в структуре указателей будут выполняться при помощи поворотов (rotations), которые представляют собой локальные операции в дереве поиска, сохраняющие свойство бинарного дерева поиска. На рис. показаны два типа поворотов — левый и правый (здесь — произвольные поддеревья). При выполнении левого поворота в узлех предполагается, что его правый дочерний узел у не является листом nil [T]. Левый поворот выполняется «вокруг» связи между х и у, делая у новым корнем поддерева, левым дочерним узлом которого становится х, а бывший левый потомок узла у — правым потомком х.

Операции поворота в бинарном дереве поиска

В псевдокоде процедуры Left_Rotate предполагается, что right[х] nil [Т], а родитель корневого узла — nil[T]. Left_Rotate(T, х)

1. у right[x] Устанавливаем у.
2. right[x] left[y] Левое поддерево у становится правым поддеревом х

3 if left[y]nil[T] 4 then p[left[y]] х

1. р[у]р[х] Перенос родителя х в у
2. if p[x] = nil[T]

1. then root[T]у
2. else if x = left[p[х]]

9 then left [p[x]] у 10 else right[p[x]] у

1. left[y] xx— левый дочерний у
2. p[x]у

31. Добавление вершины в красно – черном дереве.

Сначала выполняется обычная операция включения в двоичное дерево Tree_Insert и новая вершина помечается красным цветом. После этого восстанавливаются RB-свойства, если они нарушены путем перекраски вершин и вращений. Рассмотрим случаи нарушения RB-свойств на примере включения в дерево: При включении х нарушено третьеRB-свойство для вершины 5 (оба сына должны быть черные). Т.е. RB-свойство нарушается, если родитель нового узла красный. Как можно восстановить его: Случай 1: Если родитель красный, то родитель родителя – черный (в силу RB-свойства 2). Если у деда (7) второй сын – у ( дядя нового узла х) тоже красный, то можно перекрасить указанных предков: сделать деда красным, а родителя и дядю – черными. Это не изменит черную высоту дерева и восстановит третье свойство для родителя(5). После перекраски. Т.е. теперь 5 – черная вершина, которая может иметь и красного и черного сына. Но появился новый красный узел х(7). Теперь нарушено 3-еRB-свойство родителя узла 7 (2), т.к. этот узел тоже красный. К сожалению дядя (14) не красный и перекраску делать нельзя, не нарушив черной высоты. Тогда используем LL – поворот родителя х – (2). Исправлено нарушение 3-го свойства для узла 2, но нарушено для узла 7. Случай 3 отличается от случая 2 тем, что х является левым, а не правым сыном своего родителя. В этом случае делаем правый поворот родителя (11). Красную вершину 7, оказавшуюся в корне, окрашиваем в черную, а вершины 2 и 11 – в красные. Это не нарушит RB-свойство 4). RB_Insert (T, x)

1. Tree_Insert (T, x)
2. color [x] ← RED
3. while x ≠ root [T] and color [p[x]] = RED
4. dv if p[x] = left [p[p[x]]]
5. then y ← right [p[p[x]]]
6. if color [y] = RED
7. then color [p[x]] ← BLACK случай 1
8. color [y] ← BLACK случай 1
9. color [p[p[x]]] ← RED случай 1
10. x ← p[p[x]] случай 1
11. else if x = right [p[x]]
12. then x ← p[x] случай 2
13. Left_Rotate (T, x) случай 2
14. color [p[x]] ← BLACK случай 3
15. color [p[p[x]]] ← RED случай 3
16. Right_Rotate (T, p[p[x]]) случай 3
17. else (симметричный текст с заменой left ↔ right)
18. color [root[T]] ← BLACK

При включении, если выпадает случай 3, выполняется не более одного вращения, и в случае 2 – не более двух вращений.

Источник

Красно-черные деревья: коротко и ясно

Итак, сегодня хочу немного рассказать о красно-черных деревьях. Рассказ будет кратким, без рассмотрения алгоритмов балансировки при вставке/удалении элементов в красно-черных деревьях.

Красно-черные деревья относятся к сбалансированным бинарным деревьям поиска.

Как бинарное дерево, красно-черное обладает свойствами:

1) Оба поддерева являются бинарными деревьями поиска.

2) Для каждого узла с ключом выполняется критерий упорядочения:

ключи всех левых потомков

(в других определениях дубликаты должны располагаться с правой стороны либо вообще отсутствовать).
Это неравенство должно быть истинным для всех потомков узла, а не только его дочерних узлов.

Свойства красно-черных деревьев:

1) Каждый узел окрашен либо в красный, либо в черный цвет (в структуре данных узла появляется дополнительное поле – бит цвета).

2) Корень окрашен в черный цвет.

3) Листья(так называемые NULL-узлы) окрашены в черный цвет.

4) Каждый красный узел должен иметь два черных дочерних узла. Нужно отметить, что у черного узла могут быть черные дочерние узлы. Красные узлы в качестве дочерних могут иметь только черные.

5) Пути от узла к его листьям должны содержать одинаковое количество черных узлов(это черная высота).

Ну и почему такое дерево является сбалансированным?

Действительно, красно-черные деревья не гарантируют строгой сбалансированности (разница высот двух поддеревьев любого узла не должна превышать 1), как в АВЛ-деревьях. Но соблюдение свойств красно-черного дерева позволяет обеспечить выполнение операций вставки, удаления и выборки за время . И сейчас посмотрим, действительно ли это так.

Пусть у нас есть красно-черное дерево. Черная высота равна (black height).

Если путь от корневого узла до листового содержит минимальное количество красных узлов (т.е. ноль), значит этот путь равен .

Если же путь содержит максимальное количество красных узлов ( в соответствии со свойством ), то этот путь будет равен .

То есть, пути из корня к листьям могут различаться не более, чем вдвое (, где h — высота поддерева), этого достаточно, чтобы время выполнения операций в таком дереве было

Как производится вставка?

Вставка в красно-черное дерево начинается со вставки элемента, как в обычном бинарном дереве поиска. Только здесь элементы вставляются в позиции NULL-листьев. Вставленный узел всегда окрашивается в красный цвет. Далее идет процедура проверки сохранения свойств красно-черного дерева .

Свойство 1 не нарушается, поскольку новому узлу сразу присваивается красный цвет.

Свойство 2 нарушается только в том случае, если у нас было пустое дерево и первый вставленный узел (он же корень) окрашен в красный цвет. Здесь достаточно просто перекрасить корень в черный цвет.

Свойство 3 также не нарушается, поскольку при добавлении узла он получает черные листовые NULL-узлы.

В основном встречаются 2 других нарушения:

1) Красный узел имеет красный дочерний узел (нарушено свойство ).

2) Пути в дереве содержат разное количество черных узлов (нарушено свойство ).

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

Это вообще где-то используется?

Да! Когда в институте на третьем курсе нам читали «Алгоритмы и структуры данных», я и не могла представить, что красно-черные деревья где-то используются. Помню, как мы не любили тему сбалансированных деревьев. Ох уж эти родственные связи в красно-черных деревьях («дядя», «дедушка», «чёрный брат и крестный красный отец»), прям Санта-Барбара какая-то. Правые и левые, малые и большие повороты АВЛ-деревьев – сплошные американские горки. Вы тоже не любите красно-черные деревья? Значит, просто не умеете их готовить. А кто-то просто взял и приготовил. Так, например, ассоциативные массивы в большинстве библиотек реализованы именно через красно-черные деревья.

Это все, что я хотела рассказать.

Источник