Красное-чёрное дерево

Материал из Public ATP Wiki
Перейти к: навигация, поиск

Красно-чёрное дерево(англ. red-black tree) - самобалансирующееся бинарное дерево поиска (англ. Binary Search Tree, BST) со следующими свойствами:

  • Каждая вершина имеет цвет: красный или чёрный
  • Корень дерева - чёрный
  • У каждой нелистовой вершины ровно два ребёнка
  • Все листья чёрные и фиктивные
  • У красной вершины оба ребёнка чёрные
  • Чёрная высота каждой вершины определена корректно

Чёрная высота

На пути от любой вершины красно-чёрного дерева до её потомка-листа одинаковое количество чёрных вершин.

Чёрная высота вершины $x$ (Обозначаем $bh(x)$) - количество чёрных вершин на пути от $x$ до любого её потомка-листа, не считая самого $x$.

Лемма 1
В поддереве вершины $x$ как минимум $2^{bh(x)} - 1$ вершин.
[развернуть]
Доказательство

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

Лемма 2
Если $T$ - красно-чёрное дерево, то $h(T) \leq log_2 (n + 1)$.
[развернуть]
Доказательство

Балансировка

Рассмотрим, как поддерживать свойства красно-чёрного дереве при операции insert.

Сразу после insert

Производим вставку элемента в дерево как в любом BST и сразу красим его в красный цвет. Вставленный элемент - $z$, рассмотрим его "дядюшку" $y$ и разберём случаи, в которых после такой вставки могут нарушиться свойства нашего дерева.