Fast and Space Efficient Trie Searches

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

Но я всё же о тех, которые частный случай ацикличного направленного графа. Как только люди обманом заставили песок думать посредством нанесения наноскопических рун, появилась и нужда в массивах. Статические и динамические, конечно, хороши, но далеко не представляют такого же интереса, как ассоциативные. Когда как статический/динамический массив сопоставляет значения с их порядковым номером (индексом), ассоциативный инкапсулирует порядок и сопоставляет значения не индексу, а произвольному значению из фиксированного множества всех возможных ключей. Так мы, например, можем Хонде сопоставить Цивик, а von - Pavlo.

В общем случае, с этим прекрасно справляются хэшмапы. О которых я, к слову, писал здесь и здесь. А современный SwissMap ещё и показывает, как поиск может утилизировать SSE инструкции. Но не просто так существуют и древовидные структуры данных. Если в сердце хэшмап лежит проблема присвоения ключу его (желательно) уникального номера, то деревья - это скорее про уникальный путь ключа. Они как BlackRock: может, в повседневной разработке особо и незаметны, но неявно присутствуют вообще везде. Файловые системы - это практически всегда деревья. Базы данных - абсолютно RB Tree, как и Epoll в линуксе. Full text search (elastic и ему подобные) - сплошные префиксные деревья. Автокомплит, проверка правописания, IP routing, DNS, LZxx компрессоры - вообще всё на них основано. Даже мне для динамического роутинга в индиге пришлось имплементировать.

Основной принцип у деревьев виртуально прост: стоя у развилки, нам необходимо выбрать, по какому пути дальше идти. Функция выбора и определяет вид. Основных их есть несколько, и о них собственно речь и пойдёт.