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

Рассмотрим возможные случаи:

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

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

·  если w – черная, левый ее ребенок красный, а правый – черный. Можно поменять цвета w и ее левого ребенка, а затем применить правое вращение (RB-свойства будут сохранены). Теперь братом вершины x будет черная вершина с правым красным ребенком.

·  Если w – черная, а ее правый ребенок красный. Произведя левое вращение вокруг родителя w, можно удалить лишнюю черноту у x (для этого перекрасим w в цвет ее родителя, родителя w и ее правого ребенка в черный). Положим x, равное указателю на корень дерева, дабы выйти из цикла.

Сколько же нужно времени на выполнение операции удаления элемента из красно-черного дерева? Удаление из двоичного дерева поиска занимает O(log n). При восстановлении RB-свойств может возникнуть четыре ситуации, причем три из них (1, 3, 4) выполняются за время O(1) и приводят максимум к трем вращениям, а операция 2 может привести к повторной итерации, но вершина x сдвигается к корню дерева, поэтому максимальное количество итераций – O(log n). Значит, время выполнения операции удаления – O(log n), и при этом происходит не более трех вращений.

2  Б-деревья

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

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

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

Зачем же нужны Б-деревья? Чтобы это понять, рассмотрим основные отличия оперативной памяти от магнитных дисков.

2.1  Структуры данных на диске

Компьютер используется для обработки информации. Для того, чтобы выполнять свое предназначение, ему необходимо где-то эту информацию хранить. Используются различные виды памяти. Оперативная память представляет собой набор микросхем, позволяющих содержать определенное количество информации. Однако цена такой памяти довольно высока по сравнению с устройствами вторичной памяти (чаще всего это так называемые жесткие диски), которые зачастую позволяют хранить во много раз большие объемы информации.

Магнитная головка осуществляет запись и считывание информации с магнитной поверхности диска. Она может перемещаться вдоль радиуса диска, после чего осуществляется запись или считывание данных с дорожек, коими являются концентрические окружности на поверхности. Обычно, дорожка делится на определенное число равных секторов. Ввод/вывод осуществляется целыми секторами. На то, чтобы найти необходимый сектор, тратится время, называемое временем доступа. После того, как сектор найдет, обмен информацией осуществляется довольно быстро, зачастую обработка информации занимает намного меньше времени, чем ее поиск. Поэтому при оценке качества алгоритма мы будем учитывать:

·  число обращений к диску;

·  время вычислений.

Мы рассматриваем диск как большой участок памяти, работа с которым происходит по схеме ПРОЧИТАТЬ(x) перед обработкой и ЗАПИСАТЬ(x) после изменения x.