一.AVL树的概念AVL树AVL Tree是一种自平衡二叉搜索树Self-Balancing Binary Search Tree由Adelson-Velsky 和 Landis于 1962 年提出因此得名 AVL。AVL树的特点对于树中的任意节点左子树和右子树的高度差不超过左右子树也必须分别是 AVL 树定义平衡因子Balance FactorBFh(左子树)−h(右子树)AVL树要求BF∈{−1,0,1}每个结点都有⼀个平衡因⼦任何 结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度也就是说任何结点的平衡因⼦等于0/1/-1 AVL树并不是必须要平衡因⼦但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡 就像⼀个⻛向标⼀样二.AVL树的插入1. AVL树插入⼀个值的大概过程1. 插入⼀个值按二叉搜索树规则进行插入。2. 新增结点以后只会影响祖先结点的高度也就是可能会影响部分祖先结点的平衡因子所以更新 从新增结点-根结点路径上的平衡因子实际中最坏情况下要更新到根有些情况更新到中间就可以停止了具体情况我们下面再详细分析。3. 更新平衡因子过程中没有出现问题则插入结束4. 更新平衡因子过程中出现不平衡对不平衡子树旋转旋转后调平衡的同时本质降低了子树 的高度不会再影响上一层所以插入结束2.平衡因子更新原则• 平衡因子右子树高度-左子树高度• 只有子树高度变化才会影响当前结点平衡因子。• 插入结点会增加高度所以新增结点在parent的右子树parent的平衡因⼦新增结点在 parent的左⼦树parent平衡因⼦--• parent所在⼦树的高度是否变化决定了是否会继续往上更新更新停止条件• 更新后parent的平衡因⼦等于0更新中parent的平衡因⼦变化为-1-0或者1-0说明更新前 parent⼦树⼀边⾼⼀边低新增的结点插⼊在低的那边插⼊后parent所在的⼦树⾼度不变不会 影响parent的⽗亲结点的平衡因⼦更新结束。• 更新后parent的平衡因⼦等于1或-1更新前更新中parent的平衡因⼦变化为0-1或者0--1说 明更新前parent⼦树两边⼀样⾼新增的插⼊结点后parent所在的⼦树⼀边⾼⼀边低parent所 在的⼦树符合平衡要求但是⾼度增加了1会影响parent的⽗亲结点的平衡因⼦所以要继续向 上更新。• 更新后parent的平衡因⼦等于2或-2更新前更新中parent的平衡因⼦变化为1-2或者-1--2说 明更新前parent⼦树⼀边⾼⼀边低新增的插⼊结点在⾼的那边parent所在的⼦树⾼的那边更⾼ 了破坏了平衡parent所在的⼦树不符合平衡要求需要旋转处理旋转的⽬标有两个1、把 parent⼦树旋转平衡。2、降低parent⼦树的⾼度恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新插⼊结束。• 不断更新更新到根根的平衡因⼦是1或-1也停⽌了更新到10结点平衡因⼦为210所在的⼦树已经不平衡需要旋转处理更新到中间结点3为根的⼦树⾼度不变不会影响上⼀层更新结束最坏更新到根停止3.插入结点及更新平衡因子的代码实现三.旋转1.旋转的原则1. 保持搜索树的规则2. 让旋转的树从不满⾜变平衡其次降低旋转树的⾼度 旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。2.右单旋图中展示的是10为根的树有a/b/c抽象为三棵⾼度为h的⼦树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树 是⼀种概括抽象表⽰他代表了所有右单旋的场景• 在a⼦树中插⼊⼀个新结点导致a⼦树的⾼度从h变成h1不断向上更新平衡因⼦导致10的平 衡因⼦从-1变成-210为根的树左右⾼度差超过1违反平衡规则。10为根的树左边太⾼了需要 往右边旋转控制两棵树的平衡。•旋转核⼼步骤因为5b子树的值10将b变成10的左⼦树10变成5的右⼦树5变成这棵树新 的根符合搜索树的规则控制了平衡同时这棵的⾼度恢复到了插⼊之前的h2符合旋转原 则。如果插⼊之前10整棵树的⼀个局部⼦树旋转后不会再影响上⼀层插⼊结束了。3.右单旋代码实现4.左单旋图中展⽰的是10为根的树有a/b/c抽象为三棵⾼度为h的⼦树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树 是⼀种概括抽象表⽰他代表了所有右单旋的场景在a⼦树中插⼊⼀个新结点导致a⼦树的⾼度从h变成h1不断向上更新平衡因⼦导致10的平 衡因⼦从1变成210为根的树左右⾼度差超过1违反平衡规则。10为根的树右边太⾼了需要往 左边旋转控制两棵树的平衡。旋转核⼼步骤因为10b⼦树的值15,将b变成10的右⼦树10变成15的左⼦树15变成这棵 树新的根符合搜索树的规则控制了平衡同时这棵的⾼度恢复到了插⼊之前的h2符合旋转 原则。如果插⼊之前10整棵树的⼀个局部⼦树旋转后不会再影响上⼀层插⼊结束了。4.左单旋代码实现5.左右双旋图中可以看到左边⾼时如果插⼊位置不是在a⼦树⽽是插⼊在b⼦树b⼦树⾼度从h变 成h1引发旋转右单旋⽆法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯粹的左边 ⾼但是插⼊在b⼦树中10为跟的⼦树不再是单纯的左边⾼对于10是左边⾼但是对于5是右边 ⾼需要⽤两次旋转才能解决以5为旋转点进⾏⼀个左单旋以10为旋转点进⾏⼀个右单旋这棵树 这棵树就平衡了我们将a/b/c⼦树抽象为⾼度h的AVL ⼦树进⾏分析另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树因为 我们要对b的⽗亲5为旋转点进⾏左单旋左单旋需要动b树中的左⼦树。b⼦树中新增结点的位置 不同平衡因⼦更新的细节也不同通过观察8的平衡因⼦不同这⾥我们要分三个场景讨论。• 场景1h1时新增结点插⼊在e⼦树e⼦树⾼度从h-1并为h并不断更新8-5-10平衡因⼦ 引发旋转其中8的平衡因⼦为-1旋转后8和5平衡因⼦为010平衡因⼦为1。• 场景2h1时新增结点插⼊在f⼦树f⼦树⾼度从h-1变为h并不断更新8-5-10平衡因⼦引 发旋转其中8的平衡因⼦为1旋转后8和10平衡因⼦为05平衡因⼦为-1。• 场景3h0时a/b/c都是空树b⾃⼰就是⼀个新增结点不断更新5-10平衡因⼦引发旋 转其中8的平衡因⼦为0旋转后8和10和5平衡因⼦均为06.左右双旋代码实现7.右左双旋跟左右双旋类似下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析另外我们需要把b⼦树的 细节进⼀步展开为12和左⼦树⾼度为h-1的e和f⼦树因为我们要对b的⽗亲15为旋转点进⾏右单 旋右单旋需要动b树中的右⼦树。b⼦树中新增结点的位置不同平衡因⼦更新的细节也不同通 过观察12的平衡因⼦不同这⾥我们要分三个场景讨论。• 场景1h1时新增结点插⼊在e⼦树e⼦树⾼度从h-1变为h并不断更新12-15-10平衡因 ⼦引发旋转其中12的平衡因⼦为-1旋转后10和12平衡因⼦为015平衡因⼦为1。• 场景2h1时新增结点插⼊在f⼦树f⼦树⾼度从h-1变为h并不断更新12-15-10平衡因⼦ 引发旋转其中12的平衡因⼦为1旋转后15和12平衡因⼦为010平衡因⼦为-1。• 场景3h0时a/b/c都是空树b⾃⼰就是⼀个新增结点不断更新15-10平衡因⼦引发旋 转其中12的平衡因⼦为0旋转后10和12和15平衡因⼦均为08.右左双旋代码实现四.AVL树平衡检测我们实现的AVL树是否合格我们通过检查左右⼦树⾼度差的的程序进⾏反向验证同时检查⼀下结点 的平衡因⼦更新是否出现了问题
C++进阶 AVL树
发布时间：2026/6/3 23:05:10
一.AVL树的概念AVL树AVL Tree是一种自平衡二叉搜索树Self-Balancing Binary Search Tree由Adelson-Velsky 和 Landis于 1962 年提出因此得名 AVL。AVL树的特点对于树中的任意节点左子树和右子树的高度差不超过左右子树也必须分别是 AVL 树定义平衡因子Balance FactorBFh(左子树)−h(右子树)AVL树要求BF∈{−1,0,1}每个结点都有⼀个平衡因⼦任何 结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度也就是说任何结点的平衡因⼦等于0/1/-1 AVL树并不是必须要平衡因⼦但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡 就像⼀个⻛向标⼀样二.AVL树的插入1. AVL树插入⼀个值的大概过程1. 插入⼀个值按二叉搜索树规则进行插入。2. 新增结点以后只会影响祖先结点的高度也就是可能会影响部分祖先结点的平衡因子所以更新 从新增结点-根结点路径上的平衡因子实际中最坏情况下要更新到根有些情况更新到中间就可以停止了具体情况我们下面再详细分析。3. 更新平衡因子过程中没有出现问题则插入结束4. 更新平衡因子过程中出现不平衡对不平衡子树旋转旋转后调平衡的同时本质降低了子树 的高度不会再影响上一层所以插入结束2.平衡因子更新原则• 平衡因子右子树高度-左子树高度• 只有子树高度变化才会影响当前结点平衡因子。• 插入结点会增加高度所以新增结点在parent的右子树parent的平衡因⼦新增结点在 parent的左⼦树parent平衡因⼦--• parent所在⼦树的高度是否变化决定了是否会继续往上更新更新停止条件• 更新后parent的平衡因⼦等于0更新中parent的平衡因⼦变化为-1-0或者1-0说明更新前 parent⼦树⼀边⾼⼀边低新增的结点插⼊在低的那边插⼊后parent所在的⼦树⾼度不变不会 影响parent的⽗亲结点的平衡因⼦更新结束。• 更新后parent的平衡因⼦等于1或-1更新前更新中parent的平衡因⼦变化为0-1或者0--1说 明更新前parent⼦树两边⼀样⾼新增的插⼊结点后parent所在的⼦树⼀边⾼⼀边低parent所 在的⼦树符合平衡要求但是⾼度增加了1会影响parent的⽗亲结点的平衡因⼦所以要继续向 上更新。• 更新后parent的平衡因⼦等于2或-2更新前更新中parent的平衡因⼦变化为1-2或者-1--2说 明更新前parent⼦树⼀边⾼⼀边低新增的插⼊结点在⾼的那边parent所在的⼦树⾼的那边更⾼ 了破坏了平衡parent所在的⼦树不符合平衡要求需要旋转处理旋转的⽬标有两个1、把 parent⼦树旋转平衡。2、降低parent⼦树的⾼度恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新插⼊结束。• 不断更新更新到根根的平衡因⼦是1或-1也停⽌了更新到10结点平衡因⼦为210所在的⼦树已经不平衡需要旋转处理更新到中间结点3为根的⼦树⾼度不变不会影响上⼀层更新结束最坏更新到根停止3.插入结点及更新平衡因子的代码实现三.旋转1.旋转的原则1. 保持搜索树的规则2. 让旋转的树从不满⾜变平衡其次降低旋转树的⾼度 旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。2.右单旋图中展示的是10为根的树有a/b/c抽象为三棵⾼度为h的⼦树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树 是⼀种概括抽象表⽰他代表了所有右单旋的场景• 在a⼦树中插⼊⼀个新结点导致a⼦树的⾼度从h变成h1不断向上更新平衡因⼦导致10的平 衡因⼦从-1变成-210为根的树左右⾼度差超过1违反平衡规则。10为根的树左边太⾼了需要 往右边旋转控制两棵树的平衡。•旋转核⼼步骤因为5b子树的值10将b变成10的左⼦树10变成5的右⼦树5变成这棵树新 的根符合搜索树的规则控制了平衡同时这棵的⾼度恢复到了插⼊之前的h2符合旋转原 则。如果插⼊之前10整棵树的⼀个局部⼦树旋转后不会再影响上⼀层插⼊结束了。3.右单旋代码实现4.左单旋图中展⽰的是10为根的树有a/b/c抽象为三棵⾼度为h的⼦树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树 是⼀种概括抽象表⽰他代表了所有右单旋的场景在a⼦树中插⼊⼀个新结点导致a⼦树的⾼度从h变成h1不断向上更新平衡因⼦导致10的平 衡因⼦从1变成210为根的树左右⾼度差超过1违反平衡规则。10为根的树右边太⾼了需要往 左边旋转控制两棵树的平衡。旋转核⼼步骤因为10b⼦树的值15,将b变成10的右⼦树10变成15的左⼦树15变成这棵 树新的根符合搜索树的规则控制了平衡同时这棵的⾼度恢复到了插⼊之前的h2符合旋转 原则。如果插⼊之前10整棵树的⼀个局部⼦树旋转后不会再影响上⼀层插⼊结束了。4.左单旋代码实现5.左右双旋图中可以看到左边⾼时如果插⼊位置不是在a⼦树⽽是插⼊在b⼦树b⼦树⾼度从h变 成h1引发旋转右单旋⽆法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯粹的左边 ⾼但是插⼊在b⼦树中10为跟的⼦树不再是单纯的左边⾼对于10是左边⾼但是对于5是右边 ⾼需要⽤两次旋转才能解决以5为旋转点进⾏⼀个左单旋以10为旋转点进⾏⼀个右单旋这棵树 这棵树就平衡了我们将a/b/c⼦树抽象为⾼度h的AVL ⼦树进⾏分析另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树因为 我们要对b的⽗亲5为旋转点进⾏左单旋左单旋需要动b树中的左⼦树。b⼦树中新增结点的位置 不同平衡因⼦更新的细节也不同通过观察8的平衡因⼦不同这⾥我们要分三个场景讨论。• 场景1h1时新增结点插⼊在e⼦树e⼦树⾼度从h-1并为h并不断更新8-5-10平衡因⼦ 引发旋转其中8的平衡因⼦为-1旋转后8和5平衡因⼦为010平衡因⼦为1。• 场景2h1时新增结点插⼊在f⼦树f⼦树⾼度从h-1变为h并不断更新8-5-10平衡因⼦引 发旋转其中8的平衡因⼦为1旋转后8和10平衡因⼦为05平衡因⼦为-1。• 场景3h0时a/b/c都是空树b⾃⼰就是⼀个新增结点不断更新5-10平衡因⼦引发旋 转其中8的平衡因⼦为0旋转后8和10和5平衡因⼦均为06.左右双旋代码实现7.右左双旋跟左右双旋类似下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析另外我们需要把b⼦树的 细节进⼀步展开为12和左⼦树⾼度为h-1的e和f⼦树因为我们要对b的⽗亲15为旋转点进⾏右单 旋右单旋需要动b树中的右⼦树。b⼦树中新增结点的位置不同平衡因⼦更新的细节也不同通 过观察12的平衡因⼦不同这⾥我们要分三个场景讨论。• 场景1h1时新增结点插⼊在e⼦树e⼦树⾼度从h-1变为h并不断更新12-15-10平衡因 ⼦引发旋转其中12的平衡因⼦为-1旋转后10和12平衡因⼦为015平衡因⼦为1。• 场景2h1时新增结点插⼊在f⼦树f⼦树⾼度从h-1变为h并不断更新12-15-10平衡因⼦ 引发旋转其中12的平衡因⼦为1旋转后15和12平衡因⼦为010平衡因⼦为-1。• 场景3h0时a/b/c都是空树b⾃⼰就是⼀个新增结点不断更新15-10平衡因⼦引发旋 转其中12的平衡因⼦为0旋转后10和12和15平衡因⼦均为08.右左双旋代码实现四.AVL树平衡检测我们实现的AVL树是否合格我们通过检查左右⼦树⾼度差的的程序进⾏反向验证同时检查⼀下结点 的平衡因⼦更新是否出现了问题
