时间戳

首页 > 解决方案 > ML中的AVL树-向左旋转，警告：匹配非穷举

sml - ML中的AVL树-向左旋转，警告：匹配非穷举

问题描述

我正在 SML 中实现 AVL 树：

这是我的数据类型：

datatype 'a AVLTree = Nil | Br of ((int*('a))*('a AVLTree)*('a AVLTree));
datatype Balance = RR | LR | LL | RL;
exception NotFound;
exception NullValue

我现在正在写函数Rotate-Left，我写的如下：

fun rotate_left Nil = Nil
     |rotate_left (Br(x,A,Br(y,B,C))) = (Br(y,Br(x,A,B),C));

我从口译员那里得到：

警告：匹配不完整

如何使用我拥有的当前数据类型解决此问题？我尝试使用通配符但没有成功..

标签： smlavl-tree

解决方案

我从口译员那里得到：

Warning: match nonexhaustive

如何使用我拥有的当前数据类型解决此问题？[...]

也许不应该避免这个警告。毕竟你可以不旋转所有的树。

左旋转看起来像这样：

  A              B
 / \            / \
…   B     ~>   A   C
   / \        / \ / \
  …   C      …   …   …
     / \
    …   …

给定一个不跟踪高度的 AVL 树类型，

datatype 'a AVLTree = Nil | Br of 'a * 'a AVLTree * 'a AVLTree

（括号不是必需的）您的版本rotate_left是正确的。我在下面重写并重命名了左右子分支。一点是B的左支成为A的新的右支。

fun rotate_left (Br (a, leftA, Br (b, leftB, rightB))) =
                 Br (b, Br (a, leftA, rightB), rightB)

这是一个偏函数，它无法匹配的模式是：

  • Nil– 但是空树的左旋转没有明确定义。

  • Br (a, leftA, Nil)– 但以下左旋转也没有明确定义：

      A             ?
 / \           / \
…   Nil   ~>  A   …
             / \
            …   ?

如果您尝试对其中一棵树进行左旋转，则不会产生有意义的结果。拥有Warning: match nonexhaustive也不令人满意。您可以改为提出一个有意义的异常，例如

fun rotate_left (Br (a, leftA, Br (b, leftB, rightB))) =
                 Br (b, Br (a, leftA, rightB), rightB)
  | rotate_left _ = raise Fail "Invalid left-rotation"

现在，您还没有真正解释为什么在您的数据类型定义中有一个额外的int 。也许这是树的预先计算的高度？那会很整洁（您可以使用类型别名来编码该含义），因为那时您的不变性检查变得更便宜。在这种情况下，左旋需要更新高度：

type height = int
datatype 'a AVLTree = Nil | Br of height * 'a * 'a AVLTree * 'a AVLTree

根据上图，A 的新高度是max(height(leftA), height(leftB)) + 1B 的新高度max(height(new A), height(rightB))。rotate_left为此扩展功能：

fun height Nil = 0
  | height (Br (h, _, _, _)) = h

fun rotate_left (Br (ha, a, leftA, Br (hb, b, leftB, rightB))) =
    let val ha' = Int.max (height leftA, height leftB) + 1
        val hb' = Int.max (ha', height rightB) + 1
    in Br (hb', b, Br (ha', a, leftA, rightB), rightB) end
  | rotate_left _ = raise Fail "Invalid left-rotation"

编辑：在我看来，额外的int位于嵌套元组中，因此可能会将树转换为从某个整数到某个'a的映射。在这种情况下，请忽略保持树中高度的优化。

推荐阅读