Red-Black-Tree





Алгоритм

Красно-чёрное дерево (англ. Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов (N) и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — 'цвета'. Этот атрибут может принимать одно из двух возможных значений — 'чёрный' или 'красный'.

Свойства:

  • Операции вставки\удаления\поиска не превосходят: O(logN)
  • Расход памяти - O(N)
  • Вставка - не более 2х поворотов
  • Удаление - не более 3х поворотов