288
правок
Изменения
→Вращения
One way to view red-black BST algorithms is as maintaining the following invariant properties under insertion and deletion:
Чтобы поддерживать красно-черные двоичное деревья поиска необходимо соблюдать следующие инвариантные свойства при вставке и удалении:
* Ни один путь обход от корня до листьев дерева не содержит двух последовательных красных узлов.
* Количество черных узлов на каждом таком пути одинаково.
Из этих инвариантов следует, что длина каждого пути от корня до листьев в красно-черном дереве с <tex>N</tex> узлами не превышает <tex>2 \cdot log(N)</tex> .
</code>
В красно-черных деревьях используется такая операция как <tex>color flip</tex>, которая инвертирует цвет данного узла и двух его детей. Она не изменяет количество черых черных узлов на при любом пути обходе от корня до листьевдерева, но может привести к появлению двух последовательных красных узлов.
<code>
