Изменения

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

Красно-черное дерево

13 байт добавлено, 19:25, 20 июня 2012
Вставка элемента
1. "Дядя" этого узла тоже красный. Тогда просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" - в красный. Проверяем, не нарушает ли он теперь балансировку. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет.
[[Файл:D_1Untitled-1.png|200px|]]
2. "Дядя" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком.
[[Файл:D_2Untitled-2.png|275px250px|]]
=== Удаление вершины ===
98
правок

Навигация