31. Деревья двоичного поиска

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

Эти структуры особенно полезны, когда исходное множество такое большое, что не рационально использовать его элементы непосредственно в качестве индексов массивов. Предполагается, что все элементы множеств являются элементами некоторого универсального множества - универсума, примером которого служит множество возможных идентификаторов в программе на языке Pascal.

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

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

На рисунке показаны два дерева двоичного поиска, представляющие одно и то же множество целых чисел

Отметим интересное свойство деревьев двоичного поиска: если составить список узлов этого дерева, обходя его во внутреннем (симметричном) порядке, то полученный список будет отсортирован в порядке возрастания (в соответствии с заданным на множестве отношением линейного порядка).

31. Нагруженные деревья

Рассмотрим специальную структуру для представления множеств, состоящих из символьных строк. Некоторые из описанных здесь методов могут работать и со строками объектов другого типа, например со строками целых чисел. Эта структура данных называется нагруженными деревьями (tries). В оригинале структура называется trie, это слово получено из букв, стоящих в середине слова "retrieval" (поиск, выборка, возврат). Устоявшегося термина для этой структуры в русской литературе пока нет. О расхождении терминологии можно судить по следующему факту: 1) в известной книге Кнут Д. Искусство программирования для ЭВМ. Т.3: Сортировка и поиск. - М.,Мир, 1978г. вместо trie используется термин бор (от слова выборка), 2) а в последнем переводе переработанного издания этой книги (Кнут Д. Искусство программирования. Т.3: Сортировка и поиск. - М., Вильямс, 2000г.) - термин луч (от слова получение).Термин нагруженные деревья соответствует смыслу этой структуры. Можно было бы применить и термин синтаксические деревья, но, хотя этот термин по своему значению и "пересекается" с термином нагруженные деревья, он имеет другую направленность.

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

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

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

Чтобы избежать коллизий слов, подобных THE и THEN, введем специальный символ $, маркер конца, указывающий окончание любого слова. Тогда только слова будут словами, но не префиксы.

Самой простой реализацией узлов нагруженного дерева будет массив node указателей на узлы с индексным множеством {А, В, ..., Z, $}.

Так как мы рассматриваем каждый узел нагруженного дерева как отображение, то можно применить любую реализацию отображений.

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