Haskell中实现[[a]]到Set (Set a)的转换：求更高效方案

你的现有实现SetOfSet x:xs = Node Leaf (fromList x) (setOfSet xs)会生成一棵右斜树，所有节点都挂在右子树上，这种结构的查找、遍历等操作时间复杂度为O(n)，完全没发挥二叉搜索树的优势。既然输入的列表的列表已经是排序好的，我们可以用分治策略构建平衡二叉搜索树，把时间复杂度降到O(log n)。

实现思路 #

利用有序输入的特性，将列表分成左右两部分，取中间元素作为根节点，递归构建左右子树，最终得到高度平衡的Set结构。

完整代码示例 #

data Set a = Leaf | Node (Set a) a (Set a) deriving (Show)

-- 基于有序输入构建平衡的单个Set
fromList :: Ord a => [a] -> Set a
fromList [] = Leaf
fromList xs = Node (fromList left) midVal (fromList right)
  where
    len = length xs
    midIdx = len `div` 2
    left = take midIdx xs
    midVal = xs !! midIdx
    right = drop (midIdx + 1) xs

-- 高效实现列表转集合的集合
setOfSet :: Ord a => [[a]] -> Set (Set a)
setOfSet [] = Leaf
setOfSet xs = Node (setOfSet left) midSet (setOfSet right)
  where
    len = length xs
    midIdx = len `div` 2
    left = take midIdx xs
    midSet = fromList (xs !! midIdx)
    right = drop (midIdx + 1) xs

优势说明 #

• 分治构建的平衡二叉搜索树，左右子树高度差极小，所有核心操作（查找、插入、遍历）的时间复杂度均为O(log n)。
• 完全复用输入已排序的特性，无需额外排序开销，最大化利用前置条件提升效率。

内容的提问来源于stack exchange，提问作者user119374753