网页浏览看代码效果更佳!!!作者原创,转载请注明出处!!!1.定义

判断二叉树平衡(平衡二叉查找树-AVL树)(1)

AVL树是一种平衡二叉树,它本质上还是一棵二叉排序树,它的特点是:

(1)本身首先是一棵二叉排序树。

(2)带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

2.旋转的定义

AVL旋转是在AVL树插入或删除节点导致平衡条件不满足时进行的操作,失去平衡条件后进行的旋转可以归纳为四种情况:

(1)单向右旋处理LL:

判断二叉树平衡(平衡二叉查找树-AVL树)(2)

(2)先左旋再右旋处理LR:

判断二叉树平衡(平衡二叉查找树-AVL树)(3)

(3)单向左旋处理RR:

判断二叉树平衡(平衡二叉查找树-AVL树)(4)

(4)先右旋再左旋处理RL:

判断二叉树平衡(平衡二叉查找树-AVL树)(5)

3.树节点的定义

只是建议可以如此定义,这样代码中使用起来比较方便

public class Node{ //元素值 private E element; //父节点 private Node parent; //左孩子 private Node leftChild; //右孩子 private Node rightChild; //树的高度 private int height; }

4.插入

插入一个元素可能会影响树的平衡,如果不平衡了,需要进行旋转。

(1)按照二叉排序树的插入方式插入一个元素C,二叉排序树的插入请看数据结构与算法——二叉排序树

(2)更新元素C自身的高度,因为插入的节点肯定是叶子节点,所以高度为0。

(3)向上更新元素C的父节点P的高度。

(4)更新P的过程是:P.height=Math.max(P.leftChild.height,P.rightChild.height),同时判断P.leftChild.height和P.rightChild.height的高度差是否超过1,如果没有超过1,则继续向上递归更新P的父节点直到根节点,如果超过1,则需要进行旋转。

(5)需要旋转的场景有上面4种,需要先判断出属于上面场景中的哪一种。

<1>对于第1种情况,只需要一步右旋转即可完成,图中可以看出,元素5在旋转前后的高度不受影响,而元素10和20的高度变化了,所以我们从元素20开始,重新执行第(4)步。

<2>第3种情况同第1种情况类似,只需要一步左即可完成,元素60在旋转前后的高度不受影响,而元素40和20的高度变化了,所以我们从元素20开始,重新执行第(4)步。

<3>对于第2种情况,需要两步,先左旋转再右旋转,左旋转完成后需要从10依次往上更新掉元素的高度,但是先不要进行高度差的判断,然后进行右旋转完成,从20开始重新执行(4)。

<4>第4种情况与第2种类似,先右旋转完成,从40依次往上更新掉元素高度,先不进行高度差判断,然后左旋转完成,从20开始重新执行(4)。

(6)递归执行上面的逻辑直到根节点也是平衡的。

5.删除

删除一个元素也可能会影响树的平衡,如果不平衡了,需要进行旋转。

(1)按照二叉排序树的删除方式删除一个元素C,二叉排序树的删除请看数据结构与算法——二叉排序树,当然了,对于删除场景中的第3种情况,需要用里面的第二种删除方式,因为第一种删除方式可能导致多个元素的高度变化了。

(2)例如我们删除40,最终可以转化为删除30的情况,30删除完后,25的高度可能变化了,所以需要从25开始执行插入过程中的第(4)步。

(3)递归上面的逻辑直到根节点也是平衡的。

6.查找

查找方式跟二叉排序树完全一样,二叉排序树的查找:#1

7.性能

由于AVL树是平衡的二叉排序树,所以平均查找长度和折半查找的判定树相同,为log2(n)。

,