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

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

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

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

2.旋转的定义

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

(1)单向右旋处理LL：

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

(3)单向左旋处理RR：

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

3.树节点的定义

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

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

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

(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)。