AVL树单选转和双旋转

看了好几天树了，也算有点心得。学树，必须要图。这里有两篇里的博客，在结合书，我用的是《数据结构与算法分析C++版》就可以了。

http://blog.csdn.net/a454042522/article/details/8591421

http://blog.csdn.net/vesper305/article/details/13614403

在AVL树中必须平衡的点叫做α,

四种情况：

1.在α左孩子的左子树上插入一个节点，造成不平衡。

2.在α左孩子的右子树上插入一个节点，造成不平衡。书上称为左-右旋转

3.在α右孩子的右子树上插入一个节点，造成不平衡。

4.在α右孩子的左子树上插入一个节点，造成不平衡。书上称为右-左旋转

那么1与3是同一种类型，是对称的，属于单选转。

2与4是同一种类型，是对称的，属于双旋转。

之所以有双旋转，是因为在在α右孩子的左子树上插入一个节点这种情况（右-左旋转），单选转一次是解决不了问题的。（如下图，图复制于第一个博客链接中）

1、首先平衡点是A，A就是α，B是A的右孩子，C是右孩子的左子树。当对C插入后，A不平衡了，条件为A的左子树和右子树之间高度差为2。在图里也就是AL和B之间

高度差为2。

2、左选转一次，是对C与B做左旋转。可以发现A依旧没有平衡。

3、右旋转一次，对C和A做右旋转，以C为新节点树平衡。

谨记：

1、单选转涉及到两个节点，而双旋转涉及到三个节点。这在理解代码方面有用

2、注意每次旋转，节点的子树变化。在双旋转中，因为C要变成根，它的两个子树都要甩给别人，它的左右子树肯定都大于A，但是注意了由于旋转的过程，C的右子树比B小，就甩给B作左子树；C的左子树再甩给A作右子树。

3、双旋转就是先对平衡节点的孙子和儿子出手，在对变成的新儿子的孙子和自己出手。

4、在实际的代码中，传入函数的都是平衡点地址，结束时把新节点的地址赋予就旧平衡点。（我用的是C++）

5、理解这个&*的含义。（我用的是C++），如果单纯传入指针，对树是没有变化的，因为指针进来也只是复制一个指针的副本进行操作。

6、自己首先要能拿手画出来每一步的变化。理解代码时也可以徒手写出每一步的变化。