二叉搜索树两种搜索函数的效率对比及等价性验证

给定的二叉树类型定义 #

type 'a tree = 
  | Empty
  | Node of 'a * 'a tree * 'a tree

两个搜索函数 #

1. 函数一

let rec search x t =
  match t with
  | Empty -> Empty
  | Node(a, left, right) as t' ->
      if a = x then t'
      else 
        match search x left with
        | Empty -> search x right
        | t'' -> t''

2. 函数二

let rec search x tree = 
  match tree with 
  | Empty -> Empty
  | Node (root, left, right) as t -> 
      if (x = root) then t 
      else if (x < root) then search x left
      else search x right

等价性分析 #

这两个函数并不等价，你的判断有误。二者核心逻辑差异极大：

• 函数一完全忽略二叉搜索树（BST）的性质，不管目标值x和当前节点值的大小关系，都会先递归搜索左子树；只有左子树搜索结果为Empty时，才会去搜索右子树。
• 函数二则严格遵循BST的核心规则：左子树所有节点值小于根节点，右子树所有节点值大于根节点。它会根据x与当前根节点的大小关系，直接选择左或右子树递归搜索，不会做无用遍历。

举个简单例子：假设BST结构为Node(5, Node(3, Empty, Empty), Node(7, Empty, Empty))，搜索x=7时：

• 函数一会先遍历左子树Node(3,...)，确认找不到7后，再去遍历右子树找到目标；
• 函数二则直接判断7>5，跳过左子树，直接搜索右子树找到目标。

效率对比 #

函数二的效率远高于函数一：

• 函数二的时间复杂度为O(h)（h为树的高度），这是BST搜索的最优复杂度，每次递归只遍历树的一条路径；
• 函数一的时间复杂度在最坏情况下是O(n)（n为树的节点总数），因为它会遍历左子树的所有节点后才去遍历右子树，完全没有利用BST的性质，退化成了类似二叉树的全遍历。

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