Красное-чёрное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
Создал определение |
|||
| Строка 1: | Строка 1: | ||
'''Красно-чёрное дерево'''(англ. red-black tree) - самобалансирующееся бинарное дерево поиска (англ. Binary Search Tree, BST) со следующими свойствами: | |||
''Красно-чёрное дерево''(англ. red-black tree) - самобалансирующееся бинарное дерево поиска (англ. Binary Search Tree, BST) со следующими свойствами: | |||
* Каждая вершина имеет цвет: красный или чёрный | * Каждая вершина имеет цвет: красный или чёрный | ||
* Корень дерева - чёрный | * Корень дерева - чёрный | ||
Версия от 19:20, 12 марта 2020
Красно-чёрное дерево(англ. red-black tree) - самобалансирующееся бинарное дерево поиска (англ. Binary Search Tree, BST) со следующими свойствами:
- Каждая вершина имеет цвет: красный или чёрный
- Корень дерева - чёрный
- У каждой нелистовой вершины ровно два ребёнка
- Все листья чёрные и фиктивные
- У красной вершины оба ребёнка чёрные
- Чёрная высота каждой вершины определена корректно