左单旋3.2

右左双旋四.AVL树完整代码AVLTree.hTest.c五.

前面对map/multimap/set/multiset进行了简单的介绍在其文档介绍中发现这几个容器有个共同点是其底层都是按照二叉搜索树来实现的但是二叉搜索树有其自身的缺陷假如往树中插入的元素有序或者接近有序二叉搜索树就会退化成单支树时间复杂度会退化成O(N)因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树来实现。

二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。

因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。

一棵AVL树或者是空树或者是具有以下性质的二叉搜索树(可以调整是因为相同数据的二叉搜索树不止一种形状)

它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

平衡因子

如果一棵二叉搜索树是高度平衡的它就是AVL树。

如果它有n个结点其高度可保持在O(log2n)O(log_2

2.1

对于AVL树相比普通的二叉搜索树最主要的就是多了一个平衡因子保持AVL高度平衡的结构。

而为了能够更加便捷的操作平衡因子除了左右节点的指针还要新增一个父亲节点指针即三叉链的结构因为左右子树的增加节点就会导致父亲节点平衡因子的变化

templateclass

kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}

};2.2

kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}

};templateclass

对于AVL树的插入来说本质上还是二叉搜索树因此大致的插入逻辑还是像普通的搜索树一样即比根小向左遍历比根大向右遍历如果遇到相同节点就插入失败返回false如果没遇到遇到空的地方就直接插入。

但与普通二叉搜索树不同的是我们在插入节点的过程中要时时刻刻注意AVL树的结构即通过我们新增的成员平衡因子_bf而为了便于访问这个平衡因子相比较普通的搜索树也就增加了指向父亲节点的指针即三叉链的结构。

但需要注意的是如果插入了新节点这样不仅会导致父亲节点平衡因子的变化同样也有可能父亲的父亲节点也会跟着变化下面试着举2个例子

对于这种情况来说新增了一个cur节点恰好能够使parent的平衡因子变成0我们知道平衡因子右子树的高度-左子树的高度我们可以看出parent的值从-1或者1变成0整颗树没有任何一个子树的高度发生了变化因此插入一个节点不影响任何子树的高度即parent的平衡因子变成0就不需要继续向上遍历检索上面父亲节点的平衡因子了。

新增插入节点时都必须去检索。

对于这种情况向上遍历的平衡因子并且根据变化的结构去修改平衡因子如果平衡因子变成了不属于[-1,

1]的范围那就说明这颗子树的结构出现了问题此时就需要将这颗子树进行旋转使其结构满足所有平衡因子都属于[-1,

第一步寻找插入点

此步骤与普通的二叉搜索树的规则几乎相同唯一区别是由于多了一个parent指针parent初始化为nullptr因此在搜索的时候parent也需要不断变化。

第二步更新平衡因子

parent的平衡因子会随着插入节点而发生变化parent一旦变化那parent的parent也会发生变化因此需要一个循环使平衡因子顺着自己的parent指针不断遍历并且判断是否需要更改。

平衡因子如果变成0说明之前的parent-_bf是1或-1说明之前parent一边高一边低这次插入填上矮的那边parent所在子树高度不变不需要继续往上更新可以跳出循环。

平衡因子如果变成1或者-1说明插入之前parent-_bf

0两遍一样高现在插入后一边更高了parent所在子树高度变了需要继续往上更新平衡因子如果变成

2或者-2说明之前parent-_bf是1或-1现在插入后严重不平衡违反了左右高度差不超过1的规则就需要就地处理即旋转这颗子树旋转需要注意

让这颗子树旋转之后的高度差不超过1。

旋转过程中需要保持仍是搜索树。

更新调整孩子节点的平衡因子。

让这颗子树的高度和插入前保持一致。

Insert代码

(parent){//新增在右parent-_bf//新增在左parent-_bf--if

(cur

parent-_left){parent-_bf--;}else{parent-_bf;}//判断平衡因子的范围if

(parent-_bf

-2){//需要旋转这个子树代码和情况过多在三.AVL树的旋转中展示}else{assert(false);}}return

true;}看完这部分代码直接看下一个一级标题AVL树的旋转。

看完旋转之后再回来按照顺序依次看。

2.4

AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步

验证其为二叉搜索树

每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确

代码如下

root-_bf)//这一步可以进一步验证平衡因子是否准确不写也无所谓{cout

root-_kv.first

因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不错与删除不同的时删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。

可以想象成插入的反向思考具体实现可参考《算法导论》或《数据结构-用面向对象方法与C描述》殷人昆版。

在2.3的插入中我们说到了一旦平衡因子超出了指定的范围就会导致子树左右高度差发生变化导致结构不再是高度平衡的状态此时这个子树就需要旋转旋转到没插入前的高度。

对于旋转有很多种情况因此我把他单独拿出来作为一个大标题的形式来描述。

先不进行分类随便举个例子看看

让这颗子树旋转之后的高度差不超过1。

旋转过程中需要保持仍是搜索树。

更新调整孩子节点的平衡因子。

让这颗子树的高度和插入前保持一致。

但实际上我们的AVL树可能会非常的复杂因此并不像上面的例子那么简单。

因此如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。

根据节点插入位置的不同AVL树的旋转根据不同的插入情况分为四种左单旋、右单旋、先左单旋再右单旋、先右单旋再左单旋。

上面的例子就属于左单旋。

3.1

对于此图实际上是一个抽象图即a,b,c的高度都不是一个确切的数字。

但从图中我们可以看出在c插入节点导致高度变化为h1这个时候30的平衡因子就变成了2。

那为什么会左旋从抽象的角度来看对于高度平衡的AVL树右边过高我们就需要考虑不让右面高从绳子的角度来说右边过长那就将中间节点再往右移动对于这个模型也一样我们考虑根节点往右移动即将60作为根节点此时左子树就会往下可以看出这是一个将左子树往下压的过程通过这种角度的思考就不难对这种树进行旋转。

既然有了抽象的左旋从学习的角度同样要将这种AVL树的旋转具象化

如果h0那情况就正如我们一开始随便举的例子一样如果是根节点的1平衡因子不符合条件那就将右孩子通过旋转变成根节点右孩子的左孩子给到原来根节点的右孩子节点这样就完成了旋转同时满足了条件。

如果h1唯一与上面的情况不同的是平衡因子首先不满足条件的节点可能不会是根节点因此这种情况我们只需将这个不满足条件的节点作为需要旋转的子树的根就和上面的步骤一样。

最后这个子树的新根的parent指针再连接回去。

需要注意的细节问题是节点的parent指针。

如果h2那么情况就会变的很复杂因此上述抽象的结构我们提前将c确定形状在这我们具体实例化一下

b来说都有三种的选择因此当h2时插入之前的组合情况就会有3*39种的结果在这种情况之下在c的任何一个子树下插入都会引发30这个节点的旋转而c的孩子节点有四个位置可以插入那一共就是9*436种情况。

h继续增加只会更多因此也没必要将这么多种情况都画出来因为这些情况都属于上面抽象图的衍生都可以调用左旋转。

(parent-_bf

(subRL)//subRL不为空则需要连接到parent{subRL-_parent

parent;}subR-_left

parent-_parent;//记录保存parent-_parent

subR;if

nullptr;}else//如果是局部子树{//判断ppNode之前是左连接还是右连接if

(ppNode-_left

ppNode;}//最后更新平衡因子:一定都为0parent-_bf

subR-_bf

}和左单旋的思想是一样的只不过是将赋值的左右反过来。

这里就直接上代码了

void

这种折线似的结构似乎更加常见但如果仍用山上面的左旋或者右旋只会让其左右转一下并不能减少其任意子树的高度。

这样就无法用到上面任何一个单旋了因此下面还有两种旋转处理的情况。

3.3

就如上面的抽象图我们仍然需要对其有所见解才能进一步分析并写出代码通过观察发现对具象的三个节点原本是折线通过左旋变成直线后发现就可以通过右旋从而实现AVL树的结构了。

当然这么说还是过于敷衍下面将h具象化看看例子

如果h0则h-1的部分为-1但我们可以同样的认为他是不存在节点的如果h1和上面的情况几乎相似同3.1左单旋叙述的一样只是子树部分旋转需要注意parent指针这种情况是最普遍的。

如果h2情况就如左单旋的h2的情况一样有非常多的情况出现因此这里只需明白抽象的具体树的旋转规则就可以了。

(parent-_bf

对于左右双旋上面的步骤不难看出先左旋parent的左孩子之后再右单旋旋转parent复用前面的左单旋和右单旋的代码即可。

但是关键还要修改旋转节点对应的平衡因子由于左单旋和右单旋改变了原有的平衡因子因此我们需要在左右单旋之前将需要改变的节点及对应的平衡因子的值给保留起来保留的目的是需要根据原有的平衡因子的值将旋转后对应的值进行改变。

如果插入后subLR-_bf

-1即subLR的左子树插入上图就是这样旋转后的parent-_bf

1subL-_bf

subLR-_bf;RotateL(parent-_left);//左节点左旋RotateR(parent);//右旋//改变平衡因子if

(bf

subRL-_bf;RotateR(parent-_right);//右节点右旋RotateL(parent);//左旋//改变平衡因子if

(bf

(parent){//新增在右parent-_bf//新增在左parent-_bf--if

(cur

parent-_left){parent-_bf--;}else{parent-_bf;}//判断平衡因子的范围if

(parent-_bf

-1){RotateRL(parent);}else{cout

parent-_kv.first

endl;assert(false);}break;}else{assert(false);}}return

true;}void

(subRL)//subRL不为空则需要连接到parent{subRL-_parent

parent;}Node*

parent-_parent;//记录保存subR-_left

subR;if

nullptr;}else//如果是局部子树{//判断ppNode之前是左连接还是右连接if

(ppNode-_left

ppNode;}//最后更新平衡因子:一定都为0parent-_bf

subR-_bf

subLR-_bf;RotateL(parent-_left);//左节点左旋RotateR(parent);//右旋//改变平衡因子if

(bf

subRL-_bf;RotateR(parent-_right);//右节点右旋RotateL(parent);//左旋//改变平衡因子if

(bf

IsBalance(root-_right);}private:void

_Inorder(Node*

nullptr){return;}_Inorder(root-_left);cout

root-_kv.first

endl;_Inorder(root-_right);}Node*

_root

AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即log2(N)log_2

(N)log2​(N)。

但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。

因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。