#algo

Деревья в алгоритмах 1/2.

В алгоритмах часто используются различные деревья (как графовый термин) в виде различных структур данных. Стандартный пример это деревья поиска или кучи. Однако разновидностей структур данных, которые решают те или иные задачи, и в качестве базы (или хотя бы в названии) содержат в себе дерево очень много. Давайте на них и посмотрим.
Опустим подробные описания чего-то дефолтного вроде avl-деревьев, красно-чёрных, или бора (trie). Может только увидим их какие-то прокачаные версии. И не будем особо рассматривать персистентные сд. Там конечно всё очень круто, но для обзорного поста по многообразию ту мач.

Мне идейно очень нравится декартово дерево (пусть оно и довольно известно). Тут и все свойства обычного bst, и это в некотором роде вероятностная структура данных. А если писать неявное, то появляется возможность делать много разных операций как у дерева отрезков, но с большей вариативностью: перемещать части массива данных, менять местами чёт/нечёт и при желании даже копировать отрезки (с персистентной версией).
Splay-деревья тоже bst но обладают замечательным свойством: элементы, которые ищут чаще, со временем оказываются выше, что позволяет тратить меньше времени на их поиск в будущем. Хз, как часто они используются, но в вакууме свойство очень приятное.
Scapegoat tree в отличие от других bst старается не хранить в нодах ничего кроме key-value и указателей на детей и вместо небольшой перебалансировки на каждую операцию делает большие перебалансировки поддеревьев, но редко.

Рядом с обычными bst есть различные версии B-деревьев, которые активно используются в базах данных и файловых системах. Стандартное B-дерево это просто обобщение bst, где разрешается иметь более двух детей/элементов в ноде, что позволяет лучше работать с кешами + ускорить операции работы с большими блоками данных. Следующая версия B-дерева это B+-дерево, которое имеет немного другую структуру и быстрее работает при последовательном обходе. Тут же можно найти B*-tree (которое пытается плотнее упаковывать данные) и B*+-tree (которое, неожиданно, комбинирует фичи двух прошлых). Известными частными случаями B+-tree являются 2-3 и 2-3-4 деревья. Есть ещё какие-то чуть-чуть апдейченные версии вроде counted b-tree.

Далее идут различные боры (или префиксные деревья). Из интересного тут есть цифровые боры, которые позволяют работать с множеством чисел асимптотически эффективнее, чем со стандартными bst (в основном используя факт о максимально значении в множестве). Например это Van Emde Boas tree, X-fast trie и Y-fast trie (эти три умеют делать стандартные операции bst с лучшей асимптотикой, хотя может с памятью похуже), Fusion tree (а это в несколько новых операций). А есть вообще упоротые штуки вроде Hash Array Mapped Trie. Видел ещё ternary search tree, которое бор с не более чем тремя детьми. Это достигается введением нод разного типа и особых правил с ними. При использовании вы иногда просто юзаете ноды как ребро, опуская символ из неё. Ещё есть сжатые боры вроде Radix trie/Patricia tree.

Ещё есть всякие сд, позволяющие эффективно работать со строками Например стандартное суффиксное дерево. Идея у него очень простая: выписываем в бор все суффиксы строк вашего множества, после чего можно очень быстро искать различные подстроки. Даже можно искать строки с опечатками, правда с некоторыми ограничениями (если опечатка в начале, всё ломается). Потому есть специализированные структуры данных вроде BK-tree. Ещё довольно частым кейсом является код Хаффмана.