一、概念
平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树（Binary Search Tree，BST），它在插入和删除节点时通过自平衡的方式来维持树的平衡性。平衡性的维护可以确保树的高度保持在较小的范围内，从而保证了树的基本操作（例如搜索、插入和删除）的平均时间复杂度为 O(log n)。
平衡二叉树的主要特点是任意节点的左子树和右子树的高度差（平衡因子）不超过1。换句话说，对于树中的每个节点，它的左子树和右子树的高度差的绝对值最多为1。
平衡二叉树的平衡性质可以通过旋转操作来维护。旋转操作包括左旋（Left Rotation）、右旋（Right Rotation）、左右旋（Left-Right Rotation）和右左旋（Right-Left Rotation）。这些操作可以使不平衡的树重新平衡，从而确保树的平衡性。
平衡二叉树的优点在于它提供了较快的搜索、插入和删除操作的平均性能，相比于非平衡的二叉搜索树
二、性质
- 二叉搜索树性质： 对于树中的每个节点，其左子树上的所有节点值都小于它，右子树上的所有节点值都大于它。
- 平衡性质： 对于树中的每个节点，它的左子树和右子树的高度差（平衡因子）最多为1。换句话说，任何节点的左右子树高度之差不超过1。
平衡二叉树的平衡性质确保了树的高度始终保持在较小的范围内，从而保持了较快的搜索、插入和删除操作。
三、插入操作
插入一个节点时，首先按照二叉搜索树的规则找到插入位置。然后，从插入位置向上回溯，更新每个祖先节点的高度，并检查平衡性质是否被破坏。如果发现某个节点的平衡因子超过1或小于-1，需要通过旋转操作来修复平衡性。
四、旋转操作
平衡二叉树的旋转操作有四种：左旋、右旋、左右旋、右左旋。这些旋转操作可以将不平衡的树重新平衡。下面简要介绍左旋和右旋：
- 左旋（LL旋转）： 当一个节点的右子树比左子树高度高，且右子树的左子树高度不低于右子树的右子树时，进行左旋。左旋是通过将当前节点的右子树提升为新的根，并将原根作为新根的左子树来实现的。
- 右旋（RR旋转）： 当一个节点的左子树比右子树高度高，且左子树的右子树高度不低于左子树的左子树时，进行右旋。右旋是通过将当前节点的左子树提升为新的根，并将原根作为新根的右子树来实现的。
五、删除操作
删除节点时，首先按照二叉搜索树的规则找到要删除的节点。删除节点后，从删除位置向上回溯，更新每个祖先节点的高度，并检查平衡性质是否被破坏。如果发现某个节点的平衡因子超过1或小于-1，同样需要通过旋转操作来修复平衡性。
六、代码实现
class TreeNode { int val; int height; // 节点的高度 TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; this.height = 1; this.left = null; this.right = null; } } public class AVLTree { private TreeNode root; public AVLTree() { this.root = null; } // 获取节点高度 private int height(TreeNode node) { return (node == null) ? 0 : node.height; } // 更新节点高度 private void updateHeight(TreeNode node) { if (node != null) { node.height = 1 + Math.max(height(node.left), height(node.right)); } } // 获取平衡因子 private int getBalanceFactor(TreeNode node) { return (node == null) ? 0 : height(node.left) - height(node.right); } // 左旋 private TreeNode leftRotate(TreeNode y) { TreeNode x = y.right; TreeNode T2 = x.left; // 执行旋转 x.left = y; y.right = T2; // 更新高度 updateHeight(y); updateHeight(x); return x; } // 右旋 private TreeNode rightRotate(TreeNode x) { TreeNode y = x.left; TreeNode T2 = y.right; // 执行旋转 y.right = x; x.left = T2; // 更新高度 updateHeight(x); updateHeight(y); return y; } // 插入节点 public TreeNode insert(TreeNode root, int val) { if (root == null) { return new TreeNode(val); } // 执行标准的BST插入 if (val < root.val) { root.left = insert(root.left, val); } else if (val > root.val) { root.right = insert(root.right, val); } else { // 不允许插入相同的值 return root; } // 更新节点高度 updateHeight(root); // 获取平衡因子 int balance = getBalanceFactor(root); // 平衡维护 // 左子树高度大于右子树，且插入发生在左子树的左侧，需要进行右旋 if (balance > 1 && val < root.left.val) { return rightRotate(root); } // 右子树高度大于左子树，且插入发生在右子树的右侧，需要进行左旋 if (balance < -1 && val > root.right.val) { return leftRotate(root); } // 左子树高度大于右子树，且插入发生在左子树的右侧，需要先左旋再右旋 if (balance > 1 && val > root.left.val) { root.left = leftRotate(root.left); return rightRotate(root); } // 右子树高度大于左子树，且插入发生在右子树的左侧，需要先右旋再左旋 if (balance < -1 && val < root.right.val) { root.right = rightRotate(root.right); return leftRotate(root); } return root; } // 对外提供的插入接口 public void insert(int val) { root = insert(root, val); } // 中序遍历 private void inOrderTraversal(TreeNode root) { if (root != null) { inOrderTraversal(root.left); System.out.print(root.val + " "); inOrderTraversal(root.right); } } // 对外提供的中序遍历接口 public void inOrderTraversal() { inOrderTraversal(root); } public static void main(String[] args) { AVLTree avlTree = new AVLTree(); // 插入一些节点进行测试 avlTree.insert(10); avlTree.insert(20); avlTree.insert(30); avlTree.insert(15); avlTree.insert(5); // 中序遍历，检查树的平衡性 avlTree.inOrderTraversal(); } }
七、复杂度
平衡二叉树的高度始终保持在O(log n)范围内，因此搜索、插入和删除操作的平均时间复杂度为O(log n)。
总之，平衡二叉树通过维护平衡性质，提高了搜索、插入和删除操作的效率，确保树的高度保持在较小范围内。
