Haskell中如何向不相交线段树插入区间？

本文定义的不相交线段树是二叉搜索树类型的线段树，节点值为两两分离的区间(a,b)（a<=b，代表时间段），「分离」指区间之间不允许相邻。需要实现区间插入函数，通过合并重叠或相邻区间维持数据不变量，以下是原代码的修正方案：

原代码问题 #

原代码在插入区间与根区间重叠/相邻时直接返回undefined，未处理合并逻辑，导致无法维护线段树的性质。

修正后的实现代码 #

data SegTree = Empty | Node (Int, Int) SegTree SegTree deriving (Eq, Show)

-- | 判断前一个区间是否严格早于后一个区间（无重叠、不相邻）
isStrictlyBefore :: (Int, Int) -> (Int, Int) -> Bool
(_, b1) `isStrictlyBefore` (a2, _) = b1 < a2

-- | 合并两个区间为覆盖两者的最小区间
combine :: (Int, Int) -> (Int, Int) -> (Int, Int)
combine (a1,b1) (a2,b2) = (min a1 a2, max b1 b2)

-- | 插入区间并合并重叠/相邻区间，维持不相交线段树性质
insertByMerge :: (Int, Int) -> SegTree -> SegTree
insertByMerge x' Empty = Node x' Empty Empty
insertByMerge x' (Node x l r)
  | x' `isStrictlyBefore` x = Node x (insertByMerge x' l) r
  | x `isStrictlyBefore` x' = Node x l (insertByMerge x' r)
  | otherwise =
      let merged = combine x x'
          -- 先合并左子树中所有与merged重叠/相邻的区间
          leftMergedTree = insertByMerge merged l
      in case leftMergedTree of
           Empty -> insertByMerge merged r
           Node mergedLeft _ _ -> insertByMerge mergedLeft r

核心逻辑说明 #

1. 严格前后判断：若插入区间严格早于当前节点区间，递归插入左子树；若当前节点区间严格早于插入区间，递归插入右子树。
2. 重叠/相邻处理：
   • 合并当前节点区间与插入区间，得到merged
   • 将merged插入左子树，完成左子树中所有可合并区间的整合，返回的树的根节点为包含左子树可合并部分的大区间
   • 将该大区间插入右子树，完成右子树中相邻/重叠区间的合并
3. 性质维持：递归过程自动保证最终树的所有节点区间两两分离，左子树区间严格早于根节点，右子树区间严格晚于根节点。

测试示例 #

-- 初始树：包含(3,4)、(5,10)、(12,15)三个分离区间
initialTree = Node (5,10) (Node (3,4) Empty Empty) (Node (12,15) Empty Empty)
-- 插入(4,6)，合并后得到(3,10)，最终树为Node (3,10) Empty (Node (12,15) Empty Empty)
result1 = insertByMerge (4,6) initialTree

-- 初始树：包含(5,10)、(11,15)两个相邻区间
initialTree2 = Node (5,10) Empty (Node (11,15) Empty Empty)
-- 插入(8,12)，合并后得到(5,15)，最终树为Node (5,15) Empty Empty
result2 = insertByMerge (8,12) initialTree2

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