sml - ML 中的 AVL 树 - 向左旋转，警告 : match nonexhaustive

Question

我正在用 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));

我从口译员那里得到:

Warning: match nonexhaustive

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

Answer 1

I am getting from the interpreter:

Warning: match nonexhaustive

How do I fix this with the current datatypes I have? [...]

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

左旋转看起来像这样:

  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)) + 1 B的新高度为max(height(new A), height (右 B))。为此扩展 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 位于嵌套元组中，因此可能会将树转换为从某个整数到某个 的映射'一个。在那种情况下，请忽略保持树中高度的优化。