Хорошо, я думаю, что не было много ссылок или исследований для ответа на этот вопрос.Вместо этого я потратил время, чтобы попробовать ваши разные идеи и деревья.Я не нашел ничего лучше деревьев 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
Но, к сожалению, Хаскеллу не нравится перегрузка n.Вполне возможно, что менее стандартная реализация деревьев АА, не использующая ранги, но что-то более похожее на R и B., будет работать хорошо.
Splay-деревья сложны, потому что вам нужно сосредоточиться на одном узле, скореечем статическая структура дерева.Это можно сделать с помощью слияния insert и splay .
Treaps также непросто сделать в функциональной среде, поскольку у вас нет глобального генератора случайных чисел, но вам нужно хранить экземпляры вкаждый узел.Это может быть решено с помощью , оставляя задачу генерации приоритетов клиенту , но даже тогда вы не можете выполнить сравнение приоритетов с помощью сопоставления с образцом.