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

我正在尝试编写一种方法来从 BST 中删除元素。到目前为止，这就是我所拥有的。我不确定我是否走在正确的轨道上，或者是否有更好的方法通过使用模式匹配来匹配不同的删除情况，即：没有子项、1 个子项、2 个子项。

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

没有子节点和单个子节点的情况工作得很好，但是当要删除的节点有 2 个子节点时，我不知道如何实现这种情况。我想用其右子树上的最小项目替换该节点的值，然后删除其右子树上的最小项目。

我不太确定我理解你的逻辑remove函数正在尝试实现。通常的方法是编写一个递归函数：

• if x小于当前，删除x从左子树递归
• if x大于当前，删除x从右子树递归
• if 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功能。 merge函数的逻辑如下：

• 如果两棵树都是空的，则返回空树
• 如果剩下的是Bin(n, llst, lrst)右边是rst然后返回一棵包含n with llst在左边并（递归地）合并lrst and rst在右边（因为它们中的元素都大于n).
• 类似地，如果正确的是Bin左边是其他东西。

这不会产生balanced二叉树，但它是一个好的开始。

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

以下代码删除最大元素并将其与新树（没有最大元素）一起返回：

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)