如何将数据库导入网站,凡诺网站建设,wordpress建视频网站可以吗,安徽省住房和城乡建设厅网站域名文章目录 初知C#xff1a;AVL树1.AVL树的概念2.AVL树的是实现2.1.AVL树的结构2.2.AVL树的插入2.3.旋转2.4.AVL树的查找2.5.AVL树平衡检测 初知C#xff1a;AVL树
1.AVL树的概念
• AVL树是最先发明的自平衡⼆叉查找树#xff0c;AVL是⼀颗空树#xff0c;或者具备下列性… 文章目录 初知CAVL树1.AVL树的概念2.AVL树的是实现2.1.AVL树的结构2.2.AVL树的插入2.3.旋转2.4.AVL树的查找2.5.AVL树平衡检测 初知CAVL树
1.AVL树的概念
• AVL树是最先发明的自平衡⼆叉查找树AVL是⼀颗空树或者具备下列性质的⼆叉搜索树它的左右子树都是AV树且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索⼆叉树通过控制⾼度差去控制平衡。
• AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家他们在1962年的论⽂《Analgorithmfortheorganizationofinformation》中发表了它。
• AVL树实现这⾥我们引⼊⼀个平衡因⼦(balancefactor)的概念每个结点都有⼀个平衡因⼦任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度也就是说任何结点的平衡因⼦等于0/1/-1AVL树并不是必须要平衡因⼦但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡就像⼀个⻛向标⼀样。
• 思考⼀下为什么AVL树是⾼度平衡搜索⼆叉树要求⾼度差不超过1⽽不是⾼度差是0呢0不是更好的平衡吗画画图分析我们发现不是不想这样设计⽽是有些情况是做不到⾼度差是0的。⽐如⼀棵树是2个结点4个结点等情况下⾼度差最好就是1⽆法作为⾼度差是0 。
• AVL树整体结点数量和分布和完全⼆叉树类似⾼度可以控制在 logN那么增删查改的效率也可以控制在O(logN)相⽐⼆叉搜索树有了本质的提升。
2.AVL树的是实现
2.1.AVL树的结构
在下图我们可以看到_parent指针后续更新平衡因子有很大的作用。
2.2.AVL树的插入
2.2.1 AVL树插⼊⼀个值的⼤概过程 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。 新增结点以后只会影响祖先结点的⾼度也就是可能会影响部分祖先结点的平衡因⼦所以更新 从新增结点-根结点路径上的平衡因⼦实际中最坏情况下要更新到根有些情况更新到中间就可 以停⽌了具体情况我们下⾯再详细分析。 更新平衡因⼦过程中没有出现问题则插⼊结束 更新平衡因⼦过程中出现不平衡对不平衡⼦树旋转旋转后本质调平衡的同时本质降低了⼦树 的⾼度不会再影响上⼀层所以插⼊结束。
2.2.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会影响arent的⽗亲结点的平衡因⼦所以要继续向上 更新。 • 更新后parent的平衡因⼦等于2或-2更新前更新中parent的平衡因⼦变化为1-2或者-1--2说 明更新前parent⼦树⼀边⾼⼀边低新增的插⼊结点在⾼的那边parent所在的⼦树⾼的那边更⾼ 了破坏了平衡parent所在的⼦树不符合平衡要求需要旋转处理旋转的⽬标有两个1、把 parent⼦树旋转平衡。2、降低parent⼦树的⾼度恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新插⼊结束。
更新到10结点平衡因⼦为210所在的⼦树已经不平衡需要旋转处理 更新到中间结点3为根的⼦树⾼度不变不会影响上⼀层更新结束 最坏更新到根停⽌ 2.2.3插⼊结点及更新平衡因⼦的代码实现
2.3.旋转
2.3.1 旋转的原则
保持搜索树的规则让旋转的树从不满⾜变平衡其次降低旋转树的⾼度 旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。 说明下⾯的图中有些结点我们给的是具体值如10和5等结点这⾥是为了⽅便讲解实际中是什 么值都可以只要⼤⼩关系符合搜索树的规则即可。
2.3.2 右单旋 • 本图1展⽰的是10为根的树有a/b/c抽象为三棵⾼度为h的⼦树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树 是⼀种概括抽象表⽰他代表了所有右单旋的场景实际右单旋形态有很多种具体图2/图3/图4/ 图5进⾏了详细描述。 • 在a⼦树中插⼊⼀个新结点导致a⼦树的⾼度从h变成h1不断向上更新平衡因⼦导致10的平 衡因⼦从-1变成-210为根的树左右⾼度差超过1违反平衡规则。10为根的树左边太⾼了需要 往右边旋转控制两棵树的平衡。 • 旋转核⼼步骤因为5b⼦树的值10将b变成10的左⼦树10变成5的右⼦树5变成这棵树新 的根符合搜索树的规则控制了平衡同时这棵的⾼度恢复到了插⼊之前的h2符合旋转原 则。如果插⼊之前10整棵树的⼀个局部⼦树旋转后不会再影响上⼀层插⼊结束了。
下面五张图分别为右旋的各种情况请仔细观看有利于理解哦 图1 图2 图3 图4 图5
2.3.3 右单旋代码实现 这里传过去的parent是平衡因子为2或者-2的节点 2.3.4左单旋 •本图6展⽰的是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整棵树的⼀个局部⼦树旋转后不会再影响上⼀层插⼊结束了。 2.3.5左单旋代码实现
2.3.6左右双旋 通过图7和图8可以看到左边⾼时如果插⼊位置不是在a⼦树⽽是插⼊在b⼦树b⼦树⾼度从h变成h1引发旋转右单旋⽆法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯粹的左边⾼但是插⼊在b⼦树中10为跟的⼦树不再是单纯的左边⾼对于10是左边⾼但是对于5是右边⾼需要⽤两次旋转才能解决以5为旋转点进⾏⼀个左单旋以10为旋转点进⾏⼀个右单旋这棵树这棵树就平衡了。 图7 图8 • 图7和图8分别为左右双旋中h0和h1具体场景分析下⾯我们将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平衡因⼦均为0。
2.3.7 左右双旋代码实现 2.3.8右左双旋 •跟左右双旋类似下⾯我们将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平衡因⼦均为0。 2.3.9右左双旋代码实现
2.4.AVL树的查找 2.5.AVL树平衡检测
我们实现的AVL树是否合格我们通过检查左右⼦树⾼度差的的程序进⾏反向验证同时检查⼀下结点的平衡因⼦更新是否出现了问题。空树也是AVL树哦
