在上下文中使用空的BST的高度是多少？

Question

假设BST的数据类型定义如下（在SML中）

datatype 'a bst_Tree =
   Empty
 | Node of (int * 'a) * 'a bst_Tree * 'a bst_Tree;

因此，有两种情况是BST Empty 或者它可以有一个（钥匙，价值）和两个孩子。

现在，对于条件为AVL的情况

在AVL树中，任何节点的两个子树的高度最多都不同
_{- avl树维基百科}

我希望能够创建一个高度函数，以检查树是否平衡。我目前的设置如下

fun height (Empty) = ~1
  | height (Node(v, Empty, Empty)) = 0 (* Redundant matching because of third case *)
  | height (Node(v, L, R)) = 1 + Int.max(height(L),height(R))

我试图将树分为三个条件

1. 一棵空的树
2. 带根节点的树
3. 填充的树

这样做的原因是，似乎没有一个规范来源 Empty 与只有根的树相反。出于我的平衡功能的目的，它完成了这项工作，但我宁愿理解为什么没有一个规范的答案 Empty 树。

在谈论的问题上有一个规范的答案 维基百科 但是，尽管最初对堆栈溢出进行研究，但我发表了许多评论，说这是错误/不正确/非常规的评论

通常，值-1对应于没有节点的子树，而零对应于带有一个节点的子树。）

我抓住了我的不确定性出现的问题

树高度的定义是什么？

我想你应该看看 算法和数据结构词典 在NIST网站上。高度的定义说一个节点是高度0。

这 有效树的定义 确实包括一个空结构。该站点没有提及这种树的高度，但是基于高度的定义，也应为0。

Answer 1

这 高度 根树的定义为 最长的简单叶到根路径的长度

如果是2个节点树，则显然该长度为1。

对于1个节点树（仅根根的树），则长度必须为0。（从叶到根的路径上有0个边缘。）

如果是0节点树，那么-1毫无意义。它是一个 距离 并且必须具有一个值$ geq 0 $，但是尝试测量长度也不是有意义的 null.

有时选择-1是因为它与节点高度的此复发关系保持一致：（基本上与您上面发布的内容相同）

height(null) = -1
height((v, left, right)) = max(height(left), height(right)) + 1

但是我们可以很容易地定义：

height((v, null, null)) = 0
height(null) = 0
height((v, left, right)) = max(height(left), height(right)) + 1

Answer 2

任何恒定都可以作为高度 Empty, ，因为只有 区别 高度对于平衡很重要。那么，为什么不选择0呢？