@H_404_0@平衡二叉树的插入问题

@H_404_0@参考：

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

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

@H_404_0@这里的意思是：

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

@H_404_0@

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

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

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

@H_404_0@

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

@H_404_0@

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

@H_404_0@通过观察得出规律：

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

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

@H_404_0@

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

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

@H_404_0@

@H_404_0@

@H_404_0@变换过程：