1、AVL树

AVL树首先是一颗二叉搜索树，满足其所有性质，AVL树又叫做高度平衡的二叉搜索树;

AVL: 动态搜索树;

平衡因子bf: 右树高度 — 左树高度; bf的取值只能是1, 0, -1;

左右子树都得符合平衡因子, 若不符, 的通过旋转来调整平衡因子;

2、四种旋转

(1)、单旋转---->直线型

(2)、双旋转----->折线型

要进行两次旋转的调整，判断折线，看哪边突出(就是三个结点中有一个突出的方向)，就先向哪边旋转；

四种旋转，每次就只针对两个结点(要进行旋转的2个结点)；然后将上面的分支挂到旋转后的L/R上即可。

3、画平衡树

根据一组数字，画出其AVL树：16 3 7 11 9 26 18 14 15

画AVL树，首先其实是一颗搜索二叉树; 按照其比左孩子大，比右孩子小画就行; 有了平衡因子，不满足时在旋转调整即可。

画法如下：





4、四种旋转的实现

永远只考虑三层以内结点的旋转；

C++实现其所有代码：

(1)、右单旋

代码如下(代码中ptr代表的是要bf不为平衡处，指向要进行旋转的结点)：

voidRotateR(AVLNode<Type>*&ptr){AVLNode<Type>*subR=ptr;ptr=ptr->leftChild;//通过引用直接修改指向1的指针(可能是上一个的左孩子/右孩子)subR->leftChild=ptr->rightChild;ptr->rightChild=subR;ptr->bf=subR->bf=0;}

(2)、左单旋

左单旋与右单旋的代码是镜像的，并且想法是一致的; 所以代码如下：

voidRotateL(AVLNode<Type>*&ptr){AVLNode<Type>*subL=ptr;ptr=subL->rightChild;//同样是经过引用修改subL->rightChild=ptr->leftChild;ptr->leftChild=subL;subL->bf=ptr->bf=0;}

在进行单旋转时，因为是在插入，其自身的bf不用调整，初始化为0;修改的是根和另一个结点的bf;

(3)、先左后右单旋

在进行双旋转时，首先明确左/右孩子，根结点的最终情况, 在进行调整;并且在双旋转时每个结点的bf都得改变；

平衡因子在这不好考虑，有点复杂，具体分析如下：

平衡因子的考虑关键在：ptr有左树/右树，对应上去则subL/sunR原先必有一个分支结点; ptr没有孩子结点，对应subR/subL原先也没有分支结点；



代码如下：

voidRotateLR(AVLNode<Type>*&ptr){AVLNode<Type>*subR=ptr;//最终右孩子AVLNode<Type>*subL=ptr->leftChild;//最终左孩子ptr=subL->rightChild;//最终根节点,因为引用,最终这个修改了指向根结点，完成了连接;subL->rightChild=ptr->leftChild;ptr->leftChild=subL;if(ptr->bf<=0){subL->bf=0;//此时的情况就是,自己ptr原先没有挂结点或者是左树挂上结点，而满足这种情况下，sunL原先必有左树，此时在挂上右树，所以为0;}else{subL->bf=-1;//此时的情况是ptr有右孩子，而sunL有左孩子，满足这种情况，所以bf只能是-1;}subR->leftChild=ptr->rightChild;ptr->rightChild=subR;if(ptr->bf==-1){//当结点ptr其只有左孩子时，subR->bf=1;//sunR必定有右孩子,所以此时为1}else{subR->bf=0;//当ptr没有孩子结点或有一个右孩子时(此时subR必有右树)，所以此时为0;}ptr->bf=0;//调整后根的bf永远是0;}

(4)、先右后左单旋

与上一个双旋的代码是镜像的, 并且想法是一致的; 平衡因子的修改有点不一样，注意一下就行， 所以代码如下:

voidRotateRL(AVLNode<Type>*&ptr){AVLNode<Type>*subL=ptr;AVLNode<Type>*subR=ptr->rightChild;ptr=subR->leftChild;subR->leftChild=ptr->rightChild;ptr->rightChild=subR;if(ptr->bf>=0){subR->bf=0;}else{subR->bf=1;}subL->rightChild=ptr->leftChild;ptr->leftChild=subL;if(ptr->bf==1){subL->bf=-1;}else{subL->bf=0;}ptr->bf=0;}