OCaml 两种二叉搜索树函数比较

Question

我在 OCaml 中实现了这两个二叉搜索树搜索功能。我的问题是这些函数中哪一个是良好的 OCaml 实践并且更有效，或者它们是等价的？

给出

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

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''

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

我认为第二个是等价的，因为我们不需要与

Empty

进行另一场比赛，因为我们之前已经有了它。

Answer 1

这实际上取决于二叉树中的值是否严格排序。如果在左分支中找不到该值，您的第一个函数将搜索右分支。第二个只会跟随左 或 右分支，但不会同时跟随两者。

它们不等同。

如果我们可以在树中假设严格排序，我可能会建议以下内容，使用条件保护。

let rec search x t =
  match t with
  | Empty -> Empty
  | Node (v, _, _) when x = v -> t
  | Node (v, l, _) when x < v -> search x l
  | Node (_, _, r) -> search x r

我们可以简化为：

let rec search x = function
  | Empty -> Empty
  | Node (v, _, _) when x = v -> t
  | Node (v, l, _) when x < v -> search x l
  | Node (_, _, r) -> search x r