На этом шаге мы рассмотрим AA-деревья.
- Определение (по [1, с. 660-661]).
- AA-дерево - это сбалансированное дерево, которое добавляет к определению красно-чёрного дерева дополнительное условие:
левый дочерний узел не может быть красным.
Введённое ограничение существенно упрощает алгоритмы для работы с красно-чёрными деревьями по двум причинам:
- (1) устраняется приблизительно половина случаев реструктуризации;
- (2) упрощается алгоритм операции remove() в силу устранения "раздражающего" случая.
Именно, если у внутреннего узла имеется только один дочерний узел, он должен быть правым красным дочерним узлом, потому что левые красные дочерние узлы теперь запрещены, а один чёрный дочерний узел нарушит свойство (4) красно-чёрных деревьев (каждый путь от узла до NULL-указателя должен содержать одно и то же число чёрных узлов). В результате мы всегда можем заменить внутренний узел наименьшим узлом из его правого поддерева. Этот наименьший узел будет либо листом, либо красным дочерним узлом, и его легко обойти и удалить.
Для реализации представим информацию о сбалансированности другим способом. Вместо того, чтобы хранить цвет каждого узла, мы будем сохранять уровень узла.
Уровень узла представляет собой число левых связей на пути к сигнальному узлу nullNode (напомним, что вместо NULL-указателя мы используем узел nullNode; этот узел всегда будет чёрным) и может быть:
- (1) уровнем 1, если узел является листом;
- (2) уровнем своего родителя, если узел красный;
- (3) уровнем на 1 меньше уровня своего родителя, если узел чёрный.
Результатом будет AA-дерево.
При преобразовании структурных требований из цветов в уровни мы знаем, что левый дочерний узел должен быть на один уровень ниже, чем его родитель (но не более).
Горизонтальная связь - это соединение между узлом и дочерним узлом с одинаковыми уровнями. Цветовые свойства подразумевают следующее:
- (1) горизонтальные уровни являются правыми уровнями (потому что только правые дочерние узлы могут быть красными);
- (2) не могут существовать две последовательных горизонтальных связи (потому что не может быть двух последовательных красных узлов);
- (3) узлы на уровне 2 или выше должны иметь по два дочерних узла;
- (4) если узел не имеет правой горизонтальной связи, то его два дочерних узла находятся на одном уровне.
Поиск в AA-дереве осуществляется с помощью обычного алгоритма.
Повороты дерева решают все возникающие проблемы.
Замечание (по [1, с. 669]). AA-деревья используются для эффективной реализации классов set и map из библиотеки STL.
(1)Уайс М.А. Организация структур данных и решение задач на C++. - М.: ЭКОМ Паблишерз, 2008. - 896 с.
На следующем шаге мы рассмотрим несколько демонстрационных примеров.
