Более сложные нелинейные структуры

До сих пор мы рассматривали деревья, представляемые в виде динамически порождаемых узлов. Теперь мы опишем деревья, которые моделируют массивы в виде законченных бинарных деревьев. Они используются в приложениях, связанных с пирамидальными структурами и турнирной сортировкой. Мы подробно остановимся на пирамидах и рассмотрим их применение в пирамидальной сортировке.

Деревья бинарного поиска реализуют списки и обеспечивают среднее время поиска порядка O(log2n). Однако на несбалансированных деревьях эффективность поисковых алгоритмов снижается. В следующем номере мы рассмотрим новый тип деревьев, называемых сбалансированными или AVL-деревьями, (по фамилиям их изобретателей Г. М. Адельсона-Вельского и Е. М. Ландиса. Прим. ред.), в которых поддерживаются неизменно хорошие поисковые характеристики бинарного дерева.

Еще одна тема, которую мы оставим на потом — это итераторы. Итераторы – мощное средство сканирования, позволяющее осуществлять прохождение нелинейных структур с помощью простых методов, применяемых обычно к линейным спискам. Здесь мы разрабатываем симметричный итератор дерева, который расширяет возможности деревьев. Это используется для реализации алгоритма сортировки с помощью дерева.

Бинарные деревья, представляемые массивами

В предыдущих разделах для построения бинарных деревьев мы использовали узлы дерева. Каждый узел имеет поле данных и поля указателей на правое и левое поддеревья данного узла. Пустое дерево представляется нулевым указателем. Вставки и удаления производятся путем динамического размещения узлов и присвоения значений полям указателей. Это представление используется для целой группы деревьев от вырожденных до законченных. В данном разделе вводится последовательное представление деревьев с помощью массивов. При этом данные хранятся в элементах массива, а узлы указываются индексами. Мы выявим очень близкое родство между массивом и законченным бинарным деревом — взаимосвязь, используемую в пирамидах и очередях приоритетов.

Вспомним, что законченное бинарное дерево глубины n содержит все возможные узлы на уровнях до n-1, а узлы уровня n располагаются слева направо подряд (без дыр). Массив A есть последовательный список, элементы которого могут представлять узлы законченного бинарного дерева с корнем A[0]; потомками первого уровня A[1] и A[2]; потомками второго уровня A[3], A[4], A[5] и A[6] и т.д. Корневой узел имеет индекс 0, а всем остальным узлам индексы назначаются в порядке, определяемом поперечным (уровень за уровнем) методом прохождения. На рис. 14 показано законченное бинарное дерево для массива A из десяти элементов.

int A[10] = {5, 1, 3, 9, 6, 2, 4, 7, 0, 8}

Рис. 14 Законченное бинарное дерево для 10-элементного массива А

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

Бинарные деревья

Эквивалентное представление в виде массива

Преимущества представляемых массивами деревьев обнаруживаются тогда, когда требуется прямой доступ к узлам. Индексы, идентифицирующие сыновей и родителя данного узла, вычисляются просто. В таблице, расположенной ниже, представлено дерево, изображенное на рис. 13. Здесь для каждого уровня указаны узлы, а также их родители и сыновья.

Для каждого узла A[i] в N-элементном массиве индекс его сыновей вычисляется по формулам:

Индекс левого сына = 2*i (неопределен при 2*i+1 > N)

Индекс правого сына = 2*i + 2 (не определен при 2*i + 2 > N)

Поднимаясь от сыновей к родителю, мы замечаем, что родителем узлов A[3] и A[4] является A[1], родителем A[5] и A[6] — A[2] и т.д. Общая формула для вычисления родителя узла A[i] следующая:

Индекс родителя = (i-1)/2 (не определен при i=0)