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