在二叉树的情况下，如果树是倾斜的，则它们在执行运算上效率低下。

什么是平衡二叉树

平衡二叉树在执行操作上在计算上很有效。

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

• 任何节点上左右子树的高度的绝对差小于1。

• 对于每个节点，其左子树是平衡二叉树。

• 对于每个节点，其右子树是平衡二叉树。

高度平衡的二叉树

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

如果对于一棵树，平衡因子(k)等于零，则该树称为完全平衡的二叉树。
可以表示为HB(0)。

自平衡二进制搜索树

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

AVL树是一种自平衡二进制搜索树。
在AVL树中，如果左右子树之间的差异大于1，则它将执行以下4次旋转之一以重新平衡自身：

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

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

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

• 任何节点上左右子树的高度之间的绝对差应小于1。

• 对于每个节点，其左子树应为平衡二叉树。

• 对于每个节点，其右子树应为平衡二叉树。

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

更好的方法是在同一函数中返回高度。

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

算法如下：

• 如果node == 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);
  }
</code>

您可以在树的根上调用此函数，如果它返回的值不是-1，则它是平衡的二叉树。
如果返回-1，则它不是平衡的二叉树。