SML 二叉搜索树插入函数

Question

我是 SML 的新手，正在尝试实施 BST。我已经想出如何解析树，但正在努力创建插入函数。我希望函数是： insert(bst, key, value) of type BST * int * int -> BST 它将键值对插入给定树和 returns 结果树。不过，我在创建这个过程中遇到了困难，因为我对确保函数的类型正确感到有点困惑。

到目前为止，这是我的代码，我还包含了一个示例树

(* left subtree, right subtree, key, value *)
datatype BST = Empty | Node of BST * BST * int * int;

fun parsePost [] = Empty
  | parsePost lst =
    let
      fun pP(stack, (0, k, v)::str) = pP(Node(Empty, Empty, k, v)::stack, str)
        | pP(L::stack, (1, k, v)::str) = pP(Node(L, Empty, k, v)::stack, str)
        | pP(R::stack, (2, k, v)::str) = pP(Node(Empty, R, k, v)::stack, str)
        | pP(R::L::stack, (3, k, v)::str) = pP(Node(L, R, k, v)::stack, str)
        | pP(T::stack, []) = T;
    in
      pP([], lst)
    end;

val exTree1 = [(0, 1, 1), (0, 3, 3), (3, 2, 2)];

我正考虑这样启动插入功能：

fun insert(Empty, x, y) = Empty

但我不太确定从那里去哪里。

Answer 1

如果你将一个键值对插入到一个空树中，你真的期望得到一个空树吗？我很怀疑这是你所期望的。

相反，您可能期望一棵树有那对，但树枝是空的。

fun insert(Empty, x, y) = Node(Empty, Empty, x, y)

如果树不是空的呢？

让我们考虑一个简单的例子：

val ex1 = Node(Empty, Empty, 1, 4)

这看起来像：

      (1,4)
       / \
      /   \
     /     \
  Empty   Empty

好吧，如果我们评估 insert(ex1, 2, 5) 那么大概结果应该是这样的：

      (1,4)
       / \
      /   \
     /     \
  Empty   (2,5)
           / \
          /   \
         /     \
      Empty   Empty

为了得到这个，我们必须意识到正确的分支与我们评估 insert(Empty, 2, 5).

时得到的结果相同

      (2,5)
       / \
      /   \
     /     \
  Empty   Empty

由于树数据类型是递归的，因此您的解决方案也是如此。我们需要检查您要插入的键是否与已存储在节点中的键相同。如果是，我们无需更改任何内容。

如果小于已经存在的键，我们插入左分支，如果大于，我们插入右分支。

fun insert(Empty, x, y) = Node(Empty, Empty, x, y)
  | insert((n as Node(l, r, k, v)), x, y) = 
      case Int.compare(x, k) of
        EQUAL   => n
      | LESS    => Node(insert(l, x, y), r, k, v)
      | GREATER => Node(l, insert(r, x, y), k, v)

此策略可扩展到任何深度的树结构，因为最终一个分支将始终包含您要查找的键，或者有一个空分支。

SML 二叉搜索树插入函数

SML Binary Search Tree Insert Function

function

insert

binary-search-tree

sml

ml