递归调用与匹配用于二叉树搜索操作。

huangapple go评论75阅读模式
英文:

Recursive calls with match for operation search on binary tree

问题

以下是您提供的内容的中文翻译:

我已经找到了一个在二叉树中搜索值并返回包含该值的节点的解决方案。因此,时间复杂度预计为O(n)。

这是我的解决方案:

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

这是我找到的解决方案,但我认为我的更高效且易读:

let rec search x t =
  match t with
  | Empty -> Empty
  | Node(v, l, r) ->
    if v = x then t
    else 
      match search x l with
      | Empty -> search x r
      | t' -> t'

我的解决方案更好还是我漏掉了什么?

供参考,tree 类型的定义如下:

type 'a tree = 
  | Empty
  | Node of 'a * 'a tree * 'a tree
英文:

I have come across a solution to the problem of searching a value in the binary tree and returning the node of that residing value. The time complexity is thus expected to be O(n).

This is my solution to the problem:

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

and this is the solution I found, but I think mine is more efficient and readable:

let rec search x t =
  match t with
  | Empty -> Empty
  | Node(v, l, r) ->
    if v = x then t
    else 
      match search x l with
      | Empty -> search x r
      | t' -> t'

Is my solution better or am I missing something?

For reference, the definition of the tree type:

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

答案1

得分: 2

这些在功能上并不等同。

你的函数仅在左分支本身为Empty时才搜索右分支,而不是在搜索该分支的结果为Empty时。

考虑一下:

# let leaf v = Node (v, Empty, Empty) in
  search 4 @@ Node (2, leaf 1, leaf 4);;
- : int tree = Empty

你可能想要:

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

现在:

# let leaf v = Node (v, Empty, Empty) in
  search 4 @@ Node (2, leaf 1, leaf 4);;
- : int tree = Node (4, Empty, Empty)

另一个想法是,你可能想创建一个search_opt函数,它返回一个option类型,其中None表示没有找到匹配项。

let rec search_opt x = 
  function 
  | Empty -> None
  | Node (root, _, _) as tree when x = root -> Some tree
  | Node (_, left, right) ->
    match search_opt x left with
    | None -> search_opt x right
    | t -> t

假设我们有一棵树:let t = Node (2, Node (5, Node (7, leaf 1, leaf 6), leaf 10), Node (8, leaf 3, leaf 4)

          ------2------
         /             \
     ---5---         ---8---
    /       \       /       \
  -7-       10     3         4
 /   \
1     6

如果我计算 search_opt 3 t,那么会分解为:

search_opt 3 t
  search_opt 3 (Node (5, Node (7, leaf 1, leaf 6), leaf 10))
    search_opt 3 (Node (7, leaf 1, leaf 6))
      search_opt 3 (Node (1, Empty, Empty))
        search_opt 3 Empty -> None
        search_opt 3 Empty -> None
    search_opt 3 (Node (10, Empty, Empty))
      search_opt 3 Empty -> None
      search_opt 3 Empty -> None
  search_opt 3 (Node (8, leaf 3, leaf 4))
    search_opt 3 (Node (3, Empty, Empty)) -> Some (Node (3, Empty, Empty))
英文:

These are not equivalent in functionality.

Your function only searches the right branch if the left branch is itself Empty, and not if the result of searching that branch is Empty.

Consider:

# let leaf v = Node (v, Empty, Empty) in
  search 4 @@ Node (2, leaf 1, leaf 4);;
- : int tree = Empty

You might have meant:

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

Now:

# let leaf v = Node (v, Empty, Empty) in
  search 4 @@ Node (2, leaf 1, leaf 4);;
- : int tree = Node (4, Empty, Empty)

An additional thought is that you may want to create a search_opt function which returns an option type, where None indicates that no match was found.

let rec search_opt x = 
  function 
  | Empty -> None
  | Node (root, _, _) as tree when x = root -> Some tree
  | Node (_, left, right) ->
    match search_opt x left with
    | None -> search_opt x right
    | t -> t

Let's say we have a tree: let t = Node (2, Node (5, Node (7, leaf 1, leaf 6), leaf 10), Node (8, leaf 3, leaf 4).

          ------2------
         /             \
     ---5---         ---8---
    /       \       /       \
  -7-       10     3         4
 /   \
1     6

If I evaluate search_opt 3 t, then that breaks down something like:

search_opt 3 t
  search_opt 3 (Node (5, Node (7, leaf 1, leaf 6), leaf 10))
    search_opt 3 (Node (7, leaf 1, leaf 6))
      search_opt 3 (Node (1, Empty, Empty))
        search_opt 3 Empty -> None
        search_opt 3 Empty -> None
    search_opt 3 (Node (10, Empty, Empty))
      search_opt 3 Empty -> None
      search_opt 3 Empty -> None
  search_opt 3 (Node (8, leaf 3, leaf 4))
    search_opt 3 (Node (3, Empty, Empty)) -> Some (Node (3, Empty, Empty))

huangapple
  • 本文由 发表于 2023年4月11日 06:05:11
  • 转载请务必保留本文链接:https://go.coder-hub.com/75981079.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定