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

      Комментарии к записи По методу бинарного дерева отключены

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

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

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

Шаг 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 отсутствует, поэтому в данном случае искомый идентификатор не найден.

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

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

Статьи к прочтению:

[C++11] Алгоритмы — Сортировка бинарным деревом (BinarySort) Быстрая сортировка


Похожие статьи: