平衡二叉树（AVL树）：原理、常见算法及其应用

引言

AVL树的基本概念

常见算法

插入节点

查找节点

删除节点

AVL树的应用场景

1. 数据库索引

2. 符号表

3. 字典和词汇表

4. 动态集合

5. GPS导航系统

6. 计算机辅助设计（CAD）

结论

引言

平衡二叉树（Balanced Binary Tree），特别是AVL树（Adelson-Velsky and Landis tree），是一种自平衡的二叉搜索树。它在每次插入或删除操作之后都会自动调整自身，以确保树的高度保持在尽可能小的状态。这种自我调整机制使得AVL树能够在保持较低的高度的同时，提供高效的查找、插入和删除操作。本文将从AVL树的基本概念出发，逐步介绍其原理、常见算法，并通过具体的Java代码示例来加深理解，最后探讨AVL树在算法中的实际应用场景。

AVL树的基本概念

AVL树是一种特殊的二叉搜索树，其特点是任何节点的两个子树的高度之差最多为1。这意味着AVL树始终保持在相对平衡的状态，从而保证了操作的高效性。

节点定义

class AVLTreeNode {int val;int height;AVLTreeNode left;AVLTreeNode right;AVLTreeNode(int x) {val = x;height = 1; // 新节点默认高度为1}
}

高度和平衡因子

高度：节点的高度定义为该节点到其最远叶子节点路径上的边数。
平衡因子：节点的平衡因子定义为其左子树的高度减去右子树的高度。

失衡

当我们在一个平衡二叉树上插入一个结点时，有可能会导致失衡，即出现平衡因子绝对值大于1 的结点，如下图，当插入结点后，其中key为53的结点失去了平衡，我们称该结点为失衡结点，我们必须重新调整树的结构，使之恢复平衡。

恢复平衡：

那如何去恢复平衡，使得二叉搜索树依然成立为一棵平衡树？先来看平衡调整的四种类型：

举个例子：如第一个，当平衡二叉树为AB时，插入一个C结点，使得失衡了，失衡结点为A，此时因为C结点插入的位置为失衡结点的左孩子的左孩子，所以是LL型，以此类推。

为了恢复平衡，针对每一种都不一样，但目的都是调整为平衡的，且不能违背二叉搜索树的性质：如下图是每种失衡类型的解决方法，每个都不太一样，目的都是一样的，把key的值为中等的变为树的根，最小的放在左孩子，做大的放右孩子，通过这一目的，降低树的高度，也不用死记硬背。

常见算法

插入节点

插入新节点时，需要按照二叉搜索树的方式找到合适的位置，然后进行必要的旋转操作以恢复AVL树的平衡性。

例题：输入关键字序列(16，3，7，11 ，9，26，18，14，15)给出AVL树：

对应Java代码实现：

public class AVLTree {private AVLTreeNode root;// AVL树节点类private static class AVLTreeNode {int val;int height;AVLTreeNode left;AVLTreeNode right;AVLTreeNode(int x) {val = x;height = 1; // 新节点默认高度为1}}// 获取节点的高度private int getHeight(AVLTreeNode node) {if (node == null) {return 0;}return node.height;}// 获取节点的平衡因子private int getBalanceFactor(AVLTreeNode node) {if (node == null) {return 0;}return getHeight(node.left) - getHeight(node.right);}// 更新节点的高度private void updateHeight(AVLTreeNode node) {node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;}// 右旋private AVLTreeNode rotateRight(AVLTreeNode y) {AVLTreeNode x = y.left;AVLTreeNode T2 = x.right;// Perform rotationx.right = y;y.left = T2;// Update heightsupdateHeight(y);updateHeight(x);return x;}// 左旋private AVLTreeNode rotateLeft(AVLTreeNode x) {AVLTreeNode y = x.right;AVLTreeNode T2 = y.left;// Perform rotationy.left = x;x.right = T2;// Update heightsupdateHeight(x);updateHeight(y);return y;}// 插入节点public void insert(int value) {root = insertRecursive(root, value);}private AVLTreeNode insertRecursive(AVLTreeNode current, int value) {if (current == null) {return new AVLTreeNode(value);}if (value < current.val) {current.left = insertRecursive(current.left, value);} else if (value > current.val) {current.right = insertRecursive(current.right, value);} else {return current; // Value already exists}// Update height of this ancestor nodeupdateHeight(current);// Check balance factor to determine the rotationsint balanceFactor = getBalanceFactor(current);if (balanceFactor > 1) {if (value < current.left.val) {return rotateRight(current);} else if (value > current.left.val) {current.left = rotateLeft(current.left);return rotateRight(current);}}if (balanceFactor < -1) {if (value > current.right.val) {return rotateLeft(current);} else if (value < current.right.val) {current.right = rotateRight(current.right);return rotateLeft(current);}}return current;}// 打印AVL树public void printAVLTree() {printInOrder(root);System.out.println();}private void printInOrder(AVLTreeNode node) {if (node != null) {printInOrder(node.left);System.out.print(node.val + " ");printInOrder(node.right);}}// 主函数public static void main(String[] args) {AVLTree avlTree = new AVLTree();// 插入关键字序列avlTree.insert(16);avlTree.insert(3);avlTree.insert(7);avlTree.insert(11);avlTree.insert(9);avlTree.insert(26);avlTree.insert(18);avlTree.insert(14);avlTree.insert(15);// 打印AVL树avlTree.printAVLTree(); // 输出：3 7 9 11 14 15 16 18 26}
}

查找节点

查找特定值的节点时，从根节点开始，根据值与当前节点值的关系决定向左还是向右。

Java代码实现

boolean contains(int value) {return containsRecursive(root, value);
}private boolean containsRecursive(AVLTreeNode current, int value) {if (current == null) {return false;}if (value == current.val) {return true;}return value < current.val? containsRecursive(current.left, value): containsRecursive(current.right, value);
}

删除节点

删除节点时需要考虑三种情况：

节点是叶子节点。
节点有一个子节点。
节点有两个子节点。

Java代码实现

void delete(int value) {root = deleteRecursive(root, value);
}private AVLTreeNode deleteRecursive(AVLTreeNode current, int value) {if (current == null) {return current;}if (value < current.val) {current.left = deleteRecursive(current.left, value);} else if (value > current.val) {current.right = deleteRecursive(current.right, value);} else {// Node with only one child or no childif (current.left == null) {return current.right;} else if (current.right == null) {return current.left;}// Node with two children: Get the inorder successor (smallest in the right subtree)current.val = findMinValue(current.right);// Delete the inorder successorcurrent.right = deleteRecursive(current.right, current.val);}// If the node has only one child or no child, then it will be returned by above statements.if (current == null) {return current;}// Update the height of the current nodeupdateHeight(current);// Check balance factor to determine the rotationsint balanceFactor = getBalanceFactor(current);// Left Left Caseif (balanceFactor > 1 && getBalanceFactor(current.left) >= 0) {return rotateRight(current);}// Left Right Caseif (balanceFactor > 1 && getBalanceFactor(current.left) < 0) {current.left = rotateLeft(current.left);return rotateRight(current);}// Right Right Caseif (balanceFactor < -1 && getBalanceFactor(current.right) <= 0) {return rotateLeft(current);}// Right Left Caseif (balanceFactor < -1 && getBalanceFactor(current.right) > 0) {current.right = rotateRight(current.right);return rotateLeft(current);}return current;
}// Find the minimum value in a subtree
int findMinValue(AVLTreeNode node) {return node.left == null ? node.val : findMinValue(node.left);
}