Разбиение дерева по разбивающему элементу

Для данной вершины дерева v разбиение сбалансированного дерева поиска T на два сбалансированных дерева поиска T₁ и T₂ таких, что все элементы в T₁ меньше или равны v, и все элементы в T₂ больше или равны v.

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

Пусть высота дерева T₀ равна s₀. Пусть высоты деревьев, которые мы будем сливать, например, с деревом T₀ имеют значения s₁,…,s_K. Последовательность S={s₀,…,s_K } строго возрастающая, s_K£h, где h – высота дерева T. В силу алгоритма слияния деревьев с использованием стыковочного элемента, слияние двух деревьев X₁ и X₂ с высотой h₁ и h₂ дает дерево высотой MAX(h₁, h₂) или MAX(h₁, h₂)+1.

Из чего, по индукции, сразу получаем, что после добавления очередного дерева T_i к дереву T₀, высота дерева T₀ будет равной либо s_i, либо s_i+1. Тогда, время работы всего алгоритма T=O(|s₀- s₁|+|s₁- s₂|+…+|s_K-1- s_K|)=O(log₂ N), где N – количество вершин в суммарном дереве.

Итак, верна следующая теорема

Теорема. Для данной вершины v сбалансированного дерева поиска T разбиение на два сбалансированных дерева поиска T₁ и T₂ таких, что все элементы в T₁ меньше или равны v, и все элементы в T₂ больше или равны v. может быть произведено указанным алгоритмом за время = O(log₂ N), где N – суммарное количество вершин в деревьях T₁ и T₂.

Лекция 10

Красно-черные деревья

Красно-черными деревьями называют бинарные деревья поиска, у которых для каждой вершины добавляется дополнительное свойство: вершина является черной или красной. При этом требуется выполнение следующих свойств:

· корень дерева – черный

· у каждой красной вершины потомки – черные

· в любых двух ветвях от корня до листа количество содержащихся черных вершин равно

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

Вершины, отличные от фиктивных, называются внутренними. Будем далее называть листьями вершины, все потомки которых – фиктивные. При определении высоты дерева фиктивные вершины учитывать не будем.

Например, для задания одной вершины красно-черного дерева целых чисел в языке С можно использовать следующую структуру

Typedef struct SBTree_

{

Int IsRed;

Int value;

struct STree_ *par;

struct STree_ *left, *right;

} SBTree;

здесь указатель par указывает на родительский элемент данной вершины, а left и right – на двух потомков, которых традиционно называют левым и правым. Целая переменная IsRed указывает – является ли данная вершина красной. Величина value называется ключом вершины.

Дата добавления: 2015-10-30