在二叉搜索树中计算高度的最佳方法？（平衡AVL树）

在二叉搜索树中计算高度的最佳方法？（平衡AVL树） 第1部分-高度

正如starblue所说，高度只是递归的。用伪代码：

height(node) = max(height(node.L), height(node.R)) + 1

现在可以通过两种方式定义高度。它可以是从根到该节点的路径中的节点数，也可以是链接数。根据您引用的页面，最常见的定义是链接数。在这种情况下，完整的伪代码将是：

height(node):    if node == null:        return -1   else:        return max(height(node.L), height(node.R)) + 1

如果您想要节点数，则代码为：

height(node):    if node == null:        return 0   else:        return max(height(node.L), height(node.R)) + 1

无论哪种方式，我认为重新平衡算法都应该起作用。

但是，如果您在树中存储和更新高度信息，而不是每次都进行计算，则树的效率将大大提高（ O（ln（n）） ）。（ O（n） ）

第2部分-平衡

当它说“如果R的平衡因子是1”时，它是在说右分支的平衡因子，当顶部的平衡因子是2时。它告诉您如何选择单旋转还是旋转。两次旋转。在（类似于python）伪代码中：

if balance factor(top) = 2: // right is imbalanced     if balance factor(R) = 1: //do a left rotation     else if balance factor(R) = -1:          do a double rotationelse: // must be -2, left is imbalanced     if balance factor(L) = 1: //do a left rotation     else if balance factor(L) = -1:          do a double rotation

我希望这是有道理的