3.2.3. Построение таблиц идентификаторов по методу бинарного дерева

Можно сократить время поиска искомого элемента в ТИ, не увеличивая время, необходимое на ее заполнение. Для этого надо отказаться от организации таблицы в виде непрерывного массива данных.

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

Рассмотрим алгоритм заполнения бинарного дерева. Будем считать, что алгоритм работает с потоком входных данных, содержащим идентификаторы. Этот поток порождается в процессе разбора исходной программы сканером.

Первый идентификатор помещается в корень дерева. Все дальнейшие идентификаторы попадают в дерево по следующему алгоритму, записанному в словесной форме.

Шаг 1. Выбрать очередной идентификатор из входного потока данных. Если очередного идентификатора нет, то построение дерева закончено.

Шаг 2. Сделать текущим узлом дерева корневую вершину (текущий узел – узел, активный на данный момент).

Шаг 3. Сравнить очередной идентификатор с идентификатором, содержащимся в текущем узле дерева.

Шаг 4. Если очередной идентификатор меньше, то перейти к шагу 5, если равен – сообщить об ошибке и прекратить выполнение алгоритма (двух одинаковых идентификаторов в ТИ быть не должно!), если больше – то перейти к шагу 7. (Понятия «меньше» и «больше» связаны с алфавитным порядком букв в идентификаторе, со сравнением цифр и сравнением длины идентификаторов).

Шаг 5. Если у текущего узла существует смежная левая вершина, то сделать ее текущим узлом и перейти к шагу 3, иначе перейти к шагу 6.

Шаг 6. Создать новую вершину как левую вершину текущего узла, поместить в нее очередной идентификатор и вернуться к шагу 1!

Шаг 7. Если у текущего узла существует смежная правая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе перейти к шагу 8.

Шаг 8 Создать новую вершину в качестве правой вершины текущего узла, поместить в нее очередной идентификатор, и вернуться к шагу 1!

То есть, в ходе алгоритма меньшие значения идентификаторов распределяются по левым ветвям, а большие – по правым.

Пример 3.4.

Имеется поток данных в виде последовательности идентификаторов: GA, D1, M22, E, A12, BC, F. Организовать построение ТИ в виде бинарного дерева. Процесс построения указан на рис. 3.4. Русскими буквами показаны шаги построения в виде фрагментов дерева.

Рис. 3.4. Процесс построения ТИ в виде бинарного дерева

Вопрос слушателям. Каким образом по алгоритму получен любой фрагмент дерева? Какой из идентификаторов больше F или M22?

Поиск нужного элемента в дереве выполняется по алгоритму, схожему с алгоритмом заполнения дерева.

Шаг 1. Сделать текущим узлом дерева корневую вершину.

Шаг 2. Сравнить исходный идентификатор с идентификатором, содержащимся в текущем узле дерева.

Шаг 3. Если идентификаторы совпадают, то искомый идентификатор найден, алгоритм завершается, иначе перейти к шагу 4.

Шаг 4. Если искомый идентификатор меньше, то перейти к шагу 5, иначе – перейти к шагу 6.

Шаг 5. Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе искомый идентификатор не найден, алгоритм завершается.

Шаг 6. Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе искомый идентификатор не найден, алгоритм завершается.

Например, для поиска идентификатора A12 из пр. 3.4. на первом шаге корневая вершина GA принимается как текущий узел. На шаге 2 сравнивается A12 и GA. По условию шага 3 необходимо перейти к шагу 4. A12 меньше GA, поэтому надо перейти к шагу 5.

На 5 шаге текущим узлом становится вершина D1 и происходит возврат к шагу 2, т. е. искомый идентификатор A12 сравнивается с D1. Так как A12 и D1 не равны, то переход к шагу 4. A12 меньше D1 и переход к шагу 5. На пятом шаге текущим узлом становится вершина A12, находящаяся в левой ветви D1. Затем переход к шагу 2 и шагу 3. На третьем шаге алгоритм завершается, т. к. искомый идентификатор равен идентификатору в таблице идентификаторов, представленной в виде бинарного дерева.

Если искать отсутствующий идентификатор, то алгоритм также начинается от корневой вершины.

Вопрос слушателям. Как будет выглядеть поиск идентификатора D0 в бинарном дерева пр. 3.4?

Для данного метода число требуемых сравнений и форма получающегося дерева зависят от порядка поступления идентификаторов. Если предположить, что в исходной программе последовательность идентификаторов является статистически неупорядоченной (что в целом соответствует действительности), то можно считать, что построенное дерево будет невырожденным. Тогда среднее время записи T₃ = NФ(log₂ N), среднее время поиска T_n = Ф(log₂ N).

Основными недостатками такого метода построения ТИ является следующее.

1. Возможность вырождения дерева. Например, при последовательности идентификаторов A, B, C, D, E, F дерево вырождается в однонаправленный связный список.

2. Необходимость работы с динамическим выделением памяти при построении дерева.

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

В тех случаях, когда логарифмическая зависимость T₃ и T_n становится неудовлетворительной, то используются методы, связанные с применением КЭШ-памяти, или комбинированные методы.