RBTree - красно-черное дерево

Красно-чёрное дерево (Red-black tree, RB-Tree) — самобалансирующееся двоичное дерево поиска, гарантирующих логарифмический рост высоты от числа узлов.

Дополнительные требования к двоичному дереву:
1. Узел либо красный, либо чёрный
2. Корень — чёрный
3. Все листья (NIL) — чёрные (листья не содержат данных)
4. Оба потомка каждого красного узла — чёрные.
5. Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число чёрных узлов.
Эти ограничения реализуют главное свойство красно-чёрных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа.
Результатом является то, что дерево примерно сбалансировано.

Реализацию красно-черного дерева на java можно посмотреть тут: RBTree.java

Но в такой реализации оно сложно для понимания и программистам бд более близка реализация через B-дерево с фактором = 4.


В таком дереве каждый узел может содержать от 1 до 3 значений и от 2 до 4 указателей на потомков.

Если страница В-дерева содержит только одно значение, данный узел чёрный и имеет двух потомков.
Если страница содержит три значения, то центральный узел является чёрным, а каждый его сосед — красным.
Однако, если страница содержит два значения, любой узел может стать чёрным в красно-чёрном дереве (и тогда второй будет красным).

Пример реализации красно-черного дерева на основе B-дерева с размером блока = 3 можно посмотреть тут: BTree.scala

Для программистов БД нужно помнить 2 отличия B-дерева от B+дерева:
* при разделение элемент переносится наверх (не остается в листе)
* листы не связаны друг с другом ссылками


Красно-чёрные деревья являются одними из наиболее активно используемых на практике самобалансирующихся деревьев поиска.
В частности, контейнеры set и map в большинстве реализаций библиотеки STL языка C++, класс TreeMap языка Java, ассоциативный массив, когда реализация через списки дает слишком много коллизий
( подробное описание хэш массива тут: 3ий вариант реализации Oracle HashMap )

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