在计算红黑树高度的方法中- 1是什么意思?

Question

我不明白为什么我们要在第4行减去1。我想只返回高度(根)就可以了，负1是什么意思?

public int height() {
if(root == null)
return 0;
return height(root) - 1;
}
public int height(Node<K,V> node) {
if (node == null)
return 0;
int leftheight = height(node.left) + 1
int rightheight = height(node.right) + 1
if (leftheight > rightheight)
return leftheight;
return rightheight;
}

Answer 1

这个- 1是必需的，因为第二个height函数不计算高度，而是比高度多1。

树的高度定义为从根到叶的最长路径上的边数，但第二个函数计算从根到叶的最长路径上的节点数(或层数)，这总是多一个。

我同意这是一种奇怪的方式，因为它实际上使第二个函数的名称错误:它没有做它所说的。

此外，main函数也有一个问题，因为当根为null时，高度应该返回-1。

更自然的做法是改变基本情况，让第二个函数真正返回作为参数传递的节点的高度:

public int height() {
return height(root); // Simple: if no argument was passed, the default is the root
}
public int height(Node<K,V> node) {
if (node == null)
return -1; // <-----
int leftheight = height(node.left) + 1
int rightheight = height(node.right) + 1
if (leftheight > rightheight)
return leftheight;
return rightheight;
}

在这里使用-1值可能很奇怪，但原因如下:

树的高度为1:

a
/ 
b   c

…因为从根目录出发的最长路径有一个优势;它是一个有2层的树，高度比层数少1。

这是一个高度为0的树:

a

这里的关卡数为1，因此高度为0。

再一步，是否为空树——它甚至没有节点，也没有级别，所以相应的高度应该是-1。

参见What is the definition for a height of a tree