如何优化Haskell二叉搜索树find函数，将2d比较复杂度降至d+1

你原来的实现每个节点最多会执行2次数值比较，本质是因为==、<每一次判断都会触发独立的比较运算。要把比较复杂度降到d+1的水平，核心思路是单次比较获取全部分支需要的序关系信息，不需要重复执行比较操作。

Haskell的Ord类型类内置的compare函数正好满足这个需求：它接收两个可比较的值，单次比较后直接返回LT（小于）、EQ（等于）、GT（大于）三种枚举结果，你可以直接基于这个结果做分支判断，不需要多次比较。

优化后的代码实现如下：

optimized_find :: (Ord a) => Tree a -> a -> Bool
optimized_find Empty _ = False
optimized_find (Node t1 v t2) x = case compare x v of
    EQ -> True
    LT -> optimized_find t1 x
    GT -> optimized_find t2 x

优化效果说明 #

• 每个非空节点仅执行1次compare比较运算，相比原实现最多减少了一半的比较次数
• 最坏情况下搜索到深度为d的节点结束，总比较次数不超过d+1，完全符合优化预期
• 逻辑上和原实现完全等价，仅减少了冗余的比较操作，不会改变原查找逻辑的正确性

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