7.AVL 树：第一个自平衡二叉搜索树-网站名

一、什么是 AVL 树AVL 树是第一个自平衡二叉搜索树1962 年由 Adelson-Velsky 和 Landis 提出。它解决了普通二叉搜索树在插入有序数据时退化成链表的问题通过自动旋转保持树的平衡让查找、插入、删除操作的时间复杂度始终维持在O(log n)。AVL 树的核心特点每个节点维护一个平衡因子BF左子树高度 - 右子树高度平衡因子的绝对值 ≤ 1否则触发旋转修复支持四种旋转方式LL右旋、RR左旋、LR先左旋再右旋、RL先右旋再左旋。二、为什么需要 AVL 树普通二叉搜索树在插入有序数据时会退化成一条链表此时查找效率从O(log n)降到O(n)严重影响性能。例如依次插入 10、20、30、40、50普通二叉搜索树会变成一条右斜的链表10 \ 20 \ 30 \ 40 \ 50此时查找 50 需要遍历所有节点效率极低。AVL 树通过自动旋转始终保持树的平衡避免了这种情况。三、AVL 树的核心概念1. 平衡因子BF平衡因子左子树高度 - 右子树高度AVL 树要求所有节点的平衡因子满足|BF| ≤ 1树是平衡的|BF| 2树失去平衡需要旋转修复。2. 四种旋转方式根据失衡的类型AVL 树有四种旋转修复方式LL左左失衡左子树的左子树插入节点导致失衡需要右旋RR右右失衡右子树的右子树插入节点导致失衡需要左旋LR左右失衡左子树的右子树插入节点导致失衡需要先左旋再右旋RL右左失衡右子树的左子树插入节点导致失衡需要先右旋再左旋。四、AVL 树的节点定义AVL 树的节点需要维护数据、左右子节点指针、高度三个信息对应的 C 语言代码定义如下// AVL树节点结构体 typedef struct AVLNode { int val; // 数据域 struct AVLNode* left; // 左子节点指针 struct AVLNode* right; // 右子节点指针 int height; // 节点高度 } AVLNode;五、AVL 树的基本操作1. 获取节点高度获取节点的高度空节点的高度为 0// 获取节点高度 int getHeight(AVLNode* node) { if (node NULL) return 0; return node-height; }2. 计算平衡因子计算节点的平衡因子// 计算平衡因子 int getBalance(AVLNode* node) { if (node NULL) return 0; return getHeight(node-left) - getHeight(node-right); }3. 创建新节点创建一个新的 AVL 树节点初始化高度为 1// 创建新节点 AVLNode* createAVLNode(int val) { AVLNode* node (AVLNode*)malloc(sizeof(AVLNode)); node-val val; node-left NULL; node-right NULL; node-height 1; // 新节点高度为1 return node; }4. 右旋LL 失衡修复当左子树的左子树插入节点导致失衡时需要右旋// 右旋LL失衡修复 AVLNode* rightRotate(AVLNode* y) { AVLNode* x y-left; AVLNode* T2 x-right; // 旋转 x-right y; y-left T2; // 更新高度 y-height 1 (getHeight(y-left) getHeight(y-right) ? getHeight(y-left) : getHeight(y-right)); x-height 1 (getHeight(x-left) getHeight(x-right) ? getHeight(x-left) : getHeight(x-right)); // 返回新的根节点 return x; }5. 左旋RR 失衡修复当右子树的右子树插入节点导致失衡时需要左旋// 左旋RR失衡修复 AVLNode* leftRotate(AVLNode* x) { AVLNode* y x-right; AVLNode* T2 y-left; // 旋转 y-left x; x-right T2; // 更新高度 x-height 1 (getHeight(x-left) getHeight(x-right) ? getHeight(x-left) : getHeight(x-right)); y-height 1 (getHeight(y-left) getHeight(y-right) ? getHeight(y-left) : getHeight(y-right)); // 返回新的根节点 return y; }6. 插入节点插入节点后自动检查平衡因子触发旋转修复// 插入节点 AVLNode* insertAVLNode(AVLNode* node, int val) { // 1. 执行普通二叉搜索树的插入 if (node NULL) return createAVLNode(val); if (val node-val) { node-left insertAVLNode(node-left, val); } else if (val node-val) { node-right insertAVLNode(node-right, val); } else { return node; // 重复节点不插入 } // 2. 更新当前节点的高度 node-height 1 (getHeight(node-left) getHeight(node-right) ? getHeight(node-left) : getHeight(node-right)); // 3. 计算平衡因子判断是否失衡 int balance getBalance(node); // 4. 修复失衡 // LL失衡右旋 if (balance 1 val node-left-val) { return rightRotate(node); } // RR失衡左旋 if (balance -1 val node-right-val) { return leftRotate(node); } // LR失衡先左旋再右旋 if (balance 1 val node-left-val) { node-left leftRotate(node-left); return rightRotate(node); } // RL失衡先右旋再左旋 if (balance -1 val node-right-val) { node-right rightRotate(node-right); return leftRotate(node); } // 5. 未失衡返回原节点 return node; }7. 中序遍历AVL 树的中序遍历结果是有序的// 中序遍历 void inorderAVL(AVLNode* root) { if (root NULL) return; inorderAVL(root-left); printf(%d , root-val); inorderAVL(root-right); }六、完整代码示例#include stdio.h #include stdlib.h // AVL树节点结构体 typedef struct AVLNode { int val; struct AVLNode* left; struct AVLNode* right; int height; } AVLNode; // 获取节点高度 int getHeight(AVLNode* node) { if (node NULL) return 0; return node-height; } // 计算平衡因子 int getBalance(AVLNode* node) { if (node NULL) return 0; return getHeight(node-left) - getHeight(node-right); } // 创建新节点 AVLNode* createAVLNode(int val) { AVLNode* node (AVLNode*)malloc(sizeof(AVLNode)); node-val val; node-left NULL; node-right NULL; node-height 1; return node; } // 右旋LL失衡修复 AVLNode* rightRotate(AVLNode* y) { AVLNode* x y-left; AVLNode* T2 x-right; x-right y; y-left T2; y-height 1 (getHeight(y-left) getHeight(y-right) ? getHeight(y-left) : getHeight(y-right)); x-height 1 (getHeight(x-left) getHeight(x-right) ? getHeight(x-left) : getHeight(x-right)); return x; } // 左旋RR失衡修复 AVLNode* leftRotate(AVLNode* x) { AVLNode* y x-right; AVLNode* T2 y-left; y-left x; x-right T2; x-height 1 (getHeight(x-left) getHeight(x-right) ? getHeight(x-left) : getHeight(x-right)); y-height 1 (getHeight(y-left) getHeight(y-right) ? getHeight(y-left) : getHeight(y-right)); return y; } // 插入节点 AVLNode* insertAVLNode(AVLNode* node, int val) { if (node NULL) return createAVLNode(val); if (val node-val) { node-left insertAVLNode(node-left, val); } else if (val node-val) { node-right insertAVLNode(node-right, val); } else { return node; } node-height 1 (getHeight(node-left) getHeight(node-right) ? getHeight(node-left) : getHeight(node-right)); int balance getBalance(node); // LL失衡 if (balance 1 val node-left-val) { return rightRotate(node); } // RR失衡 if (balance -1 val node-right-val) { return leftRotate(node); } // LR失衡 if (balance 1 val node-left-val) { node-left leftRotate(node-left); return rightRotate(node); } // RL失衡 if (balance -1 val node-right-val) { node-right rightRotate(node-right); return leftRotate(node); } return node; } // 中序遍历 void inorderAVL(AVLNode* root) { if (root NULL) return; inorderAVL(root-left); printf(%d , root-val); inorderAVL(root-right); } // 释放AVL树内存 void freeAVLTree(AVLNode* root) { if (root NULL) return; freeAVLTree(root-left); freeAVLTree(root-right); free(root); } int main() { AVLNode* root NULL; // 插入有序数据测试AVL树的自平衡能力 root insertAVLNode(root, 10); root insertAVLNode(root, 20); root insertAVLNode(root, 30); root insertAVLNode(root, 40); root insertAVLNode(root, 50); root insertAVLNode(root, 25); // 中序遍历结果应该是有序的 printf(中序遍历结果); inorderAVL(root); // 输出10 20 25 30 40 50 printf(\n); // 释放内存 freeAVLTree(root); printf(内存已释放\n); return 0; }七、AVL 树的实际应用场景AVL 树在实际开发中应用非常广泛常见场景包括数据库索引早期的数据库索引使用 AVL 树保证查询效率C STLstd::map和std::set的底层实现就是平衡树的思想现代实现多为红黑树文件系统部分文件系统使用 AVL 树管理目录结构提高查找效率编译器编译器的符号表使用 AVL 树存储保证符号查找的高效性实时系统AVL 树的操作时间稳定适合对响应时间要求严格的实时系统。八、总结AVL 树是第一个自平衡二叉搜索树通过维护平衡因子和自动旋转解决了普通二叉搜索树在插入有序数据时退化成链表的问题让查找、插入、删除操作的时间复杂度始终维持在O(log n)。AVL 树的核心是四种旋转方式LL右旋、RR左旋、LR先左旋再右旋、RL先右旋再左旋通过旋转修复失衡保持树的平衡。在实际开发中AVL 树是平衡树的基础后续的红黑树、B 树等都是在 AVL 树的基础上发展而来的是算法和开发中不可或缺的基础数据结构。希望这篇文章能帮助你深入理解 AVL 树的原理和实现

资讯详情

7.AVL 树：第一个自平衡二叉搜索树