RB- бинарное дерево со след свойствами

►каждая внешняя (или нулевая) вершина считается черной;

►корневая вершина дерева черная; ►украсной вершины дети черные;

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

g

c	h
a	e
b d	f

h <= 2 log2 (n+1)

Преимущества RB

►Простая процедура восстановления сбалансированности

►перекраска

операции вращения вершины влево и вправо, (не больше двух при добавлении элемента и не больше четырех при удалении).

число операций при восстановлении структуры RB-дерева <= K · h

реализация