Поиск данных с помощью красно-черных и AVL-деревьев — это поиск данных при помощи производных от бинарного дерева сортировки.
Введение
Двоичное дерево является бинарным деревом поиска при соблюдении следующих условий:
- Левое поддерево каждого узла не может считаться пустым, если значения всех узлов в левом поддереве будут меньше значения его корневого узла.
- Правое поддерево каждого узла не может считаться пустым, если значение всех узлов в правом поддереве больше, чем значение его корневого узла.
- Левое и правое поддеревья каждого узла также считаются двоичными деревьями поиска.
- Не присутствуют узлы с одинаковыми значениями ключа.
Как правило, двоичный связанный список применяется как структура хранения двоичного дерева. Бинарное упорядоченное дерево можно пройти для того, чтобы получить упорядоченную последовательность ключевых слов. Неупорядоченную последовательность можно преобразовать в упорядоченную последовательность за счет формирования бинарного дерева поиска.
Процессом формирования дерева является процесс поиска неупорядоченных последовательностей. Любой новый вставленный узел может считаться новым листовым узлом в бинарном дереве поиска. При вставке можно не перемещать другие узлы, а просто изменить указатель узла с пустого на непустой. Сложность поиска, вставки и удаления равняется высоте дерева, и ожидается равной:
O (log n).
Поиск данных с помощью красно-черных и AVL-деревьев
В красно-черном дереве баланс может быть достигнут при помощи поддержания раскраски вершин в пару цветов, а именно, в красный и черный, которые подчиняются следующим правилам:
- Красная вершина не должна быть сыном красной вершины.
- Черная глубина любого листа должна быть одинаковой. Черной глубиной является количество черных вершин на пути из корня.
- Корень дерева должен быть черным.
Специальные null-вершины, замещающие отсутствующих потомков, считаются черными. На рисунке ниже приведен пример красно-черного дерева.
Рисунок 1. Красно-черное дерево. Автор24 — интернет-биржа студенческих работ
Далее следует рассмотреть, какой может быть самая большая глубина правильно построенного красно-черного дерева, имеющего «n» вершин. Предположим, что наиболее глубокий лист находится на глубине «h». Тогда согласно первому правилу, как минимум половина вершин на пути от корня должны быть черными. Это означает, что черная высота дерева должна быть не меньше половины «h». Следует заметить, что в подобном дереве должно быть не меньше, чем:
2^(h/2) -1
черных вершин. Поскольку у каждой черной вершины с черной глубиной «k», если она не является листом, обязано быть минимально два потомка с черной глубиной «k+1». Тогда:
2^(h/2) -1 ≤ n или h ≤ 2*log2(n+1).
Все главные операции с красно-черным деревом могут быть реализованы за O(h), то есть O(log n), согласно приведенному выше. Классическая реализация базируется на рассмотрении значительного количества случаев и довольно сложно воспринимается. Известны более простые и понятные версии, в которых простота в сравнении с классической реализацией может быть получена за счет ориентации на понятность, а не на оптимизацию количества элементарных модификаций дерева (вращений).
Для того чтобы реализовать этот вид сбалансированных деревьев, следует в каждой из вершин хранить дополнительно один бит информации, кодирующий цвет. Иногда это может вызвать большие трудности из-за выравнивания. В этом случае лучше применять структуры без дополнительных требований к памяти.
Принцип красно-черных деревьев повсеместно используется при реализации стандартных библиотек, а также в различных вариантах применяется в ядре Linux, например, для организации очередей запросов. И конечно этот принцип используется во многих других системах в аналогичных случаях. Красно-черные деревья имеют тесные связи с B-деревьями, даже можно утверждать, что они являются идентичными B-деревьям четвертого порядка.
AA-дерево является модификацией красно-черного дерева, в которой имеется дополнительное ограничение, а именно, красная вершина способна быть лишь правым сыном. Из-за этого дополнительного ограничения, операции могут быть реализованы более просто, чем у красно-черного дерева, в частности, за счет сокращения числа рассматриваемых случаев. Оценка на высоту деревьев должна оставаться прежней, а именно:
2*log2(n).
Эффективность по времени у них получается примерно одинаковой, но поскольку в реализации вместо цвета, как правило, сохраняют другую характеристику («уровень» вершины), расходы по памяти могут достигать одного байта.
AVL(АВЛ)-дерево получило свое название по фамилиям создавших его советских математиков Г.М. Адельсон-Вельского и Е.М. Ландиса. Данная версия предполагает наложение на дерево своего ограничения, а именно, у каждой вершины высоты левого и правого поддеревьев могут иметь отличия не более чем на единицу.
Реализация, подобно красно-черному дереву, базируется на разборе случаев и является достаточно сложной для понимания и обладает сложностью O(log(n)) на все главные операции. Для обеспечения нормальной работы следует сохранять в каждой из вершин разницу между высотами левого и правого поддеревьев. Поскольку она не может быть больше единицы, достаточно отводить два бита на каждую вершину.
У декартова дерева, если изображать его на плоскости, ключ будет соответствовать x-координате вершины (за счет упорядоченности). Тогда можно определить и y-координату, именуемую высотой, которая будет иметь также дополнительное свойство, то есть, высота вершины больше высоты детей.
Реализация операций в этом варианте считается простой и логичной, и это сделало данную структуру очень любимой в спортивном программировании. По результатам тестирования она получила признание как наиболее эффективная по времени среди красно-черных, AA и АВЛ деревьев. Но, к сожалению, она имеет достаточно большие накладные расходы по памяти, а именно, от двух до четырех байта на вершину на хранение высоты, и не может применяться там, где требуется гарантированная производительность (к примеру, в ядре операционной системы).
