。

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

因此两位俄罗斯的数学家G.M.Adelson

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

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

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

如果它有n个结点其高度可保持在

O(log_2

因为插入逻辑比较复杂我在这里就写一个大致思路具体代码我上传到了git上。

AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。

那么AVL树的插入过程可以分为两步

bool

新节点插入后AVL树的平衡性可能会遭到破坏此时就需要更新平衡因子//

并检测是否破坏了AVL树的平衡性/*cur插入后parent的平衡因子一定需要调整在插入之前parent的平衡因子分为三种情况-10,

如果cur插入到parent的左侧只需给parent的平衡因子-1即可2.

如果cur插入到pParent的右侧只需给parent的平衡因子1即可此时parent的平衡因子可能有三种情况0正负1

正负21.

如果parent的平衡因子为0说明插入之前pParent的平衡因子为正负1插入后被调整成0此时满足AVL树的性质插入成功2.

如果parent的平衡因子为正负1说明插入前parent的平衡因子一定为0插入后被更新成正负1此时以pParent为根的树的高度增加需要继续向上更新3.

如果parent的平衡因子为正负2则parent的平衡因子违反平衡树的性质需要对其进行旋转处理*/while

(parent){//

parent-_pLeft)parent-_bf--;elseparent-_bf;//

pParent-_bf

双亲的平衡因子为正负2违反了AVL树的平衡性需要对以parent//

pParent-_bf){//

0p所在的高度不会改变不会影响爷爷节点。

说明更新前p-_bf是1或者-1p的矮的那一边插入了新节点左右高度均衡了p的高度不变不会影响爷爷更新结束。

更新后p-_bf

-1p所在的子树高度变了会影响爷爷。

说明更新前p-_bf是0p的有一边插入p变得不均衡但不违反规则p的高度变了会影响爷爷继续往上更新

更新后p-_bf

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

根据节点插入位置的不同AVL树的旋转分为四种

/*上图在插入前AVL树是平衡的新节点插入到30的左子树(注意此处不是左孩子)中30左子树增加了一层导致以60为根的二叉树不平衡要让60平衡只能将60左子树的高度减少一层右子树增加一层即将左子树往上提这样60转下来因为60比30大只能将其放在30的右子树而如果30有右子树右子树根的值一定大于30小于60只能将其放在60的左子树旋转完成后更新节点的平衡因子即可。

在旋转过程中有以下几种情况需要考虑1.

60可能是根节点也可能是子树如果是根节点旋转完成后要更新根节点如果是子树可能是某个节点的左子树也可能是右子树大家在此处可举一些详细的例子进行画图考虑各种情况加深旋转的理解

void

旋转完成之后30的右孩子作为双亲的左孩子parents-_left

SubLR;//

因为60可能是棵子树因此在更新其双亲前必须先保存60的双亲Node*

ppnode

parents-_parent;parents-_parent

SubR;SubR-_parent

将双旋变成单旋后再旋转即先对30进行左单旋然后再对90进行右单旋旋转完成后再考虑平衡因子的更新。

旋转之前先看60的平衡因子是多少旋转结束以后根据60的平衡因子更新结果。

从这三张图中可以发现不管旋转之前60的平衡因子是多少最后都会变成0在单旋中已经将它置0所以我们只用观察3090

的平衡因子。

而不管这棵树怎么变它必定会遵守搜索二叉树的规则所以在这里我只是用了一个示例向大家展示这三种情况。

不管这棵树的形状是什么样的只要它满足搜索二叉树的规则那么左右双旋只会有这几种情况。

旋转之前60的平衡因子可能是-1/0/1旋转完成之后根据情况对其他节点的平衡因子进行调整

void

旋转之前保存pSubLR的平衡因子旋转完成之后需要根据该平衡因子来调整其他节点的平衡因子int

SubLR-_bf;//

这里与左右双旋相似将双旋变成单旋后再旋转即先对90进行右单旋然后再对30进行左单旋旋转完成后再考虑平衡因子的更新。

旋转之前先看60的平衡因子是多少旋转结束以后根据60的平衡因子更新结果。

void

SubRL-_bf;RotateR(SubR);RotateL(parents);//

Renewal

假如以parent为根的子树不平衡即parent的平衡因子为2或者-2分以下情况考虑

parent的平衡因子为2说明parent的右子树高设parent的右子树的根为SubR

当SubR的平衡因子为-1时执行右左双旋parent的平衡因子为-2说明parent的左子树高设parent的左子树的根为SubL

旋转完成后原parent为根的子树个高度降低已经平衡不需要再向上更新。

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

验证其为二叉搜索树

如果中序遍历可得到一个有序的序列就说明为二叉搜索树验证其为平衡树

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

bool

为了提高效率,可以走后序来计算每个节点的左子树和右子树的高度差为多少

bool

如果root的左子树或者右子树不平衡,就直接返回falsereturn

false;}//

判断每个节点的右子树的最大高度与左子树的最大高度的差值是否等于该节点的平衡因子else

(rightHight

}这段代码是随机生成10000个数插入到我自己写的一棵AVL树中插完这10000个树以后我对这棵树进行了一下判断是否平衡结果是平衡的证明我的插入逻辑是没有问题的我测试了不止这一组数据。

因为插入删除比较复杂我在这里就写一个大致思路具体代码我上传到了git上。

因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不

过与插入不同的是删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。

删除节点会影响删除节点的部分祖先如果是删除根节点也会找一个可以替代的节点交换值再删除具体可以参考搜索二叉树的删除部分。

更新原则

-1p所在的子树高度不变不会影响爷爷。

说明更新前p-_bf是0p的两边是均衡的p的有一边删除了p变得不均衡但不违反规则p的高度不变不会影响爷爷更新结束。

更新后p-_bf

-1p的有一边删除了p的左右变得均衡p的高度变了会影响爷爷继续往上更新。

更新后p-_bf

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

log_2(N)

log2​(N)。

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

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

源码地址https://gitee.com/ASL498/data-structure/tree/master/AVLTree