从F#中的二进制搜索树中删除元素

Question

我试图编写一个方法，从BST中删除一个元素。到目前为止，这就是我所拥有的。我不确定我是否在正确的轨道上，或者是否有更好的方法通过使用模式匹配来匹配不同的删除案例，即:没有孩子，一个孩子，两个孩子。

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);;

没有子节点和单个子节点的情况可以很好地工作，但是当要删除的节点有两个子节点时，我想不出如何实现这种情况。我希望将该节点的值替换为其右侧子树上最小的项，然后删除其右侧子树上的最小项。

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)

编辑下面的内容实际上不起作用！这几乎是完成的，但是您需要添加merge函数。合并函数的逻辑如下：

• 如果两个树都是空的，则返回空树。
• 如果左边是Bin(n, llst, lrst)，右边是rst，那么返回一个树，其中包含n，左边有llst，右边(递归)合并了lrst和rst (因为它们中的元素都大于n)。
• 类似地，如果右边是Bin，那么左就是其他任何东西。

这不会产生一个平衡的二叉树，但这是一个良好的开端。

编辑：我认为最简单的选择可能是编写两个函数--一个函数删除树的最大元素，另一个函数删除树中最小的元素(合并时，只需调用这两个函数中的一个)。这可能比编写一个完全通用的删除函数更容易。

下面删除最大的元素并返回它，以及一个新的树(没有最大的元素)：

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

我遵循了托马斯在他的帖子中提到的步骤，我想出了这样的解决方案：

// 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)