什么是平衡二叉树 (Balanced Binary Tree)？

推荐答案

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树，其中每个节点的左右子树的高度差不超过1。这种平衡性确保了树的操作（如插入、删除和查找）在最坏情况下的时间复杂度为O(log n)。

本题详细解读

平衡二叉树的定义

平衡二叉树是一种二叉搜索树，其中每个节点的左右子树的高度差不超过1。这意味着树的高度是平衡的，从而保证了树的操作效率。

平衡二叉树的性质

1. 高度平衡：每个节点的左右子树的高度差不超过1。
2. 递归定义：平衡二叉树的左右子树也必须是平衡二叉树。
3. 操作效率：由于树的高度平衡，插入、删除和查找操作的时间复杂度为O(log n)。

平衡二叉树的实现

平衡二叉树的实现通常通过自平衡二叉搜索树（如AVL树或红黑树）来完成。这些树在插入或删除节点时会自动调整结构，以保持树的平衡性。

平衡二叉树的应用

平衡二叉树广泛应用于需要高效查找、插入和删除操作的场景，如数据库索引、内存管理、编译器设计等。

平衡二叉树的示例

以下是一个简单的平衡二叉树的示例：

      10
     /  \
    5    20
   / \   / \
  2   7 15 30

在这个示例中，每个节点的左右子树的高度差都不超过1，因此这是一棵平衡二叉树。

平衡二叉树的验证

验证一棵二叉树是否为平衡二叉树，可以通过递归计算每个节点的左右子树的高度差来实现。如果所有节点的左右子树高度差都不超过1，则该树是平衡的。

// www.javascriptcn.com code example
def is_balanced(root):
    def check_height(node):
        if not node:
            return 0
        left_height = check_height(node.left)
        right_height = check_height(node.right)
        if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
            return -1
        return max(left_height, right_height) + 1
    
    return check_height(root) != -1

在这个代码中，check_height函数递归地计算每个节点的左右子树的高度，并检查高度差是否超过1。如果超过1，则返回-1，表示树不平衡。