平衡二叉树介绍平衡二叉搜索树AVL树是一种自平衡的二叉搜索树由两位前苏联数学家G.M. Adelson-Velsky和E.M. Landis于1962年发明其名称即取自他们姓氏的首字母。它通过在每次插入或删除节点后自动调整树的结构来保证其始终处于一种“高度平衡”的状态从而确保了高效的查找性能。平衡二叉树概念和特性1.什么是“平衡”AVL树的核心是引入了 平衡因子Balance Factor, BF 的概念。一个节点的平衡因子定义为其左子树的高度减去右子树的高度有时定义相反但原理相同。 在AVL树中每个节点的平衡因子只能是 -1、0 或 1。 这意味着任意节点的左右子树高度差绝对值不超过1。这确保了树形结构是平衡的避免了退化成链表。2.为什么需要平衡普通的二叉搜索树BST在极端情况下例如插入有序数据会退化成类似链表的结构导致其操作时间复杂度从理想的 O(log n) 恶化到 O(n)。 AVL树通过维持平衡保证了其查找、插入和删除操作的时间复杂度在平均和最坏情况下均为 O(log n)其中 n 是树中节点的数量。一个有 n 个节点的AVL树其最大深度约为 1.44 * log₂(n)。平衡二叉树核心操作当插入或删除节点后某些节点的平衡因子可能会变成 2 或 -2此时树就“失衡”了。为了恢复平衡AVL树会执行一种名为“旋转”的局部调整操作。旋转右旋Right Rotation—— 解决“左左LL”失衡场景节点 A 失衡平衡因子为 2且其左子节点 B 偏重平衡因子为 0 或 1。我们需要将 A 向右旋转让 B 成为新的根。旋转前的结构注意 B 的右子树 T2A/ \B T3 - T3 是 A 的右子树不受影响/ \T1 T2 - T2 是 B 的右子树它需要“过继”核心操作三步走1.暂存左子B A.left2.过继子树将 B 的右子树 T2 挂给 A 作为新的左子树 → A.left B.right3.完成旋转将 A 挂给 B 作为新的右子树 → B.right A旋转后的结构B/ \T1 A/ \T2 T3验证中序遍历旋转前顺序T1 - B - T2 - A - T3旋转后顺序T1 - B - T2 - A - T3完全一致证明了旋转不破坏二叉搜索树的性质左旋Left Rotation—— 解决“右右RR”失衡场景节点 A 失衡平衡因子为 -2且其右子节点 B 偏重。这是右旋的完美镜像。旋转前的结构注意 B 的左子树 T2 需要“过继”A/ \T1 B - T1 是 A 的左子树不受影响/ \T2 T3 - T2 是 B 的左子树它需要“过继”核心操作三步走1.暂存右子B A.right2.过继子树将 B 的左子树 T2 挂给 A 作为新的右子树 → A.right B.left3.完成旋转将 A 挂给 B 作为新的左子树 → B.left A旋转后的结构B/ \A T3/ \T1 T2验证中序遍历旋转前顺序T1 - A - T2 - B - T3旋转后顺序T1 - A - T2 - B - T3完全一致记忆口诀帮你快速区分右旋新根是 左孩子。把左孩子的右子树T2过继给旧根当左子树。左旋新根是 右孩子。把右孩子的左子树T2过继给旧根当右子树。一句话总结旋转就是“爷爷下来当孙子孙子上去当爷爷”关键是那棵被“过继”的子树它永远跟随新根原来的方向右旋时 T2 是左孩子的右子树所以过继后挂在右边左旋时 T2 是右孩子的左子树过继后挂在左边。源码/* 左旋 过继子树将q的左子树挂给p作为新的右子树 → p.right q.left 完成旋转将p挂给q作为新的左子树 → q.left p */voidAVLTree::levorotation(Node*p,Node*q,Node*s){//左旋操作q-parentp-parent;if(p-parentp-isLeftTree){p-parent-leftq;q-isLeftTreetrue;}elseif(p-parent){p-parent-rightq;q-isLeftTreefalse;}//将p挂到q的左子树q-parentp;p-isLeftTreetrue;p-rightq-left;q-leftp;}/* 右旋 过继子树将 q 的右子树挂给 p 作为新的左子树 → p.left q.right 完成旋转将 p 挂给 q 作为新的右子树 → q.right p */voidAVLTree::rightHandedRotation(Node*p,Node*q,Node*s){//右旋q-parentp-parent;if(p-parentp-isLeftTree){p-parent-leftq;q-isLeftTreetrue;}elseif(p-parent){p-parent-rightq;q-isLeftTreefalse;}//将p挂到q的右子树q-parentp;q-isLeftTreefalse;p-leftq-right;q-rightp;}2026-9-1修正旋转代码/* 左旋 过继子树将q的左子树挂给p作为新的右子树 → p.right q.left 完成旋转将p挂给q作为新的左子树 → q.left p */voidAVLTree::levorotation(Node*p,Node*q){//左旋操作//操作q中间节点q-parentp-parent;if(p-parentp-isLeftTree){p-parent-leftq;q-isLeftTreetrue;}elseif(p-parent){p-parent-rightq;q-isLeftTreefalse;}//修正一若删除节点为根节点则更新根节点else{rootNodeq;q-isLeftTreefalse;}//修正二节点操作有误应该操作的是p节点而不是q节点//操作p节点p-parentq;p-rightq-left;if(p-right){p-right-isLeftTreefalse;}q-leftp;p-isLeftTreetrue;}/* 右旋 过继子树将 q 的右子树挂给 p 作为新的左子树 → p.left q.right 完成旋转将 p 挂给 q 作为新的右子树 → q.right p */voidAVLTree::rightHandedRotation(Node*p,Node*q){//右旋//操作q节点q-parentp-parent;if(p-parentp-isLeftTree){p-parent-leftq;}elseif(p-parent){p-parent-rightq;q-isLeftTreefalse;}//修正一若删除节点为根节点则更新根节点else{rootNodeq;q-isLeftTreefalse;}//修正二节点操作有误应该操作的是p节点而不是q节点//操作p节点p-parentq;p-leftq-right;if(p-left){p-left-isLeftTreetrue;}q-rightp;p-isLeftTreefalse;}理解了这两个基础操作AVL树的LR和RL双旋就很容易了——它们只是连续调用两次单旋例如LR 先对左孩子左旋再对自身右旋。根据失衡节点的位置和形态主要有四种旋转方式失衡类型 描述 解决方法 1.LL (左左) 在节点A的左子树的左子树上插入节点导致失衡 对节点A执行一次右旋 (Right Rotation) 2.RR (右右) 在节点A的右子树的右子树上插入节点导致失衡 对节点A执行一次左旋 (Left Rotation) 3.LR (左右) 在节点A的左子树的右子树上插入节点导致失衡 先对A的左子节点左旋再对A右旋 4.RL (右左) 在节点A的右子树的左子树上插入节点导致失衡 先对A的右子节点右旋再对A左旋 通过这四种旋转操作AVL树能高效地恢复平衡。平衡二叉树优缺点与应用场景优点查找操作非常高效因为它是一种严格的平衡二叉树。缺点为了维护这种严格的平衡在插入和删除节点时可能需要进行多次旋转操作维护成本相对较高。因此AVL树适用于查找操作远多于插入和删除操作的场景例如数据库索引需要快速查找数据需要频繁查找的内存数据结构。早期曾被用于 Linux 内核中。 相比之下红黑树也是一种自平衡二叉搜索树但它是一种“弱平衡”树插入和删除操作更快因此在需要频繁增删改查的综合性场景如C STL的map和set中应用更广。下一篇讲解红黑树。平衡二叉树的操作AVL树的操作核心是在标准二叉搜索树BST操作的基础上增加“平衡维护”的步骤。具体来说查找操作和BST完全一致而插入和删除操作则在BST操作之后需要沿路径向上回溯检查平衡因子并在失衡时执行旋转。1.查找Search与普通BST完全相同时间复杂度稳定为 O(log n)。从根节点开始若目标值等于当前节点则返回小于则去左子树大于则去右子树。由于AVL树严格平衡查找过程不存在最坏情况链表退化的问题。源码见二叉搜索树BST Tree讲解2.插入Insert插入分三步走重点在于回溯和旋转第一步标准BST插入。从根节点出发按照BST规则将新节点插入为叶子节点。源码见二叉搜索树BST Tree讲解第二步更新平衡因子。从新插入的节点开始自底向上向根节点方向回溯更新沿途所有祖先节点的高度和平衡因子。第三步检查并修复失衡。在回溯过程中如果遇到某个节点A的平衡因子变为 2 或 -2说明以A为根的子树失衡。此时根据插入位置执行四种旋转之一插入在A的左子树的左子树LL对A执行右旋。插入在A的右子树的右子树RR对A执行左旋。插入在A的左子树的右子树LR先对A的左子节点左旋再对A右旋。插入在A的右子树的左子树RL先对A的右子节点右旋再对A左旋。关键特性在插入操作中一旦执行了旋转修复失衡点以上的祖先节点的平衡因子会自动恢复无需继续向上回溯因此插入操作最多只需要两次旋转LR或RL情况即可完成。插入源码//插入操作voidAVLTree::insert(intval){BinarySearchTree::insert(val);Node*pnullptr;//判断是否平衡if(isBalance(p)||pnullptr){//是平衡二叉树不需要调整return;}//需要调整//(p,q,s),左左型右右型右左型和左右型的旋转调整if(p-rightnullptr){//左左型和左右型Node*qp-left;if(q-rightnullptr){//左左型 右旋Node*sq-left;rightHandedRotation(p,q,s);}else{//左右型Node*sq-right;//先左旋levorotation(q,s,nullptr);//后右旋rightHandedRotation(p,s,q);}}else{//右右型和右左型Node*qp-right;if(q-leftnullptr){//右右型 左旋Node*sq-left;levorotation(p,q,s);}else{//右左型Node*sq-right;//先右旋rightHandedRotation(q,s,nullptr);//后左旋levorotation(p,s,q);}}}2026-9-1修正旋转代码Node*AVLTree::insert(intval){Node*sBinarySearchTree::insert(val);Node*pnullptr;Node*qnullptr;//修正一插入后找到第一个不平衡的节点并调整//判断是否平衡if(!firstUnBalance(s,p,q)){//是平衡二叉树不需要调整returns;}//需要调整//(p,q,s),左左型右右型右左型和左右型的旋转调整if(q-isLeftTreetrue){//左左型和左右型if(s-isLeftTreetrue){//左左型 右旋rightHandedRotation(p,q);}else{//先左旋levorotation(q,s);//后右旋rightHandedRotation(p,s);}}else{//右右型和右左型if(s-isLeftTreefalse){//右右型 左旋levorotation(p,q);}else{//右左型//先右旋rightHandedRotation(q,s);//后左旋levorotation(p,s);}}}3.删除Delete平衡二叉搜索树讲解二 
长河君 · 2026/9/2 7:29:18 · 阅读 1.2k 平衡二叉搜索树讲解
平衡二叉树介绍平衡二叉搜索树AVL树是一种自平衡的二叉搜索树由两位前苏联数学家G.M. Adelson-Velsky和E.M. Landis于1962年发明其名称即取自他们姓氏的首字母。它通过在每次插入或删除节点后自动调整树的结构来保证其始终处于一种“高度平衡”的状态从而确保了高效的查找性能。平衡二叉树概念和特性1.什么是“平衡”AVL树的核心是引入了 平衡因子Balance Factor, BF 的概念。一个节点的平衡因子定义为其左子树的高度减去右子树的高度有时定义相反但原理相同。 在AVL树中每个节点的平衡因子只能是 -1、0 或 1。 这意味着任意节点的左右子树高度差绝对值不超过1。这确保了树形结构是平衡的避免了退化成链表。2.为什么需要平衡普通的二叉搜索树BST在极端情况下例如插入有序数据会退化成类似链表的结构导致其操作时间复杂度从理想的 O(log n) 恶化到 O(n)。 AVL树通过维持平衡保证了其查找、插入和删除操作的时间复杂度在平均和最坏情况下均为 O(log n)其中 n 是树中节点的数量。一个有 n 个节点的AVL树其最大深度约为 1.44 * log₂(n)。平衡二叉树核心操作当插入或删除节点后某些节点的平衡因子可能会变成 2 或 -2此时树就“失衡”了。为了恢复平衡AVL树会执行一种名为“旋转”的局部调整操作。旋转右旋Right Rotation—— 解决“左左LL”失衡场景节点 A 失衡平衡因子为 2且其左子节点 B 偏重平衡因子为 0 或 1。我们需要将 A 向右旋转让 B 成为新的根。旋转前的结构注意 B 的右子树 T2A/ \B T3 - T3 是 A 的右子树不受影响/ \T1 T2 - T2 是 B 的右子树它需要“过继”核心操作三步走1.暂存左子B A.left2.过继子树将 B 的右子树 T2 挂给 A 作为新的左子树 → A.left B.right3.完成旋转将 A 挂给 B 作为新的右子树 → B.right A旋转后的结构B/ \T1 A/ \T2 T3验证中序遍历旋转前顺序T1 - B - T2 - A - T3旋转后顺序T1 - B - T2 - A - T3完全一致证明了旋转不破坏二叉搜索树的性质左旋Left Rotation—— 解决“右右RR”失衡场景节点 A 失衡平衡因子为 -2且其右子节点 B 偏重。这是右旋的完美镜像。旋转前的结构注意 B 的左子树 T2 需要“过继”A/ \T1 B - T1 是 A 的左子树不受影响/ \T2 T3 - T2 是 B 的左子树它需要“过继”核心操作三步走1.暂存右子B A.right2.过继子树将 B 的左子树 T2 挂给 A 作为新的右子树 → A.right B.left3.完成旋转将 A 挂给 B 作为新的左子树 → B.left A旋转后的结构B/ \A T3/ \T1 T2验证中序遍历旋转前顺序T1 - A - T2 - B - T3旋转后顺序T1 - A - T2 - B - T3完全一致记忆口诀帮你快速区分右旋新根是 左孩子。把左孩子的右子树T2过继给旧根当左子树。左旋新根是 右孩子。把右孩子的左子树T2过继给旧根当右子树。一句话总结旋转就是“爷爷下来当孙子孙子上去当爷爷”关键是那棵被“过继”的子树它永远跟随新根原来的方向右旋时 T2 是左孩子的右子树所以过继后挂在右边左旋时 T2 是右孩子的左子树过继后挂在左边。源码/* 左旋 过继子树将q的左子树挂给p作为新的右子树 → p.right q.left 完成旋转将p挂给q作为新的左子树 → q.left p */voidAVLTree::levorotation(Node*p,Node*q,Node*s){//左旋操作q-parentp-parent;if(p-parentp-isLeftTree){p-parent-leftq;q-isLeftTreetrue;}elseif(p-parent){p-parent-rightq;q-isLeftTreefalse;}//将p挂到q的左子树q-parentp;p-isLeftTreetrue;p-rightq-left;q-leftp;}/* 右旋 过继子树将 q 的右子树挂给 p 作为新的左子树 → p.left q.right 完成旋转将 p 挂给 q 作为新的右子树 → q.right p */voidAVLTree::rightHandedRotation(Node*p,Node*q,Node*s){//右旋q-parentp-parent;if(p-parentp-isLeftTree){p-parent-leftq;q-isLeftTreetrue;}elseif(p-parent){p-parent-rightq;q-isLeftTreefalse;}//将p挂到q的右子树q-parentp;q-isLeftTreefalse;p-leftq-right;q-rightp;}2026-9-1修正旋转代码/* 左旋 过继子树将q的左子树挂给p作为新的右子树 → p.right q.left 完成旋转将p挂给q作为新的左子树 → q.left p */voidAVLTree::levorotation(Node*p,Node*q){//左旋操作//操作q中间节点q-parentp-parent;if(p-parentp-isLeftTree){p-parent-leftq;q-isLeftTreetrue;}elseif(p-parent){p-parent-rightq;q-isLeftTreefalse;}//修正一若删除节点为根节点则更新根节点else{rootNodeq;q-isLeftTreefalse;}//修正二节点操作有误应该操作的是p节点而不是q节点//操作p节点p-parentq;p-rightq-left;if(p-right){p-right-isLeftTreefalse;}q-leftp;p-isLeftTreetrue;}/* 右旋 过继子树将 q 的右子树挂给 p 作为新的左子树 → p.left q.right 完成旋转将 p 挂给 q 作为新的右子树 → q.right p */voidAVLTree::rightHandedRotation(Node*p,Node*q){//右旋//操作q节点q-parentp-parent;if(p-parentp-isLeftTree){p-parent-leftq;}elseif(p-parent){p-parent-rightq;q-isLeftTreefalse;}//修正一若删除节点为根节点则更新根节点else{rootNodeq;q-isLeftTreefalse;}//修正二节点操作有误应该操作的是p节点而不是q节点//操作p节点p-parentq;p-leftq-right;if(p-left){p-left-isLeftTreetrue;}q-rightp;p-isLeftTreefalse;}理解了这两个基础操作AVL树的LR和RL双旋就很容易了——它们只是连续调用两次单旋例如LR 先对左孩子左旋再对自身右旋。根据失衡节点的位置和形态主要有四种旋转方式失衡类型 描述 解决方法 1.LL (左左) 在节点A的左子树的左子树上插入节点导致失衡 对节点A执行一次右旋 (Right Rotation) 2.RR (右右) 在节点A的右子树的右子树上插入节点导致失衡 对节点A执行一次左旋 (Left Rotation) 3.LR (左右) 在节点A的左子树的右子树上插入节点导致失衡 先对A的左子节点左旋再对A右旋 4.RL (右左) 在节点A的右子树的左子树上插入节点导致失衡 先对A的右子节点右旋再对A左旋 通过这四种旋转操作AVL树能高效地恢复平衡。平衡二叉树优缺点与应用场景优点查找操作非常高效因为它是一种严格的平衡二叉树。缺点为了维护这种严格的平衡在插入和删除节点时可能需要进行多次旋转操作维护成本相对较高。因此AVL树适用于查找操作远多于插入和删除操作的场景例如数据库索引需要快速查找数据需要频繁查找的内存数据结构。早期曾被用于 Linux 内核中。 相比之下红黑树也是一种自平衡二叉搜索树但它是一种“弱平衡”树插入和删除操作更快因此在需要频繁增删改查的综合性场景如C STL的map和set中应用更广。下一篇讲解红黑树。平衡二叉树的操作AVL树的操作核心是在标准二叉搜索树BST操作的基础上增加“平衡维护”的步骤。具体来说查找操作和BST完全一致而插入和删除操作则在BST操作之后需要沿路径向上回溯检查平衡因子并在失衡时执行旋转。1.查找Search与普通BST完全相同时间复杂度稳定为 O(log n)。从根节点开始若目标值等于当前节点则返回小于则去左子树大于则去右子树。由于AVL树严格平衡查找过程不存在最坏情况链表退化的问题。源码见二叉搜索树BST Tree讲解2.插入Insert插入分三步走重点在于回溯和旋转第一步标准BST插入。从根节点出发按照BST规则将新节点插入为叶子节点。源码见二叉搜索树BST Tree讲解第二步更新平衡因子。从新插入的节点开始自底向上向根节点方向回溯更新沿途所有祖先节点的高度和平衡因子。第三步检查并修复失衡。在回溯过程中如果遇到某个节点A的平衡因子变为 2 或 -2说明以A为根的子树失衡。此时根据插入位置执行四种旋转之一插入在A的左子树的左子树LL对A执行右旋。插入在A的右子树的右子树RR对A执行左旋。插入在A的左子树的右子树LR先对A的左子节点左旋再对A右旋。插入在A的右子树的左子树RL先对A的右子节点右旋再对A左旋。关键特性在插入操作中一旦执行了旋转修复失衡点以上的祖先节点的平衡因子会自动恢复无需继续向上回溯因此插入操作最多只需要两次旋转LR或RL情况即可完成。插入源码//插入操作voidAVLTree::insert(intval){BinarySearchTree::insert(val);Node*pnullptr;//判断是否平衡if(isBalance(p)||pnullptr){//是平衡二叉树不需要调整return;}//需要调整//(p,q,s),左左型右右型右左型和左右型的旋转调整if(p-rightnullptr){//左左型和左右型Node*qp-left;if(q-rightnullptr){//左左型 右旋Node*sq-left;rightHandedRotation(p,q,s);}else{//左右型Node*sq-right;//先左旋levorotation(q,s,nullptr);//后右旋rightHandedRotation(p,s,q);}}else{//右右型和右左型Node*qp-right;if(q-leftnullptr){//右右型 左旋Node*sq-left;levorotation(p,q,s);}else{//右左型Node*sq-right;//先右旋rightHandedRotation(q,s,nullptr);//后左旋levorotation(p,s,q);}}}2026-9-1修正旋转代码Node*AVLTree::insert(intval){Node*sBinarySearchTree::insert(val);Node*pnullptr;Node*qnullptr;//修正一插入后找到第一个不平衡的节点并调整//判断是否平衡if(!firstUnBalance(s,p,q)){//是平衡二叉树不需要调整returns;}//需要调整//(p,q,s),左左型右右型右左型和左右型的旋转调整if(q-isLeftTreetrue){//左左型和左右型if(s-isLeftTreetrue){//左左型 右旋rightHandedRotation(p,q);}else{//先左旋levorotation(q,s);//后右旋rightHandedRotation(p,s);}}else{//右右型和右左型if(s-isLeftTreefalse){//右右型 左旋levorotation(p,q);}else{//右左型//先右旋rightHandedRotation(q,s);//后左旋levorotation(p,s);}}}3.删除Delete平衡二叉搜索树讲解二