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