【数据结构与算法】第28篇：平衡二叉树（AVL树）

一、AVL树的定义1.1 平衡因子平衡因子 左子树高度 - 右子树高度AVL树要求所有节点的平衡因子只能是 -1、0、1。text节点高度从该节点到最远叶子节点的边数 空树高度-1 或 0不同定义本文用-11.2 为什么需要平衡普通BST插入有序序列时会退化text插入1,2,3,4,5 退化后 1 \ 2 \ 3 \ 4 \ 5 查找效率 O(n)AVL树通过旋转保持平衡查找效率始终 O(log n)。二、节点结构ctypedef struct AVLNode { int data; struct AVLNode *left; struct AVLNode *right; int height; // 节点高度 } AVLNode, *AVLTree;2.1 辅助函数c// 获取节点高度 int getHeight(AVLNode *node) { return node NULL ? -1 : node-height; } // 计算平衡因子 int getBalanceFactor(AVLNode *node) { if (node NULL) return 0; return getHeight(node-left) - getHeight(node-right); } // 更新节点高度 void updateHeight(AVLNode *node) { if (node NULL) return; int leftH getHeight(node-left); int rightH getHeight(node-right); node-height (leftH rightH ? leftH : rightH) 1; }三、四种旋转调整3.1 右旋LL型触发条件平衡因子 1 且 左子树的平衡因子 ≥ 0text不平衡节点: A 左孩子: B A B / \ / \ B C 右旋→ D A / \ / \ D E E CcAVLNode* rightRotate(AVLNode *y) { AVLNode *x y-left; AVLNode *T2 x-right; // 旋转 x-right y; y-left T2; // 更新高度 updateHeight(y); updateHeight(x); return x; }3.2 左旋RR型触发条件平衡因子 -1 且 右子树的平衡因子 ≤ 0text不平衡节点: A 右孩子: B A B / \ / \ C B 左旋→ A E / \ / \ D E C DcAVLNode* leftRotate(AVLNode *y) { AVLNode *x y-right; AVLNode *T2 x-left; // 旋转 x-left y; y-right T2; // 更新高度 updateHeight(y); updateHeight(x); return x; }3.3 左右旋LR型触发条件平衡因子 1 且 左子树的平衡因子 0text步骤1对左孩子左旋 步骤2对当前节点右旋 A A C / \ / \ / \ B C 左旋→ C C 右旋→ B A / \ / / \ \ D E B D E C / \ D EcAVLNode* leftRightRotate(AVLNode *node) { node-left leftRotate(node-left); return rightRotate(node); }3.4 右左旋RL型触发条件平衡因子 -1 且 右子树的平衡因子 0text步骤1对右孩子右旋 步骤2对当前节点左旋cAVLNode* rightLeftRotate(AVLNode *node) { node-right rightRotate(node-right); return leftRotate(node); }四、插入操作cAVLNode* insert(AVLNode *root, int value) { // 1. 普通BST插入 if (root NULL) { AVLNode *newNode (AVLNode*)malloc(sizeof(AVLNode)); newNode-data value; newNode-left NULL; newNode-right NULL; newNode-height 0; return newNode; } if (value root-data) { root-left insert(root-left, value); } else if (value root-data) { root-right insert(root-right, value); } else { return root; // 重复值不插入 } // 2. 更新高度 updateHeight(root); // 3. 计算平衡因子判断是否需要旋转 int balance getBalanceFactor(root); // 左子树过高 if (balance 1) { if (value root-left-data) { // LL型 return rightRotate(root); } else { // LR型 return leftRightRotate(root); } } // 右子树过高 if (balance -1) { if (value root-right-data) { // RR型 return leftRotate(root); } else { // RL型 return rightLeftRotate(root); } } return root; }五、完整代码演示c#include stdio.h #include stdlib.h typedef struct AVLNode { int data; struct AVLNode *left; struct AVLNode *right; int height; } AVLNode, *AVLTree; int getHeight(AVLNode *node) { return node NULL ? -1 : node-height; } int getBalanceFactor(AVLNode *node) { if (node NULL) return 0; return getHeight(node-left) - getHeight(node-right); } void updateHeight(AVLNode *node) { if (node NULL) return; int leftH getHeight(node-left); int rightH getHeight(node-right); node-height (leftH rightH ? leftH : rightH) 1; } AVLNode* rightRotate(AVLNode *y) { AVLNode *x y-left; AVLNode *T2 x-right; x-right y; y-left T2; updateHeight(y); updateHeight(x); return x; } AVLNode* leftRotate(AVLNode *y) { AVLNode *x y-right; AVLNode *T2 x-left; x-left y; y-right T2; updateHeight(y); updateHeight(x); return x; } AVLNode* leftRightRotate(AVLNode *node) { node-left leftRotate(node-left); return rightRotate(node); } AVLNode* rightLeftRotate(AVLNode *node) { node-right rightRotate(node-right); return leftRotate(node); } AVLNode* insert(AVLNode *root, int value) { if (root NULL) { AVLNode *newNode (AVLNode*)malloc(sizeof(AVLNode)); newNode-data value; newNode-left NULL; newNode-right NULL; newNode-height 0; return newNode; } if (value root-data) { root-left insert(root-left, value); } else if (value root-data) { root-right insert(root-right, value); } else { return root; } updateHeight(root); int balance getBalanceFactor(root); // LL if (balance 1 value root-left-data) { return rightRotate(root); } // RR if (balance -1 value root-right-data) { return leftRotate(root); } // LR if (balance 1 value root-left-data) { return leftRightRotate(root); } // RL if (balance -1 value root-right-data) { return rightLeftRotate(root); } return root; } void inorder(AVLNode *root) { if (root NULL) return; inorder(root-left); printf(%d , root-data); inorder(root-right); } void preorder(AVLNode *root) { if (root NULL) return; printf(%d , root-data); preorder(root-left); preorder(root-right); } void printTree(AVLNode *root, int level) { if (root NULL) return; printTree(root-right, level 1); for (int i 0; i level; i) printf( ); printf(%d(h%d,bf%d)\n, root-data, root-height, getBalanceFactor(root)); printTree(root-left, level 1); } int main() { AVLNode *root NULL; printf( 插入序列: 10, 20, 30, 40, 50, 25 \n); int values[] {10, 20, 30, 40, 50, 25}; for (int i 0; i 6; i) { root insert(root, values[i]); printf(\n插入 %d 后:\n, values[i]); printf(中序遍历: ); inorder(root); printf(\n); printf(树结构:\n); printTree(root, 0); } return 0; }运行结果text 插入序列: 10, 20, 30, 40, 50, 25 插入 10 后: 中序遍历: 10 树结构: 10(h0,bf0) 插入 20 后: 中序遍历: 10 20 树结构: 20(h1,bf-1) 10(h0,bf0) 插入 30 后: 中序遍历: 10 20 30 树结构: 30(h1,bf-1) 20(h0,bf0) 10(h0,bf0) 插入 40 后: 中序遍历: 10 20 30 40 树结构: 40(h2,bf-2) 30(h1,bf-1) 20(h0,bf0) 10(h0,bf0) 插入 50 后: 中序遍历: 10 20 30 40 50 树结构: 50(h2,bf-2) 40(h1,bf-1) 30(h0,bf0) 20(h0,bf0) 10(h0,bf0) 插入 25 后: 中序遍历: 10 20 25 30 40 50 树结构: 50(h2,bf-1) 40(h1,bf1) 30(h0,bf0) 25(h0,bf0) 20(h1,bf0) 10(h0,bf0)六、旋转判断总结平衡因子子树平衡因子类型操作1≥0LL右旋10LR左右旋-1≤0RR左旋-10RL右左旋记忆口诀LL左边太重右旋RR右边太重左旋LR左子树的右边太重先左旋左子再右旋RL右子树的左边太重先右旋右子再左旋七、复杂度分析操作时间复杂度说明查找O(log n)树高始终 log n插入O(log n)查找位置 旋转常数次删除O(log n)类似插入AVL树的树高严格控制在 log n 级别性能稳定。八、AVL树 vs 普通BST对比项普通BSTAVL树最坏查找O(n)O(log n)插入复杂度O(log n)平均O(log n)实现复杂度简单复杂需要旋转额外开销无每个节点存储高度适用场景数据随机数据有序或对性能要求高九、小结这一篇我们学习了AVL树要点说明平衡因子左高-右高取值-1,0,1LL右旋RR左旋LR左旋左子 右旋RL右旋右子 左旋插入BST插入 更新高度 旋转平衡核心思想在BST插入后从插入点向上检查平衡因子发现不平衡就旋转调整。下一篇我们讲红黑树原理与C语言模拟。十、思考题为什么AVL树的高度平衡能保证查找效率O(log n)在LR旋转中为什么需要先左旋再右旋直接右旋行不行如果插入序列是30,20,10会触发哪种旋转画图说明。尝试实现AVL树的删除操作。欢迎在评论区讨论你的答案。