从 F# 中的二叉搜索树中删除一个元素

Question

我正在尝试编写一种从 BST 中删除元素的方法。到目前为止，这就是我所拥有的。我不确定我是否在正确的轨道上，或者是否有更好的方法通过使用模式匹配来匹配不同的删除案例，即：no children, 1 child, 2 child仁.

type 'a bst = NL | BinTree of 'a * 'a bst * 'a bst;;

let rec smallest = function
    | NL -> failwith "tree is empty"
    | BinTree(m, lst, rst) -> if lst = NL then BinTree(m, lst, rst)
                              else smallest lst;;

let rec smallest2 = function
    | NL -> failwith "tree is empty"
    | BinTree(m, lst, rst) -> if lst = NL then m
                              else smallest2 lst;;

let rec rem2 = function
    | NL -> NL
    | BinTree(m, NL, NL) -> NL
    | BinTree(m, NL, rst) -> rst
    | BinTree(m, lst, NL) -> lst
    | BinTree(m, lst, rst) -> BinTree(smallest2 rst, lst, rst);;


let rec rem x = function
    |NL -> failwith "Node doesn't exit"
    |BinTree(m, lst, rst) -> if m = x then rem2 (BinTree(m, lst, rst)) 
                             elif m < x then BinTree(m, lst, rem x rst) 
                             else BinTree(m, rem x lst, rst);;

没有children和单个child的情况完美运行，但是当要删除的节点有2个children时，我不知道如何实现案件。我想用它右子树上的最小项替换该节点的值，然后删除其右子树上的最小项。

Answer 1

我不太确定我是否理解您的 remove 函数试图实现的逻辑。通常的做法是编写一个递归函数：

如果x小于当前，递归从左子树中移除x
如果x大于当前，递归地从右子树中移除x
如果x等于当前，则丢弃当前节点并合并两棵树

在 F# 中对此进行编码的方法是使用模式匹配编写递归函数 - 与您编写的函数非常相似：

let rec remove x = function
  | NL -> NL
  | BinTree(m, lst, rst) when x = m -> merge lst rst
  | BinTree(m, lst, rst) when x < m -> BinTree(m, remove x lst, rst)
  | BinTree(m, lst, rst) (* x > m *) -> BinTree(m, lst, remove x rst)

[EDIT 下面实际上是行不通的！] 这样就差不多完成了，但是还需要添加 merge 函数。合并函数的逻辑如下：

如果两棵树都是空的，return空树
如果左边是 Bin(n, llst, lrst) 右边是 rst 那么 return 一棵包含 n 的树，左边是 llst 并且（递归）合并右边的lrst和rst（因为两者中的元素都大于n）。
同样，如果右边是 Bin，左边是其他任何东西。

这不会生成平衡二叉树，但这是一个好的开始。

编辑：我认为也许最简单的选择是编写两个函数——一个删除树中最大的元素，一个删除树中最小的元素（然后在合并时，你可以只调用这两个之一）。这可能比编写一个完全通用的删除函数更容易。

下面删除最大的元素并returns它，连同一棵新树（没有最大的元素）：

let rec remLargest = function
  | NL -> failwith "Tree was empty!"
  | BinTree(m, l, NL) -> m, l
  | BinTree(m, l, r) -> 
      let res, newR = remLargest r
      res, BinTree(m, l, newR)

Answer 2

我按照 Tomas 在他的 post 中描述的步骤进行了操作，并想出了这个解决方案：

// BST - binary search tree
type BST<'a when 'a: comparison> = | Leaf
                                   | Node of BST<'a> * 'a * BST<'a>

let rec rmMaxBST = function
    | Leaf              -> failwith "Tree was empty"
    | Node(tL, x, Leaf) -> x, tL
    | Node(tL, x, tR  ) -> let m, newTR = rmMaxBST tR
                           m, Node(tL, x, newTR)

let rec rmMinBST = function
    | Leaf              -> failwith "Tree was empty"
    | Node(Leaf, x, tR) -> x, tR
    | Node(tL,   x, tR) -> let m, newTL = rmMinBST tL
                           m, Node(newTL, x, tR)

let mergeBST t1 t2 =
    match t1, t2 with
    | (Leaf, Leaf)      -> Leaf
    | (t1,   Leaf)      -> let x, t = rmMaxBST t1
                           Node(t, x, Leaf)               
    | (t1,   t2  )      -> let x, t = rmMinBST t2
                           Node(t1, x, t)              

let rec delBST x = function
    | Leaf                       -> Leaf
    | Node(tL, a, tR) when x < a -> Node(delBST x tL, a,          tR)
    | Node(tL, a, tR) when a < x -> Node(         tL, a, delBST x tR)
    | Node(tL, _, tR)            -> mergeBST tL tR

我在 REPL 中试过这个：

> delBST 3 Leaf;;

val it : BST<int> = Leaf

> delBST 3 (Node(Leaf, 4, Leaf));;

val it : BST<int> = Node (Leaf,4,Leaf)

> delBST 3 (Node(Leaf, 3, Leaf));;

val it : BST<int> = Leaf

> delBST 3 (Node(Node(Leaf, 1, Leaf), 3, Node(Leaf, 5,Leaf)));;

val it : BST<int> = Node (Node (Leaf,1,Leaf),5,Leaf)

> delBST 1 (Node(Node(Leaf, 1, Leaf), 3, Node(Leaf, 5,Leaf)));;

val it : BST<int> = Node (Leaf,3,Node (Leaf,5,Leaf))

> delBST 5 (Node(Node(Leaf, 1, Leaf), 3, Node(Leaf, 5,Leaf)));;

val it : BST<int> = Node (Node (Leaf,1,Leaf),3,Leaf)

从 F# 中的二叉搜索树中删除一个元素

Delete an element from a binary search tree in F#

f#

types

binary-search-tree