平衡二叉树的插入问题

参考：

http://www.cnblogs.com/fornever/archive/2011/11/15/2249492.html

文章中，将平衡二叉树的插入问题，归结为四种情形。分别是左左，右右，左右，右左。

这里的意思是：

（1）左左：在一个结点的左孩子的左孩子上插入了一个结点，导致平衡破坏。

a结点有右孩子d，那要进行x和a变换，那么a的右孩子放哪啊？

很简单，如图放在x的左孩子上；分析：x>d,d>a,所以d可作为x的左孩子，且可作为a的右孩子中的孩子。

（2）右右：在一个结点的右孩子的右孩子上插入了一个结点，导致平衡破坏。

（3）左右：在一个结点的左孩子的右孩子上插入了一个结点，导致平衡破坏。

（4）右左：在一个结点的右孩子的左孩子上插入了一个结点，导致平衡破坏。

通过观察得出规律：

左左，右右只需做出一次旋转变换即可重新得出平衡二叉树。

左右，右左，需要做出两次旋转变化才能得到平衡二叉树。左右，一次变化得到左左，然后再变化得到平衡；右左，一次变化得到右右，然后再变化得到平衡。

这样，看网易这道校园招聘题就有思路了：

以下是一颗平衡二叉树，请画出插入键值3以后的这颗平衡二叉树。

变换过程：