平衡二叉树完全指南：定义、特性与高效检查方法

如果二叉树偏斜，进行操作时会变得计算效率低下。

这就是确保树不偏斜的动机。因此需要平衡二叉树。

什么是平衡二叉树

平衡二叉树在进行操作时具有较高的计算效率。

平衡二叉树将满足以下条件：

1. 每个节点的左子树和右子树的高度差值都小于1。
2. 每个节点的左子树是平衡二叉树。
3. 每个节点的右子树是平衡二叉树。

平衡二叉树

平衡二叉树也被称为高平衡二叉树。高平衡二叉树可以表示为HB(k)，其中k是左右子树高度之差。’k’被称为平衡因子。

如果树的平衡因子（k）等于零，则该树被称为完全平衡二叉树。可以表示为HB（0）。

自平衡二叉搜索树

如果一个二叉搜索树的平衡因子为1，则它是一个AVL（Adelso-Velskii和Landis）树。这意味着在AVL树中，左子树和右子树的高度差最多为1。

AVL树是一种自平衡的二叉搜索树。在AVL树中，如果左右子树之间的差值大于1，则会执行以下四种旋转之一来重新平衡自身：

• 左旋转
• 右旋转
• 左-右旋转
• 右-左旋转

如何检查二叉树是否平衡？

要检查一个二叉树是否平衡，我们需要检查三个条件：

1. 任意节点的左右子树高度的绝对差应该小于1。
2. 每个节点的左子树应该是一个平衡二叉树。
3. 每个节点的右子树应该是一个平衡二叉树。

我们将需要一个能够计算树的高度的函数。一种方法是编写一个单独的函数来计算高度，并在每次需要高度时调用它。这样会导致计算效率低下。

更好的实现方式是在同一个函数中返回高度。

对于每个节点，如果它不平衡，我们将返回-1；如果它平衡，我们将返回该节点/子树的高度。

以下是算法：

• 如果节点为空 -> 返回0
• 检查左子树。如果不平衡 -> 返回-1
• 检查右子树。如果不平衡 -> 返回-1
• 计算左右子树高度的绝对差。如果大于1 -> 返回-1
• 如果树是平衡的 -> 返回高度

伪代码如下所示：

 private int balanceHeight (TreeNode currentNode)
    {
        if (currentNode == null)
        {
            return 0;
        }

        // 检查左子树
        int leftSubtreeHeight = balanceHeight (currentNode.left);
        if (leftSubtreeHeight == -1) return -1;
        // 如果左子树不平衡，则整棵树也不平衡

        // 检查右子树
        int rightSubtreeHeight = balanceHeight (currentNode.right);
        if (rightSubtreeHeight == -1) return -1;
        // 如果右子树不平衡，则整棵树也不平衡

        // 检查当前节点的左右子树高度差
        if (Math.abs(leftSubtreeHeight - rightSubtreeHeight) > 1)
        {
            return -1;
        }
        // 如果平衡，则返回高度
        return (Math.max(leftSubtreeHeight, rightSubtreeHeight) + 1);
    }

你可以在树的根节点上调用这个函数，如果它返回的值不等于-1，那么这棵树就是一棵平衡二叉树。如果它返回-1，那么这棵树就不是一棵平衡二叉树。

结论

在本教程中，我们讲解了平衡二叉树以及如何检查一棵树是否为平衡二叉树。希望你能理解并喜欢与我们一起学习。