Рубрики

Красно-Черное Дерево | Комплект 1 (Введение)

Красно-черное дерево — это самобалансирующееся двоичное дерево поиска (BST), где каждый узел следует следующим правилам.

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

2) Корень дерева всегда черный.

3) Нет двух смежных красных узлов (красный узел не может иметь красного родителя или красного ребенка).

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

Почему красно-черные деревья?
Большинство операций BST (например, поиск, максимальное, минимальное, вставка, удаление и т. Д.) Занимают время O (h), где h — высота BST. Стоимость этих операций может стать O (n) для перекошенного двоичного дерева. Если мы удостоверимся, что высота дерева остается O (Logn) после каждой вставки и удаления, то мы можем гарантировать верхнюю границу O (Logn) для всех этих операций. Высота красно-черного дерева всегда равна O (Logn), где n — количество узлов в дереве.

Сравнение с AVL Tree
Деревья AVL более сбалансированы по сравнению с красно-черными деревьями, но они могут вызвать большее вращение при вставке и удалении. Так что, если ваше приложение включает в себя много частых вставок и удалений, тогда предпочтительны красно-чёрные деревья. И если вставки и удаления происходят реже, а поиск — более частая операция, то дерево AVL должно быть предпочтительнее, чем красно-черное дерево.

Как Красно-Черное Дерево обеспечивает баланс?
Простой пример понимания балансировки: цепочка из 3 узлов в красно-черном дереве невозможна. Мы можем попробовать любую комбинацию цветов и увидеть, что все они нарушают свойство красно-черного дерева.

A chain of 3 nodes is nodes is not possible in Red-Black Trees. 
Following are NOT Red-Black Trees
        30             30               30       
       / \            /  \             /  \
     20  NIL         20   NIL         20   NIL
    / \             / \              /  \   
  10  NIL          10  NIL          10  NIL  
Violates          Violates        Violates
Property 4.      Property 4       Property 3 

Following are different possible Red-Black Trees with above 3 keys
         20                           20
       /   \                        /   \
     10     30                    10     30
    /  \   /  \                 /  \    /  \
 NIL  NIL NIL NIL             NIL  NIL NIL NIL


Из приведенных выше примеров мы получаем некоторое представление о том, как красно-черные деревья обеспечивают баланс. Ниже приводится важный факт о балансировке в красно-черных деревьях.

Черная высота красно-черного дерева:
Высота черного — это количество черных узлов на пути от корня до листа. Листовые узлы также считаются черными узлами. Из приведенных выше свойств 3 и 4 мы можем вывести, что красно-черное дерево высотой h имеет black-height> = h / 2 .

Number of nodes from a node to its farthest descendant leaf is no more than twice as the number of nodes to the nearest descendant leaf.


Каждое Красное Черное Дерево с n узлами имеет высоту <=
2Log 2 (n + 1)

Это можно доказать, используя следующие факты:
1) Для общего двоичного дерева, пусть k будет минимальным числом узлов на всех путях от корня до NULL, тогда n> = 2 k — 1 (например, если k равно 3, то n не меньше 7). Это выражение также можно записать в виде k <= Log 2 (n + 1)

2) Из свойства 4 красно-черных деревьев и вышеупомянутого утверждения можно сказать, что в красно-черном дереве с n узлами существует путь от корня к листу с не более чем Log 2 (n + 1) черными узлами.

3) Из свойства 3 красно-черных деревьев мы можем утверждать, что число черных узлов в красно-черном дереве не менее ⌊ n / 2 ⌋, где n — общее количество узлов.

Из вышеупомянутых 2 пунктов мы можем заключить тот факт, что Красное Черное Дерево с n узлами имеет высоту <= 2Log 2 (n + 1)

В этом посте мы представили красно-черные деревья и обсудили, как обеспечить баланс. Сложной задачей является сохранение баланса при добавлении и удалении ключей. Вскоре мы будем обсуждать операции вставки и удаления в следующих публикациях на красно-черном дереве.

Упражнение:
1) Можно ли иметь все черные узлы в красно-черном дереве?
2) Нарисуйте красно-черное дерево, которое не является мудрой структурой AVL ?

Вставка и удаление
Вставка красное черное дерево
Красно-черное дерево

Приложения :

  1. Большинство функций самобалансирующейся библиотеки BST, таких как map и set в C ++ (OR TreeSet и TreeMap в Java), используют Red Black Tree
  2. Используется для реализации CPU Scheduling Linux. Полностью честный планировщик использует его.

Ссылки:
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест
http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Видеолекция о красно-черном дереве Тима Рафгардена
MIT Видео лекция о красно-черном дереве
MIT Лекционные заметки о красном черном дереве

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Красно-Черное Дерево | Комплект 1 (Введение)

0.00 (0%) 0 votes