图文基本根据：《详细图文——AVL树》
也被称作平衡二叉搜索树、AVL树；特点是要么是一棵空树，要么左右两个子树的高度差绝对值不超过1，并且两个子树也都是平衡二叉树。
image.png

平衡因子

左右子树的高度差就是它的平衡因子。AVL树上所有结点的平衡因子只可能是-1，0，1。为了方便计算AVL树里node一般可以加上height这个属性用来表示结点的高度。

添加结点

特意查了节点和结点，二叉树中的node应该是结点。结点表示结合、交合的意思，通常表示的是交叉点。

向AVL树中添加节点很容易导致二叉树失去平衡，所以我们需要在每次插入节点后进行平衡的维护操作。插入节点破坏平衡性有如下四种情况：

LL（右旋）

LL的意思就是向左子树的左孩子中插入新节点后导致不平衡，这种情况需要右旋操作来解决。
image.png
右旋操作的步骤如下图：
image.png
也就是把X的右节点替换为Y，Y的左节点替换为X的右节点，Y作为发生问题的结点被传入以解决，实例代码如下：

  1. //右旋
  2. Node*
  3. rightRotate(Node* y){
  4.     Node* x = y->left;
  5.     y->left = x->right;
  6.     x->right = y;
  7.     //要是结点中有高度的信息，也需要在这里更新一下树的高度
  8. }

RR（左旋）

RR，也就是右子树的右结点插入导致的不平衡。此时就需要左旋来解决此时的不平衡问题
image.png
左旋的操作步骤如下图：image.png
理解了右旋那么左旋也就是左右更改了一下左右而已，算法的本质并没有变化

  1. Node*
  2. rightRotate(Node* y){
  3.     Node* x = y->right;
  4.     y->right = x->left;
  5.     x->left = y;
  6.     //节点中有高度信息的时候也需要更新高度信息
  7. }

LR（先左旋后右旋）

也就是左子结点中又插入了新的右子结点导致的不平衡。
image.pngimage.png
（原po图三这里画错了手动改一下~
LR的思路其实也并不复杂，先针对X结点进行左旋，使得LR变成LL，之后再进行右旋就可以解决问题。复杂度相比上边的LL RR有一些提升

  1. Node*
  2. lrRoatate(Node* y){
  3.     Node* x = y->left;
  4.     Node* z = x->right;
  5.     y->left = z->right;
  6.     x->right = z->left;
  7.     z->left = x;
  8.     z->right  = y;
  9.     return z;
  10. }

RL（先右旋再左旋）

右子结点中插入了左子节点导致的不平衡
image.png
image.png
这里的推演过程可以参考一下总结里写的试试，

总结

记什么LL RR LR RL记性不好我也记不住。总之就是AVL树的不平衡肯定会涉及三个结点，旋转的最后情况都是处于中位数的结点做了根结点。之后的情况自己很容易就可以推演出来，还有就是推演的时候用上上图中的T1234可以方便很多，且不容易出错。还有就是利用上「左子树所有节点都比当前结点小，右子树上结点都比当前结点大」这个特性可以很方便的对比出结点的大小。