二叉平衡树(AVL树)

AVL树插入元素结论

单旋转:

双旋转:

如果看到后面会发现,我下面举得列子,类型一和类型三和我结论里面的有点不一样,那是因为类型一的节点4和类型三的节点14无论以何种方式都能达到平衡状态,为了减少我们的代码分类次数,于是可以归到旋转两次里面

二叉平衡树的定义

（1）左右子树深度之差的绝对值不超过1;

（2）左右子树仍然为平衡二叉树.

推导过程

添加元素:

​ 链表,添加元素就有两种方法,第一是往尾部直接添加元素,第二是往中间某个节点添加,而第二种方法添加需要遍历到相应的位置才可以添加,时间复杂度O(n)

​ 于是我思考,平衡树其实也是链表,也可以往中间添加元素,但是这样岂不是得不偿失,顾此失彼了,反而让平衡树添加变得更加慢了,因为不但要调整该节点的位置,还要旋转树,考虑的更多了,于是便有了直接添加到尾部,不满足再旋转,简单粗暴

什么时候旋转?怎么旋转?

​ 平衡树如果左子树和右子树高度一致,那么无论怎么添加都是平衡的,只有左右子树差一的情况才需要改变树

​ 于是有了以下2种情况,每种又分为两类,一种四类

情况一左子树高于右子树:

• 类型一:左子树高于右子树,添加到左子树最外面,也就是添加到3的左或者右,情况都是一样的,

右旋(就是右子树长高):到到下面的效果,树平衡了我们把叫做右旋,只需要旋转一次,往后面想是不是右子树的最外面也是一样的呢?我们可以试一试,后面解答

把节点5当做根节点,旋转后因为根节点是5了,7必须要到右边去,于是把7放到9的左边,后面所有的都差不多,如果连这个都看不懂,建议先看看二叉查找树,自己好好想想,后面不再解释

• 类型二:里层添加元素,无论是添加节点8还是节点10,都是一样对待

第一步依然找最外层的节点7,左旋

第二步:原始最外层节点7的右孩子(节点9)右旋

于是平衡了

​

情况二右子树高于左子树:

• 类型三:右子树的最外层添加,无论是节点15的左叶子还是右叶子,最外层的是节点15

左旋(左子树长高):发现依然是一次旋转,我们的树便平衡了,我们叫做左旋

又再次平衡了

• 类型四:里层添加元素,依然是无论在节点11的左叶子还是右叶子添加都一样
  

我们试着右旋转一次:于是得到下面这个样子,还是不平衡,怎么办呢?(再次说明,添加节点10或者节点12,我只是懒,不想拆开再画了,效果一样,不要纠结,就害怕看错了)

第一步依然是找到最外层的节点13,右旋,发现依然不平衡

第二步,原始树最外层节点13的左孩子(节点11),左旋

于是平衡了

复杂例子训练

上面的例子都是过于简单的,于是我们添加一个比较复杂的列子来再次试验,随便添加一个节点(红色表示)

这次我没有标注大小,相信也能识别出来,特别注意我标注的根节点(绿色,如果不是绿色,代表…什么你知道吧),紫色的右子树节点,红色的添加节点和黄色的一般节点,之前我一直强调最外层节点和他的孩子,现在就能看到效果了

根据我们的结论右旋一次:

然后再左旋一次

达到平衡,发现什么规律了吗?

=分隔线===

没关系我们换个节点再来一次,再换叶子添加

再来旋转,一样先右旋

再左旋:

我相信你已经发现什么了

添加元素的时候,如果高度超过了平衡树的规则就会旋转,先找到添加节点的最外层节点和最外层节点的子节点,然后旋转两次就可以达到平衡,赶快练习下吧

多思考多练习,思考下删除操作又该如何实现呢?转载请标明出处谢谢