二叉树（非BST）三种搜索操作版本的差异与效率疑问

首先给出二叉树的类型定义：

type 'a btree = 
| Empty
| Node of 'a * 'a btree * 'a btree;;

下面是三个搜索函数的实现版本：

版本1 #

let rec bsearch x tree = 
  match tree with 
  | Empty -> Empty
  | Node (root, left, right) -> 
      if (root = x) then tree else
        match left with 
        | Empty -> bsearch x right
        | Node (_, left, _) -> bsearch x left;;

版本2 #

let rec bsearch x tree = 
  match tree with 
  | Empty -> Empty
  | Node (root, left, right) when x = root -> tree
  | Node (_, left, right) ->
    match left with
    | Empty -> bsearch x right
    | t -> bsearch x t;;

版本3 #

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

三者的核心差异 #

1. 递归特性与栈开销：版本1、2是尾递归实现，OCaml会将尾递归优化为循环结构，栈空间复杂度为O(1)；版本3是非尾递归，每一层递归都会保留栈帧，栈空间复杂度为O(h)（h为树的高度）。
2. 模式匹配风格与逻辑实现：
   • 版本1用if判断目标匹配，且遍历左子树时冗余解构了Node结构（Node (_, left, _)），写法不够简洁。
   • 版本2使用卫语句（when子句）处理目标匹配，更贴合OCaml模式匹配的惯用写法，匹配左子树时直接用t指代非空节点，代码更精炼。
   • 版本3采用"先递归搜索左子树，再根据左子树的结果决定是否搜索右子树"的逻辑，必须等待左递归的返回结果才能继续执行，这也是它无法成为尾递归的原因。

关于版本3的| t' -> t'与效率 #

• | t' -> t'并非无用分支：如果左子树中存在目标节点，bsearch x left会返回该节点（而非Empty），此时就会匹配这个分支并直接返回找到的节点，是完整逻辑的必要部分。
• 版本3确实是三者中效率最低的：一方面非尾递归带来额外的栈帧开销，树越深开销越大；另一方面相比版本1、2，它多了一次对左递归结果的模式匹配操作，额外增加了运行时的判断成本。

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