АВЛ и Красно-черное -деревья.
АВЛ-дерево – сбалансированное двоичное дерево поиска. Для каждой его вершины высоты двух ее поддеревьев различаются не более чем на 1. Изобретено Адельсон-Вельским Г.М. и Ландисом Е.М. в 1962 г.
В АВЛ-дереве высоты h не меньше 𝐹ℎ узлов, где 𝐹ℎ - число Фибоначчи.
Специальные балансирующие операции,
восстанавливающие свойство «высоты двух поддеревьев различаются не более чем на 1» - вращения.
- Малое левое вращение.
- Малое правое вращение.
- Большое левое вращение.
- Большое правое вращение.
* В каждой вершине храним высоту ее поддерева.
* При операциях, изменяющих структуру дерева, надо
пересчитывать высоту затронутых поддеревьев.
* При операциях вставки и удаления высота дерева может
измениться только на 1.
* Соответственно разница высот поддеревьев может стать.
равной 2
* Исправляем это соответствующим вращением.
Используется когда:
Высота(R) = Высота(L) + 2 и Высота(С) ≤ Высота(R)
После операции:
- высота дерева остается прежней, если Высота(С)=Высота(R)
- высота дерева уменьшится на 1, если Высота(С)<Высота(R)
Используется когда:
Высота(R) = Высота(L) + 1 и Высота(С) ≤ Высота(L)+2
После операции:
- высота дерева уменьшится на 1.
Комбинация МПВ (c-b) и МЛВ (a-c)
Используется когда:
Высота(R) = Высота(L) + 1 и Высота(С) ≤ Высота(L)+2
После операции:
- высота дерева уменьшится на 1
Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.
- Проходим по пути поиска, пока не убедимся, что ключа нет в дереве.
- Включаем новую вершину как в стандартной операции вставки в дерево поиска.
- Возвращаемся к родителю вставленной вершины и проверяем в каждой вершине сбалансированность. Если разность высот поддеревьев равна 2 – выполняем нужное вращение.
Время работы: О(log n)
- Ищем вершину, которую требуется удалить.
- Проверяем сколько поддеревьев у удаляемой вершины
- Если удаляемая вершина – лист или имеет одно поддерево, то удаляем ее.
- Если есть 2 поддерева, то ищем вершину на замену в соответствии с алгоритмом удаления из бинарного дерева. Меняем значения и удаляем вершину
- Возвращаемся к родителю удаленной вершины и проверяем в каждой вершине сбалансированность. Если разность высот поддеревьев равна 2 – выполняем нужное вращение.
Время работы: О(log n)
Красно-черное дерево – двоичное дерево поиска
- Вершины делятся на красные и черные
- Каждая вершина хранит ключ и значение
- Отсутствующие указатели помечаются указателями на фиктивный узел - nil
- Каждый лист nil – черный
- Если вершина - красная, то ее потомки – черные
- Все пути от корня к листьям содержат одинаковое число черных вершин. Это число называется черной высотой дерева ( bh(n) ).
- Каждый узел промаркирован красным или чёрным цветом.
- Корень и конечные узлы (листья) дерева — чёрные.
- У красного узла родительский узел — чёрный.
- Все простые пути из любого узла x до листьев содержат одинаковое количество чёрных узлов.
- Чёрный узел может иметь чёрного родителя.
- При обычной вставке свойство красно-черности могут нарушаться.
- Для изменения структуры дерева применяются операции поворота.
- Для изменения красно-черности применяется корректировка.
- Для удобства полагаем, что для дерева имеется узел nil.
Для поддержания сбалансированности вводится операция
поворота или вращения.
Для этого отцепляется поддерево и переносится на другую
сторону.
Возможно 5 случаев,
нарушающих свойства красночерного дерева.
Восстановление свойств
начинается с нового элемента и
идет вверх по дереву.
- Узел z – красный
- Дядя U узла z – красный
- Узел P – это корень левого поддерева родителя G
- Родительский узел P узла z красный
- Дядя U узла z – черный.
- Узел z – правый потомок P.
- Узел z – красный.
- Узел P – это корень левого поддерева родителя G.
- Родительский узел P узла z красный.
- Дядя U узла z – черный.
- Узел z – левый потомок P.
- Узел z – красный.
- Узел P – это корень левого поддерева родителя G.
- Родительский узел P узла z красный.
Обозначения:
- P – предок удалённого узла M.
- N – потомок удалённого узла M, поставленный на его место.
- S – «брат» удалённого узла M.
- Поиск: т.к. КЧД в худшем случае выше – поиск медленнее, но не более чем на 40%
- Сбалансированность КЧД хуже, чем у АВЛ, но работа по поддержанию сбалансированности обычно эффективнее. Для балансировки КЧД производится минимальная работа по сравнению с АВЛ-деревьями.
- Вставка требует до 2-х поворотов, но из-за большей высоты КЧД может занимать больше времени
- Удаление в КЧД обычно быстрее (КЧД требует до 3-х поворотов для удаления, АВЛ-дерево может потребовать повороты до глубины корня)
Для АВЛ: 𝐻 (𝑛) ≤ 1,44 ∗ log(𝑛 + 2)
Для КЧД: 𝐻 (𝑛) ≤ 2 ∗ log(𝑛 + 1)
//TODO