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

Материал из Public ATP Wiki
Версия от 22:19, 12 марта 2020; Algocourselecturenotes (обсуждение | вклад) (Создал определение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

  • Каждая вершина имеет цвет: красный или чёрный
  • Корень дерева - чёрный
  • У каждой нелистовой вершины ровно два ребёнка
  • Все листья чёрные и фиктивные
  • У красной вершины оба ребёнка чёрные
  • Чёрная высота каждой вершины определена корректно
Источник — «http://wiki.atp-fivt.org/index.php?title=Красное-чёрное_дерево&oldid=252»