КРАСНО-ЧЕРНЫЕ ДЕРЕВЬЯ.

Свойства:

1) Каждая вершина имеет цвет – красный или черный,

2) Если вершина красная, то оба ее потомка черные,

3) Все пути, ведущие от корня к листьям, содержат одинаковое количество черных вершин.

Красно-черное является подмножеством СДБ, в котором каждый узел может содержать от 1 до 3 значений и, соответственно, от 2 до 4 указателей на потомков.

Можно «поднять» красные узлы в графическом представлении красно-черного дерева так, чтобы они оказались на одном уровне по горизонтали со своими предками черными узлами, образуя страницу, тогда будет видно, что горизонтальная ссылка всегда указывает на красную вершину, а вертикальная – на черную.

SPLAY-ДЕРЕВЬЯ.

Расширяющееся дерево является двоичным деревом поиска, в котором поддерживается свойство сбалансированности. Это дерево принадлежит классу «саморегулирующихся деревьев», которые поддерживают необходимый баланс ветвления дерева, чтобы обеспечить выполнение операций поиска, добавления и удаления за логарифмическое время от числа хранимых элементов. Это реализуется без использования каких-либо дополнительных полей в узлах дерева (как, например, в Красно-чёрных деревьях или АВЛ-деревьях, где в вершинах хранится, соответственно, цвет вершины и глубина поддерева). Вместо этого «расширяющие операции» (splay operation), частью которых являются вращения, выполняются при каждом обращении к дереву. Учётная стоимость в расчёте на одну операцию с деревом составляет O (logn). Идея: после обращения к вершине мы поднимаем ее к корню.

Операции:

Splay (расширение)

Основная операция дерева. Заключается в перемещении вершины в корень при помощи последовательного выполнения трёх операций: Zig, Zig-Zig и Zig-Zag. Обозначим вершину, которую хотим переместить в корень за x, её родителя - p, а родителя p (если существует) - g.

· Zig: выполняется, когда p является корнем.

· Zig-Zig: выполняется, когда и x, и p являются левыми (или правыми) сыновьями. Дерево поворачивается по ребру между g и p, а потом - по ребру между p и x.

· Zig-Zag: выполняется, когда x является правым сыном, а p - левым (или наоборот). Дерево поворачивается по ребру между p и x, а затем - по ребру между x и g.

С одной стороны, –сложность доступа, n – количество вершин. В данном случае дерево ведет себя как сбалансированное. С другой стороны, если к каждому элементу осуществлялся хотя бы 1 доступ, то дерево ведет себя как дерево оптимального поиска, т. е. сложность доступа составляет

Поиск элемента:

Если ключ найден, то применяется splay к нему. Иначе применяется к последней вершине, к которой осуществлялся доступ.

Добавление элемента:

Вставка ->Splay

Пример:

Удаление элемента:

Удаление ->Splay к родителю

Пример:

Объединение двух деревьев:

t₁ t₂

Ищем максимальную вершину в t₁, проводим с ней splayи ставим ее в корень нового дерева.

Split (разделение дерева на две части):

Поиск и splayвершины х, по которой будем делить ->Разделяем либо по одному, либо по второму ребру.

Не нашли, что искали? Воспользуйтесь поиском: