Базовые структуры данных. Сбалансированные деревья

Лекция 5: Базовые структуры данных. Сбалансированные деревья

0  Введение

На предыдущей лекции мы рассмотрели деревья. Основные операции над двоичными деревьями высоты h могут быть выполнены за O(h) действий. Однако возникает одна проблема: малая высота дерева не гарантируется, поэтому в худших случаях деревья не более эффективны, чем списки. Для того чтобы справится с этой проблемой, были придуманы различные методы создания и поддержки «сбалансированных» деревьев, гарантирующих высоту дерева O(log n).

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

Красно-черное дерево (red-black tree) – это двоичное дерево поиска, вершины которого раскрашены в два цвета: красный (red) и черный (black). Таким образом, в каждой вершине дополнительно хранится бит, определяющий цвет вершины.

При этом для дерева выполняются особые свойства, гарантирующие, что высота двух любых листьев различается не более чем в два раза. Благодаря этому можно говорить, что красно-черные деревья относятся к сбалансированным (balanced) деревьям.

Как и обычные, красно-черные деревья содержат указатели на родительскую вершину (p), на левого (left) и правого (right) ребенка, а кроме того есть поле цвета (color), определяющее, красная вершина или черная. Если у вершины отсутствует ребенок или родитель, то соответствующее поле содержит нулевое значение, которое для упрощения будем считать ссылкой на некоторый несуществующий фиктивный элемент, лист. Тогда все вершины дерева, содержащие ключи, будут внутренними, что упростит рассмотрение дерева.

Двоичное дерево поиска мы можем назвать красно-черным, если оно удовлетворяет следующему набору свойств (назовем их RB-свойствами):

·  каждая вершина либо красная, либо черная;

·  каждый лист (фиктивная вершина) черная;

·  если вершина красная, то оба ее ребенка черные;

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

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

Красно-черное дерево с n внутренними вершинами имеет высоту не более 2 log (n+1).

Таким образом, процедуры поиска, выделения максимального и минимального элементов, получения следующего и предыдущего элементов выполняются за время, пропорциональное высоте дерева h, то есть за O(log n).

Не все так просто с процедурами добавления и удаления элементов, так как их использование может привести к нарушению RB-свойств. Поэтому после применения указанных процедур требуется нормализация дерева. Далее будет показано, как реализовать добавление и удаление элементов за время O(log n) с сохранением RB-свойств.

1.1  Вращения

Операции добавления и удаления элементов в дерево выполняются за время O(log n), но они могут привести к нарушению RB-свойств. Поэтому после каждой операции необходимы действия по изменению структуры дерева и перекрашиванию некоторых вершин.

Для нормализации структуры дерева применяются вращения (rotations). Эта операция сохраняет свойство упорядоченности и производится над указателями, поэтому занимает время O(1). В чем же состоит операция вращения?

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

1.2  Добавление вершины

Добавление вершины в красно-черное дерево занимает время O(log n). Мы сначала используем процедуру добавления вершины в обычное двоичное дерево поиска и красим вершину в красный цвет. Это может привести к нарушению RB-свойств, поэтому после добавления требуется перекрасить некоторые вершины и произвести вращения.

Несложно заметить, что добавление красной вершины x может привести к нарушению только одного свойства: оба ребенка красной вершины должны быть черными (в нашем случае возможен вариант, когда новая красная вершина получает красного родителя). Такая ситуация может сохраняться после любого количества итераций цикла. После каждой итерации вершина поднимается вверх по дереву (если только не удалось устранить нарушение полностью; в этом случае мы выходим из цикла).

Всего возможны шесть случаев, причем три из них симметричны трем другим. Разница состоит лишь  том, является ли родитель X правым или левым ребенком своего родителя. Мы предполагаем, что дерево имеет черный корень, и будем поддерживать это свойство. Поэтому мы можем утверждать, что существует родитель родителя вершины x: родитель x красный (потому что именно этим нарушается свойство красно-черных деревьев), а красная вершина не может быть корнем нашего дерева. Кроме того, родитель родителя вершины x имеет черный цвет, так как пара x–родитель x является единственным нарушением RB-свойств.

Рассмотрим вершину, которая приходится «дядей» вершине x (y), то есть имеет того же родителя, что и родитель x. Рассмотрим возможные случаи:

·  родитель x и y красные; как уже отмечалось ранее, родитель родителя x – черный. Тогда перекрашиваем y и родителя x в черный цвет, а родительскую вершину для родителя x в красный. Теперь нарушение RB-свойств возможно только для этой вершины и ее родителя (если он красный), поэтому продолжим выполнение цикла, приняв за x эту вершину.