Cтраница 1
Бинарная версия исчисления предикатов ( § § 3.1.4, 3.1.6) привела к графическим обозначениям через семантические сети ( см. разд. [1]
Громоздкий, поддерживаемый, в основном, в Unix, бинарные версии допускают только восемь бит на пиксель. [2]
В этом разделе мы рассмотрим деревья поиска, которые позволяют использовать разряды ключей для проведения поиска подобно DST-деревьям, но ключи которых упорядочены, что позволяет поддерживать рекурсивные реализации функции sort и других функций таблиц символов, как это делалось в отношении BST-деревьев. Основная идея заключается в хранении ключей только в нижней части дерева, в листьях. Результирующая структура данных обладает рядом полезных свойств и служит основой для нескольких эффективных алгоритмов поиска. Впервые структура была создана Брианде ( Briandais) в 1959 г., и поскольку она оказалась удобной для поиска ( re / r / eval), в 1960 г. Фредкин ( Fredkin) применил к ней специальное название trie. С некоторой долей юмора обычно это слово произносится как трай-и ( try - попытка, англ. Вероятно, в соответствии с принятой в книге терминологией, подобного рода деревья следовало бы называть trie - деревьями бинарного поиска, тем не менее, повсеместно используется термин trie - дерево и все его понимают. В этом разделе рассматривается базовая бинарная версия, в разделе 15.3 - важную вариацию, а в разделах 15.4 и 15.5 - базовую версию trie - деревьев со многими путями и ее вариации. [3]