Какое само балансирующее дерево является самым простым в функциональном программировании?

Я проектирую собственное балансировочное дерево в Haskell. Как упражнение и потому, что приятно иметь в своей задней руке.

Раньше в C и Python я предпочитал Treaps и Splay Trees из-за их простых правил балансировки. Мне всегда не нравилось R/B Trees, так как они казались больше работы, чем они стоили.

Теперь, из-за функционального характера Haskell, все, кажется, изменилось. Я могу написать функцию вставки R/B в 10 строках кода. Treaps, с другой стороны, требует обертывания для хранения генератора случайных чисел, а Splay Trees - боль делать сверху вниз.

Итак, я спрашиваю, есть ли у вас опыт работы с другими типами деревьев? Какие из них лучше подходят для сопоставления шаблонов и сверху вниз функциональных языков?

Ответ 1

Хорошо, я думаю, не было много ссылок или исследований для ответа на этот вопрос. Вместо этого я потратил время, чтобы попробовать ваши разные идеи и деревья. Я не нашел ничего лучше, чем деревья RB, но, возможно, это просто искажение поиска.

Дерево RB может быть (вставка) сбалансировано с четырьмя простыми правилами, так как показано Крисом Окасаки:

balance T (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance T (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance T a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance T a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance T a x b = T B a x b

Деревья AVL могут быть сбалансированы аналогичным образом. Однако правила также не сжимаются:

balance T (T (T a x b   dx) y c (-1)) z d (-2) = T (T a x b dx) y (T c z d  0) 0
balance T a x (T b y (T c z d   dz)   1 )   2  = T (T a x b  0) y (T c z d dz) 0
balance T (T a x (T b y c   1 )   1 ) z d (-2) = T (T a x b -1) y (T c z d  0) 0
balance T (T a x (T b y c (-1))   1 ) z d (-2) = T (T a x b  0) y (T c z d  1) 0
balance T (T a x (T b y c   _ )   1 ) z d (-2) = T (T a x b  0) y (T c z d  0) 0
balance T a x (T (T b y c   1 ) z d (-1))   2  = T (T a x b -1) y (T c z d  0) 0
balance T a x (T (T b y c (-1)) z d (-1))   2  = T (T a x b  0) y (T c z d  1) 0
balance T a x (T (T b y c   _ ) z d (-1))   2  = T (T a x b  0) y (T c z d  0) 0
balance t = t

В то время как деревья AVL швы обычно считаются уступающими деревьям RB, они, вероятно, не стоят лишних хлопот.

Деревья AA теоретически могут быть сбалансированы хорошо и легко:

balance T n (T n a x b) y c = T n a x (T n b y c) -- skew
balance T n a x (T n b y (T n c z d)) = T (n+1) (T n a x b) y (T n c z d) --split
balance T n a x b = T n a x b

Но, к сожалению, Haskell не любит перегрузку n. Возможно, что менее стандартная реализация деревьев АА, а не использование рангов, а что-то более похожее на R и B, будет работать хорошо.

Деревья Splay трудны, потому что вам нужно сосредоточиться на одном node, а не на статической структуре дерева. Это можно сделать с помощью слияния вставки и воспроизведения.

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

Ответ 2

Как вы говорите, красные черные деревья не так уж трудны в использовании. Вы указали пальцы на вид? Вам может быть интересно увеличить вашу базовую структуру данных с помощью молнии. Другое дерево, которое может показаться вам интересным, - это дерево AA это упрощение красных черных деревьев.

Ответ 3

Это тот, который уже реализован.

В Haskell реализованы мелкие реализации сбалансированных деревьев, таких как Data.Map и Data.Set. Разве они не соответствуют вашим потребностям? Не переопределяйте, не используйте повторно.

Ответ 4

Стандартная библиотека OCaml использует дерево AVL для своего функтора map. Кажется, что проще реализовать, чем дерево RB, если вы включили операцию remove.