平衡二叉树 （简单易懂）

目录

一、概念

二、性质

三、插入操作

四、旋转操作

五、删除操作

六、代码实现

七、复杂度

---

一、概念

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树（Binary Search Tree，BST），它在插入和删除节点时通过自平衡的方式来维持树的平衡性。平衡性的维护可以确保树的高度保持在较小的范围内，从而保证了树的基本操作（例如搜索、插入和删除）的平均时间复杂度为 O(log n)。

平衡二叉树的主要特点是任意节点的左子树和右子树的高度差（平衡因子）不超过1。换句话说，对于树中的每个节点，它的左子树和右子树的高度差的绝对值最多为1。

平衡二叉树的平衡性质可以通过旋转操作来维护。旋转操作包括左旋（Left Rotation）、右旋（Right Rotation）、左右旋（Left-Right Rotation）和右左旋（Right-Left Rotation）。这些操作可以使不平衡的树重新平衡，从而确保树的平衡性。

平衡二叉树的优点在于它提供了较快的搜索、插入和删除操作的平均性能，相比于非平衡的二叉搜索树

二、性质

1. 二叉搜索树性质： 对于树中的每个节点，其左子树上的所有节点值都小于它，右子树上的所有节点值都大于它。

2. 平衡性质： 对于树中的每个节点，它的左子树和右子树的高度差（平衡因子）最多为1。换句话说，任何节点的左右子树高度之差不超过1。

平衡二叉树的平衡性质确保了树的高度始终保持在较小的范围内，从而保持了较快的搜索、插入和删除操作。

三、插入操作

插入一个节点时，首先按照二叉搜索树的规则找到插入位置。然后，从插入位置向上回溯，更新每个祖先节点的高度，并检查平衡性质是否被破坏。如果发现某个节点的平衡因子超过1或小于-1，需要通过旋转操作来修复平衡性。 

四、旋转操作

平衡二叉树的旋转操作有四种：左旋、右旋、左右旋、右左旋。这些旋转操作可以将不平衡的树重新平衡。下面简要介绍左旋和右旋：

1. 左旋（LL旋转）： 当一个节点的右子树比左子树高度高，且右子树的左子树高度不低于右子树的右子树时，进行左旋。左旋是通过将当前节点的右子树提升为新的根，并将原根作为新根的左子树来实现的。

2. 右旋（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)。

总之，平衡二叉树通过维护平衡性质，提高了搜索、插入和删除操作的效率，确保树的高度保持在较小范围内。