Красно черное дерево итмо

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

левостороннее красно-черное дерево. И реализовать в нем метод добавления новых элементов с балансировкой.

ShumAhd/left-sided-red-black-tree

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Алгоритмы и структуры данных (семинары)

##Урок 4. Структуры данных дерево и хэш-таблица

Необходимо превратить собранное на семинаре дерево поиска в полноценное левостороннее красно-черное дерево. И реализовать в нем метод добавления новых элементов с балансировкой.

Красно-черное дерево имеет следующие критерии: • Каждая нода имеет цвет (красный или черный) • Корень дерева всегда черный • Новая нода всегда красная • Красные ноды могут быть только левым ребенком • У краной ноды все дети черного цвета

Соответственно, чтобы данные условия выполнялись, после добавления элемента в дерево необходимо произвести балансировку, благодаря которой все критерии выше станут валидными. Для балансировки существует 3 операции – левый малый поворот, правый малый поворот и смена цвета.

(Провозился три дня, собрал франкинштейна)

Введите целое число 6 поворот влево!! 5● 6● Вы хотите продолжить? (введите y или n) y Введите целое число 3 вращение вправо 3◯ 5◯ 6◯ Вы хотите продолжить? (введите y или n) y Введите целое число 67 поворот влево!! 3◯ 5◯ 6● 67◯ Вы хотите продолжить? (введите y или n) y Введите целое число 12 поворот влево!! вращение вправо поворот влево!! 3◯ 5● 6◯ 12◯ 67◯ Вы хотите продолжить? (введите y или n) y Введите целое число 33 3◯ 5● 6◯ 12◯ 33● 67◯ Вы хотите продолжить? (введите y или n) ``` 

About

левостороннее красно-черное дерево. И реализовать в нем метод добавления новых элементов с балансировкой.

Источник

AA-дерево

АA-дерево (англ. AA-Tree) — структура данных, представляющая собой сбалансированное двоичное дерево поиска, которое является разновидностью красно-черного дерева с дополнительными ограничениями.

АA-дерево названо по первым буквам имени и фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию красно-черного дерева в 1993 году.

Описание дерева

Структура АА-дерева

Определение:

Уровень вершины (англ. Level) — вертикальная высота соответствующей вершины.

Для представления АА-дерева в памяти будем использовать следующую структуру:

struct Node: V value // значение вершины V level // высота вершины Node left // указатель на левого потомка Node right // указатель на правого потомка // Конструктор вершины (создаем экземпляр структуры с полученными значениями) Node (value : V, level : V, left : Node, right: Node)

Свойства АА-дерева

• Уровень каждого листа равен [math]1[/math] .
• Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
• Уровень каждого правого ребенка равен или на один меньше, чем у его родителя.
• Уровень каждого правого внука строго меньше, чем у его прародителя.
• Каждая вершина с уровнем больше [math]1[/math] имеет двоих детей.

Связь с красно-чёрным деревом

В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка). На картинке ниже представлен пример красно-чёрного дерева.

Теперь рассмотрим то же дерево, но с информацией об уровне каждой вершине. Горизонтальные ребра обозначают связи между ребрами одного уровня.

На практике в AA-дереве вместо значения цвета для балансировки дерева в вершине хранится информация только о ее уровне.

Для поддержки баланса красно-черного дерева необходимо обрабатывать [math]7[/math] различных вариантов расположения вершин:

В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин, чтобы проверить соблюдается ли главное правило «одна правая горизонтальная связь». То есть мы должны проверить нет ли левой горизонтальной связи, как на первом рисунке ниже и нет ли двух последовательных правых горизонтальных связей, как на правом рисунке.

Балансировка

Определение:

Горизонтальное ребро (англ. Horizontal edges) — ребро, соединяющее вершины с одинаковым уровнем.

В AA-дереве разрешены правые ребра, не идущие подряд, и запрещены все левые горизонтальные ребра. Эти более жесткие ограничения , аналогичные ограничениям на красно-черных деревьях, приводят к более простой реализации балансировки AA-дерева.

Для балансировки АА-дерева нужны следующие две операции:

Skew

[math]\mathrm[/math] — устранение левого горизонтального ребра. Делаем правое вращение, чтобы заменить поддерево, содержащее левую горизонтальную связь, на поддерево, содержащее разрешенную правую горизонтальную связь.

Node skew(t : Node) if t == [math]\varnothing[/math] return [math]\varnothing[/math] else if t.left == [math]\varnothing[/math] return t // Проверяем, есть ли у нас левое горизонтальное ребро else if t.left.level == t.level // Меняем указатель горизонтального левого ребра return Node(t.left, t.left.level, t.left.left, Node(t, t.level, t.left.right, t.right)) else return t

На рисунке ниже представлен пример работы алгоритма.

Split

[math]\mathrm[/math] — устранение двух последовательных правых горизонтальных ребер. Делаем левое вращение и увеличиваем уровень, чтобы заменить поддерево, содержащее две или более последовательных правильных горизонтальных связи, на вершину, содержащую два поддерева с меньшим уровнем.

Node split(t : Node) if t == [math]\varnothing[/math] return [math]\varnothing[/math] else if t.right == [math]\varnothing[/math] or t.right.right == [math]\varnothing[/math] return t // Проверяем, один ли уровень у родителя и внука, т.е. существует ли два последовательных правых горизонтальных ребра else if t.level == t.right.right.level // Существует два правых горизонтальных ребра. Берем центральную вершину, «поднимаем» ее и возвращаем указатель на нее return Node(t.right, t.right.level + 1, Node(t, t.level, t.left, t.right.left), t.right.right) else return t

На рисунке ниже представлен пример работы алгоритма.

Операции

Вставка элемента

Вставка нового элемента происходит как в обычном дереве поиска, только на пути вверх необходимо делать ребалансировку, используя [math]\mathrm[/math] и [math]\mathrm[/math] . Ниже представлена рекурсивная реализация алгоритма.

Node insert(x : V, t : Node) // x — вставляемое значение, t — корень дерева, в который вставляется вершина if t == [math]\varnothing[/math] return Node(x, 1, [math]\varnothing[/math], [math]\varnothing[/math]) else if x < t.value t.left = insert(x, t.left) else if x > t.value t.right = insert(x, t.right) // Случай x == t.value не определен. Т.е. вставка не будет иметь никакого эффекта, // возможны различные варианты обработки, в зависимости от решаемой задачи t = skew(t) t = split(t) return t

Пример вставки нового элемента (на рис. уровни разделены горизонтальными линиями):

Удаление вершины

Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего «предшественника» или «преемника», в зависимости от реализации. «Предшественник» находится в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, «преемник» может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем [math]1[/math] , имеющих двух детей, предшественник или преемник будет на уровне [math]1[/math] , что делает их удаление тривиальным. Ниже представлена рекурсивная реализация алгоритма.

Будем использовать дополнительную функцию [math]\mathrm[/math] , она будет обновлять уровень вершины, которую передают в функцию, в зависимости от значения уровня дочерних вершин.

Node decreaseLevel(t : Node) shouldBe = min(t.left.level, t.right.level) + 1 if shouldBe < t.level t.level = shouldBe if shouldBe < t.right.level t.right.level = shouldBe return t

Чтобы сохранять баланс дерева необходимо делать [math]\mathrm[/math] , [math]\mathrm[/math] и [math]\mathrm[/math] для каждой вершины.

Node delete(x : V, t : Node) // x — удаляемый элемент, t — корень дерева, из которого он должен быть удален if t == [math]\varnothing[/math] return t else if x > t.value t.right = delete(x, t.right) else if x < t.value t.left = delete(x, t.left) else if leaf(t) return [math]\varnothing[/math] else if t.left == [math]\varnothing[/math] l = successor(t) t.right = delete(l.valuel, t.right) t.value = l.value else l = predecessor(t) t.left = delete(l.value, t.left) t.value = l.value // Сбалансируем дерево. Если необходимо, уменьшим поля «уровень» // у вершин на данном уровне, и затем skew и split все вершины на новом уровне t = decreaseLevel(t) t = skew(t) t.right = skew(t.right) if t.right [math] \neq\ \varnothing[/math] t.right.right = skew(t.right.right) t = split(t) t.right = split(t.right) return t

Пример удаления вершины (на рис. уровни разделены горизонтальными линиями):

Эффективность

Оценка на высоту деревьев соответствует оценке для красно-черного дерева, [math]2\cdot \log 2(N)[/math] , так как AA-дерево сохраняет структуру красно-черного дерева. Следовательно все операции происходят за [math]O(\log N)[/math] , потому что в сбалансированном двоичном дереве поиска почти все операции реализуются за [math]O(h)[/math] . Скорость работы AA-дерева эквивалентна скорости работы красно-черного дерева, но так как в реализации вместо цвета обычно хранят «уровень» вершины, дополнительные расходы по памяти достигают байта.

См. также

Источники информации

Источник