AVL平衡二叉树及其4种旋转方式

1.AVL平衡二叉树：二叉树中每个节点的左子树和右子树高度之差的绝对值小于等于1。

2.平衡因子=左子树的高度-右子树的高度。AVL树的平衡因子只有-1,0,1。

3.右旋转 LL

旋转前特征:

1)节点a为不平衡的节点。

2）节点b和节点c为在高度较高的路径上，从a开始的接下来的两个节点。

3）y1,y2,y3和y4代表节点a,节点b,节点c的子节点或者子树。可以为null，可以为叶子结点，也可以为节点数>1的一个二叉树。

4）节点b是节点a的左孩子。节点c是节点b的左孩子。

 

旋转后的特征：

1）节点b变成根节点

2）原来的根节点a变成节点b的右孩子

3）y3变成节点a的左孩子。【如果y3不为空，由于之前y3是节点b的右孩子，现在节点a变成节点b的右孩子。因为b<y3根节点的值<a，节点a变成节点b的右孩子后，节点a并没有左孩子。所以当y3变成节点a的左孩子后，也同样满足b<y3根节点的值<a。】

4）y1,y2,y4和父节点的关系都不发生变化。

 

4.左旋转RR

旋转前特征:

1）节点a为不平衡的节点。

2）节点b和节点c为在高度较高的路径上，从a开始的接下来的两个节点。

3）y1,y2,y3和y4代表节点a,节点b,节点c的子节点或者子树。可以为null，可以为叶子结点，也可以为节点数>1的一个二叉树。

4）节点b是节点a的右孩子。节点c是节点b的右孩子。

旋转后的特征：

1）节点b变成根节点

2）原来的根节点a变成节点b的左孩子

3）y2变成节点a的右孩子。【如果y2不为空，由于之前y2是节点b的左孩子，现在节点a变成节点b的左孩子。因为a<y2根节点的值<b，节点a变成节点b的左孩子后，节点a并没有右孩子。所以当y2变成节点a的右孩子后，也同样满足a<y2根节点的值<b。】

4）y1,y3,y4和父节点的关系都不发生变化。

5.先左旋后右旋LR

旋转前特征:

1)节点a为不平衡的节点。

2）节点b和节点c为在高度较高的路径上，从a开始的接下来的两个节点。

3）y1,y2,y3和y4代表节点a,节点b,节点c的子节点或者子树。可以为null，可以为叶子结点，也可以为节点数>1的一个二叉树。

4）节点b是节点a的左孩子。节点c是节点b的右孩子。

 

step1：左旋操作

step2：右旋操作

将step1的结果进行右旋操作

6.先右旋后左旋RL

旋转前特征:

1)节点a为不平衡的节点。

2）节点b和节点c为在高度较高的路径上，从a开始的接下来的两个节点。

3）y1,y2,y3和y4代表节点a,节点b,节点c的子节点或者子树。可以为null，可以为叶子结点，也可以为节点数>1的一个二叉树。

4）节点b是节点a的右孩子。节点c是节点b的左孩子。

step1：右旋操作

step2：左旋操作