从F#中的二进制搜索树中删除元素 [英] Delete an element from a binary search tree in F#

问题描述

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

I'm trying to write a method to delete an element from a BST. So far, this is what I have. I'm not sure if I'm on the right track or if there is a better way to do it by using pattern matching to match the different delete cases ie: no children, 1 child, 2 children.

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个子节点时，我不知道如何实现这种情况.我想用该节点的右子树上的最小项替换该节点的值，然后删除其右子树上的最小项.

The cases of no children and a single child work perfectly, but when the node to be deleted has 2 children, I cannot figure out how to implement this case. I want to replace that node's value with the smallest item on it's right subtree, and then remove the smallest item on its right subtree.

推荐答案

我不太确定我了解您的remove函数尝试实现的逻辑.通常的方法是编写一个递归函数:

I'm not quite sure I understand the logic that your remove function is trying to implement. The usual way to do this is to write a recursive function that:

• 如果x小于当前值，则递归从左侧子树中删除x
• 如果x大于当前值，则以递归方式从右子树中删除x
• 如果x等于当前节点，则删除当前节点并合并两棵树

• if x is smaller than the current, remove x from the left sub-tree recursively
• if x is larger than the current, remove x from the rightsub-tree recursively
• if x is equal to the current, drop the current node and merge the two trees

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

The way to encode this in F# is to write a recursive function using pattern matching - quite similar to the functions you wrote:

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函数.合并功能的逻辑如下:

[EDIT The following is not actually going to work!] This is almost complete, but you need to add the merge function. The logic for the merge function is the following:

• 如果两棵树都为空，则返回空树
• 如果左侧为Bin(n, llst, lrst)，右侧为rst，则返回一棵包含n且左侧为llst且右侧(递归地)合并了lrst和rst的树(因为元素两者都大于n).
• 类似地，如果right为Bin，而left为其他.

• If both trees are empty, return empty tree
• If left is Bin(n, llst, lrst) and the right is rst then return a tree that contains n with llst on the left and (recursively) merged lrst and rst on the right (because elements in both of them are larger than n).
• Similarly if right is Bin and left is anything else.

这不会产生平衡的二叉树，但这是一个很好的开始.

This is not going to produce a balanced binary tree, but it is a good start.

编辑:我认为，最简单的选择可能是编写两个函数-一个删除树的最大元素，另一个删除树的最小元素(然后在合并时，您可以只调用一个这两个中的一个).这可能比编写一个完全通用的删除功能要容易.

EDIT: I think that perhaps an easiest option is to write two functions - one to remove the largest and one to remove the smallest element of the tree (then when merging, you can just call one of these two). This might be easier than writing a fully general remove function.

以下内容删除最大的元素并将其与一棵新树(不包含最大的元素)一起返回:

The following removes the largest element and returns it, together with a new tree (without the largest element):

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)

这篇关于从F#中的二进制搜索树中删除元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！