По методу бинарного дерева

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим в качестве примера последовательность идентификаторов GA, Dl, M22, Е, А12, ВС, F. На рис. 2 проиллюстрирован весь процесс построения бинарного дерева для этой последовательности идентификаторов.

Рис. 2. Пошаговое заполнение бинарного дерева для последовательности идентификаторов GA, D1, М22, Е, А12, ВС, F

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

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

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

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

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

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

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

Например, проведем поиск в дереве (см. рис. 2) идентифи­катора А12. Берем корневую вершину (она становится текущим узлом), сравни­ваем идентификаторы GA и А12. Искомый идентификатор меньше – текущим узлом становится левая вершина D1. Опять сравниваем идентификаторы. Иско­мый идентификатор меньше – текущим узлом становится левая вершина А12. При следующем сравнении искомый идентификатор найден.

Если искать отсутствующий идентификатор, например A11, то поиск опять пойдет от корневой вершины. Сравниваем идентификаторы GA и А11. Искомый идентификатор меньше – текущим узлом становится левая вершина D1. Опять сравниваем идентификаторы. Искомый идентификатор меньше – текущим уз­лом становится левая вершина А12. Искомый идентификатор меньше, но левая вершина у узла А12 отсутствует, поэтому в данном случае искомый идентифика­тор не найден.

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

В целом метод бинарного дерева является довольно удачным механизмом для организации таблиц идентификаторов. Он нашел свое применение в ряде ком­пиляторов. Иногда компиляторы строят несколько различных деревьев для идентификаторов разных типов и разной длины.