平衡二叉树

平衡二叉树定义（AVL）:它或者是一棵空树，或者具有以下性质的二叉树：它的左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是一棵平衡二叉树。
很显然，平衡二叉树是在二叉排序树（BST）上引入的，就是为了解决二叉排序树的不平衡导致时间复杂度大大下降，那么AVL就保持住了（BST）的最好时间复杂度O(logn)，所以每次的插入和删除都要确保二叉树的平衡。

AVL树的旋转规律

• LL型
  平衡二叉树某一节点的左孩子的左子树上插入一个新的节点，使得该节点不再平衡。这时只需要把树向右旋转一次即可，如图所示，原A的左孩子B变成父节点，A变成其右孩子，而原B的右子树变成A的左子树，注意旋转之后BRh是A的左子树

  
  image.png

• RR型
  平衡而啥树某一节点的右孩子的右子树上插入一个新的节点，使得该节点不再平衡。这是只需要把树向左旋转一次即可，如图所示，原A右孩子B变成父节点，A变成其左孩子，而原B的左子树Blh将变成A 的右子树

  
  B11F155F-8772-40A5-ACF4-D788D1BC9335.png

• LR型
  平衡二叉树某一节点的左孩子的右子树上插入一个新的节点，使得该节点不再平衡。这时需要旋转两次，仅一次的旋转是不能够使二叉树再次平衡。如图所示，在B节点按照RR型向左旋转一次之后，二叉树在A节点仍然不能保持平衡，这时还需要再向右旋转一次。

  
  540F13E3-3F50-4A3C-984D-17227A332EB2.png

• RL型
  平衡二叉树某一节点的右孩子的左子树上插入一个新的节点，使得该节点不再平衡。同样，这时需要旋转两次，旋转方向刚好同LR型相反。

  
  26D8E037-9EFE-4C2B-82D5-6F93E41CD62D.png