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

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

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

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

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