简笔随笔，诸多想法，随想随写，如有不当、错误之处，欢迎指正，哈~

笔者在近些课程里，学习了森林界的二叉门，AVL纲的旋转目，各种树种的变化，那可叫一个多姿万千啊！

亦如欲……必先利其器，自然我们先聊聊AVL树，AVL树本质上还是一棵二叉搜索树，它的特点是：

1.本身首先是一棵二叉搜索树。

2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

双旋即在单旋转的基础上，更深一点的操作。

这里提出一个非两次单旋的真正双旋小方案，两次单旋的会聚，却是会让其运算效率变差一些，所以在多数情况下，“真双旋”更为优秀。

这是在输入一组有序数字的过程中，为了使其更为“平衡”，而因生的一种旋转方案。

简单的LL,RR,LR,RL旋转，便可轻易地实现，主要是实现三个重要节点的计算和转动与之带动。

这是单旋部分代码：

static Potation

SingleRotateWithLeft(Position K2)

{

   Potation K1;

   K1 =K2->Left;

   K2->Left=K1->Right;

   K1->Right=K2;

   K2->Height=Max(Height(K2->Left),Height(K2->Right)) +1;

   K1->Height=Max(Height(K1->Left),K2->Height) +1;

   return K1;

}

鉴于笔者目前编程能力较弱，这里仅提供粗糙的伪代码：

AVLNode 双旋平衡(AVLNode 节点,插入键) {

  平衡因子 = 获取平衡因子（节点）;

  if (平衡因子  > 1 && 插入键< 节点值)

    返回右运行（节点）;

  if (平衡因子 < -1 && 插入键 > 节点值)

    返回左运行（节点）;     

  if (平衡因子  > 1 && 插入键 > 节点左值) {

   

     节点左值 = 左循环（节点左值）;

   返回右循环（节点）;

 

  }

  if (平衡因子 < -1 && 插入键 < 节点左值) {

   

    节点右值 = 右循环（节点右值）;

   返回左循环（节点）;

 

  }

      返回节点;

}

我们可以看到，其实只要在一个函数里，将LR,RL循环判断好后执行，即可。

 

参考资料

1.  G. Adelson-Velskii and E.M. Landis, "An algorithm for the organization of information." Doklady Akademii Nauk SSSR, 146:263–266, 1962（Russian）. English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962.

2.  严蔚敏, 吴伟民. 数据结构: C 语言版[M]. 清华大学出版社有限公司, 2002.

     3. 百度百科

https://baike.baidu.com/item/AVL%E6%A0%91/10986648?fr=aladdin