Изменения

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

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

12 байт добавлено, 19:48, 20 июня 2012
Объединение красно-чёрных деревьев
Рассмотрим пример объединения двух красно-чёрных деревьев и вершины<tex>(35)</tex>:
[[Файл:Merge1Untitled-7.jpg‎png‎|550px|]]
Узнаём чёрную высоту левого и правого дерева. Чёрная высота левого и правого деревьев равна <tex>2</tex> и <tex>1</tex> соответственно.
Чёрная высота вершины<tex>(8)</tex> левого дерева равна высоте правого дерева и ключ является наибольшим. Поэтому вершина<tex>(8)</tex> становится левым сыном вершины<tex>(35)</tex>, а правое дерево будет правым сыном. Вершина<tex>(35)</tex> станет правым сыном вершины<tex>(0)</tex>:
[[Файл:Merge2Untitled-8.jpg‎png‎|400px|]]
Далее проверяем: не нарушили ли мы свойства красно-чёрного дерева. Так как присутствует нарушение(у красной вершины есть красный сын), то перекрасим вершины и сделаем поворот:
[[Файл:Merge3Untitled-9.jpg‎png‎|400px|]]
== Преимущества красно-чёрных деревьев ==
98
правок

Навигация