Изменения

Перейти к: навигация, поиск

Левосторонние красно-чёрные деревья

Нет изменений в размере, 17:18, 19 апреля 2018
Удаление максимума
Будем поддерживать инвариант : Для любого узла либо сам узел, либо правый предок узла '''красный'''.
Будем придерживаться тактики , что удалять лист легче, чем внутренний узел.
 
Заметим, что если правый потомок вершины и правый потомок правого потомка вершины черные, необходимо переместить левую красную ссылку вправо для сохранения инварианта.
[[MinEasy.png|400px|thumb|centerright| Перемещение красной ссылки. Простой случай]]  [[MinHard.png|400px|thumb|centerright| Перемещение красной ссылки. Сложный случай]]
===Псевдокод===
288
правок

Навигация