本文主要是介绍c++模板类构建AVlL树及AVL树的单双旋转图文简述，以及插入新节点后如何通过旋转使之继续保持平衡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
AVL树 可以将AVL树看作平衡二叉搜索树， 因为原始二叉搜索树极端情况下效率不高，如只有一条单链，此时和链表相当
因此出现了这一古老的树种，AVL树 ：http://baike.baidu.com/link?url=YSwg_fEmV9l07F364_g9B3aBgf2uRaa8fpG8zmXrMCPasdON523B6zJKelC8fddrF9p2QQ-JjYhD2g9l7D-sCDBLzgfJmF6t2nI51M0nJbu
先贴代码，后面有叙述，单旋和双旋。
AVLTree.H(前面的注释相当于我自己的笔记，给自己看的，大家可以忽略):
//a的新平衡破坏了AVL的条件，a是需要重新平衡的结点，不平衡时，a两颗子树高度差为2
//从插入点往上找，第一个不平衡点为a，把a与使a不平衡的那个儿子旋转(单旋转）也许使它不平衡的不是它儿子是它孙子辈但不影响操作，孩子取代父亲做根，父亲做孩子
//因为单旋转为外部，所以，最左和最右不会变。此时，需要改变的结点为（左边情况下）原孩子的右孩子需要链接到a的左边(a此时为孩子了)，a的孩子此时是新的父亲。另一边类似
//不管单双旋转，最左边和最右边的情况不会变
//单旋转 a的左子树的左边 或a的右子树的右边插入
//双旋转 a的左子树的右边，或右子树的左边插入 此时单旋转解决不了问题，因为子树太大还有二叉搜索树的性质 先在a的儿子和孙子间旋转再在a与他的新儿子间旋转 不管下面有多深，我们只关心，a a的儿子 a的孙子
//可以这样区别单双旋转 区分到a的孙子（即使它孙子后面还有节点）就可以截止了 a的左儿子的左右哪个子树，a的右儿子的左右哪个子树
//需要调整的为插入点 到a结点 之间的结点
//双旋转，左右双旋转 理解为 在a左子树的右边插入使avl性质不满足 先把a儿子和孙子左旋转 a儿子传进来，再把a与他的新儿子右旋转（传a） 另一边类似（先右旋，后左旋）
//而单旋转，a左边插入，注意是a的左边，a不一定是插入点的父亲，a右旋转。 另一边类似
//不管单双，都是向插入孩子的另一边旋转， 比如左右双旋， 在a的左边的右边插入，所以a的儿子与孙子先左旋转，接着a与它的新儿子进行一次右旋转！是a右旋转。 所以不管单双的哪种情况都是向插入的相反方向旋转！
//单旋转代码 最后一步，k2 = k1并不是把k2地址改了，只是把k2这个指针保存的地址改了 修改了指针值。 你想啊， 假如k2以前是root或者某个结点的子树，现在那个root不是k2了，不链接到原k2地址，而是把root或者某个结点子树链接到了k1保存的地址！
//左旋右旋说的旋转父亲而不是孩子
//如何区别 单旋转还是 双旋转 即 a左儿子左子树方向 右儿子右子树方向(单)。 右儿子左子树方向，左儿子右子树方向(双)。//单双旋 孩子分配情况：
/*单旋转 以a左子树左边插入为例， a的儿子(左子树)的右子数(如果存在)旋转后成为a的左子树 (因为以前par是a， 之后par是a的左子树， 之前a的左子树是左子树， 旋转后变为 它左子树的右子右子树)
简单点， a左子树左边插入， 左子树的右子树链接到原a的左子树， 原a成为左子树的右子树， 原a的右子树与 a的左子树的左子树不变*/
//双旋转：a的孙子(插入方向上)代替了a的位置， 假设是a的左子树右边插入 左右双旋&#这篇关于c++模板类构建AVlL树及AVL树的单双旋转图文简述，以及插入新节点后如何通过旋转使之继续保持平衡的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
