平衡二叉树的定义与检验

作者 Jayant Verma

对于二叉树来说，如果它是倾斜的，执行运算时计算效率就会很低。

因此，我们需要确保二叉树不会倾斜，即需要平衡二叉树。

什么是平衡二叉树

平衡二叉树在执行运算时计算效率很高。

平衡二叉树遵循以下条件：

在任一节点上，其左右两个子树的高度差绝对值小于1。
任一节点的左子树都是一棵平衡二叉树。
任一节点的右子树都是一棵平衡二叉树。

高度平衡二叉树

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

如果一棵树的平衡因子（k）为0，那么它被称为完全平衡的二叉树，表示为 HB(0) 。

完全平衡的二叉树

自平衡二叉查找树

如果二叉搜索树的平衡因子为 1 ，那么它就是一棵 AVL 树（AVL 即 Adelso-Velskii and Landis，其发明者的名字）。在 AVL 树中，左子树和右子树之间的高度差最多为 1 。

AVL 树是一种自平衡二叉查找树。在 AVL 树中，如果左右子树之间的高度差大于 1，它会执行以下四种旋转之一来重新平衡自己：

左旋平衡
右旋平衡
双向旋转平衡（先左后右）
双向旋转平衡（先右后左）

AVL 树

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

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

任一节点上的左右子树高度差绝对值应小于1。
任一节点上的左子树都是一棵平衡二叉树。
任一节点上的右子树都是一棵平衡二叉树。

我们需要一个可以计算树高的函数。我们可以编写一个单独的函数来计算高度，并在每次需要时调用它，但这种方法计算效率很低。

为实现这一目的，更好的方法是在同一函数中直接返回高度。

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

算法如下:

如果节点==null ->返回 0
检查左子树。如果不平衡 -> 返回 -1
检查右子树。如果不平衡 -> 返回 -1
左右子树高度差绝对值。如果大于 1 -> 返回 -1
如果树是平衡的->返回高度

伪代码如下所示：

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

        // checking left subtree检查左子树
        int leftSubtreeHeight = balanceHeight (currentNode.left);
        if (leftSubtreeHeight == -1) return -1;
        // if left subtree is not balanced then the entire tree is also not balanced

        //checking right subtree检查右子树
        int rightSubtreeHeight = balanceHeight (currentNode.right);
        if (rightSubtreeHeight == -1) return -1;
        // if right subtree is not balanced then the entire          tree is also not balanced如果左子树不平衡，整个树也不平衡

        //checking the difference of left and right subtree for current node检验该节点的左右子树高度差
        if (Math.abs(leftSubtreeHeight - rightSubtreeHeight) > 1)
        {
            return -1;
        }
        //if it is balanced then return the height如果平衡，则返回该节点高度
        return (Math.max(leftSubtreeHeight, rightSubtreeHeight) + 1);
    }

你可以在二叉树的根部调用这个函数，如果返回 -1 以外的任何值，那么该树即为平衡二叉树。如果返回-1，那么它就不是平衡二叉树。

小结

本教程介绍了平衡二叉树的定义与检验方法。希望您顺利掌握，学习愉快！