二叉树算法之平衡二叉树（AVL Tree）详细解读

平衡二叉树（AVL Tree）是一种自平衡的二叉搜索树（Binary Search Tree, BST），其特点是通过维护树的高度平衡来保证基本操作（插入、删除和查找）的时间复杂度为 O(log⁡n)。AVL树是由G.M. Adelson-Velsky和E.M. Landis于1962年提出的，因此得名“AVL树”。

1. AVL树的定义

AVL树的每个节点都有一个平衡因子（Balance Factor），其值为该节点的左子树高度减去右子树高度。对于任何一个节点，平衡因子的值只能为 −1、0 或 1，表示树的高度是平衡的。如果一个节点的平衡因子为 −1，表示右子树比左子树高；如果平衡因子为 1，表示左子树比右子树高；如果平衡因子为 0，表示左右子树高度相等。

2. AVL树的特性

性质：对于每个节点，左子树和右子树的高度差（平衡因子）最多为1。
高度平衡：由于AVL树保持高度平衡，查找、插入和删除的时间复杂度都是 O(log⁡n)
自平衡：在插入或删除节点后，AVL树会通过旋转操作来恢复平衡。

3. AVL树的旋转

当AVL树失去平衡时，通过旋转操作来恢复平衡。主要的旋转操作有四种：

右旋（Right Rotation）：
- 当某个节点的左子树比右子树高时，进行右旋转，以恢复平衡。
- 适用于插入在左子树的左侧（LL型）。
左旋（Left Rotation）：
- 当某个节点的右子树比左子树高时，进行左旋转，以恢复平衡。
- 适用于插入在右子树的右侧（RR型）。
左-右旋（Left-Right Rotation）：
- 当某个节点的左子树比右子树高，且插入在左子树的右侧时，先进行左旋再进行右旋，以恢复平衡（LR型）。
右-左旋（Right-Left Rotation）：
- 当某个节点的右子树比左子树高，且插入在右子树的左侧时，先进行右旋再进行左旋，以恢复平衡（RL型）。

4. AVL树的插入操作

插入操作分为以下步骤：

普通的二叉搜索树插入：按照二叉搜索树的性质插入新节点。
更新平衡因子：从插入位置向上更新每个节点的高度和平衡因子。
检查平衡：如果某个节点的平衡因子变为 −2 或 2，则需要进行旋转操作。
旋转恢复平衡：根据失衡的情况，选择适当的旋转操作来恢复平衡。

AVL树的Java实现

以下是AVL树的Java实现示例，包括插入和旋转操作：

class AVLTreeNode {int key;int height;AVLTreeNode left, right;public AVLTreeNode(int key) {this.key = key;this.height = 1;}
}class AVLTree {private AVLTreeNode root;// 获取节点高度private int height(AVLTreeNode node) {return node == null ? 0 : node.height;}// 获取平衡因子private int getBalance(AVLTreeNode node) {return node == null ? 0 : height(node.left) - height(node.right);}// 右旋private AVLTreeNode rightRotate(AVLTreeNode y) {AVLTreeNode x = y.left;AVLTreeNode T2 = x.right;// 进行旋转x.right = y;y.left = T2;// 更新高度y.height = Math.max(height(y.left), height(y.right)) + 1;x.height = Math.max(height(x.left), height(x.right)) + 1;return x; // 新的根节点}// 左旋private AVLTreeNode leftRotate(AVLTreeNode x) {AVLTreeNode y = x.right;AVLTreeNode T2 = y.left;// 进行旋转y.left = x;x.right = T2;// 更新高度x.height = Math.max(height(x.left), height(x.right)) + 1;y.height = Math.max(height(y.left), height(y.right)) + 1;return y; // 新的根节点}// 插入节点public AVLTreeNode insert(AVLTreeNode node, int key) {// 1. 执行普通的BST插入if (node == null) {return new AVLTreeNode(key);}if (key < node.key) {node.left = insert(node.left, key);} else if (key > node.key) {node.right = insert(node.right, key);} else { // 不允许重复值return node;}// 2. 更新当前节点的高度node.height = Math.max(height(node.left), height(node.right)) + 1;// 3. 获取平衡因子int balance = getBalance(node);// 4. 如果节点失衡，则进行旋转操作// LL型if (balance > 1 && key < node.left.key) {return rightRotate(node);}// RR型if (balance < -1 && key > node.right.key) {return leftRotate(node);}// LR型if (balance > 1 && key > node.left.key) {node.left = leftRotate(node.left);return rightRotate(node);}// RL型if (balance < -1 && key < node.right.key) {node.right = rightRotate(node.right);return leftRotate(node);}return node; // 返回未变化的节点指针}// 中序遍历public void inorder(AVLTreeNode node) {if (node != null) {inorder(node.left);System.out.print(node.key + " ");inorder(node.right);}}public void display() {inorder(root);System.out.println();}public void insert(int key) {root = insert(root, key);}public static void main(String[] args) {AVLTree avlTree = new AVLTree();int[] keys = {10, 20, 30, 40, 50, 25};for (int key : keys) {avlTree.insert(key);}System.out.println("中序遍历 AVL 树：");avlTree.display(); // 输出: 10 20 25 30 40 50}
}