平衡二叉树(AVL)

定义

平衡二叉树是建立在二叉平衡树基础上，目的使得各个节点的深度尽可能小。
平衡二叉树是一颗二叉树，或者为空，或者满足如下两个性质：

1. 左右子树深度之差的绝对值不大于1
2. 左右子树都是平衡二叉树

实现

构造平衡二叉树的过程是动态调整的过程，主要的调整方式有四种，分别为LL型、RR型、LR型、RL型

1. LL型
   LL型转换方式如下图所示

   
   image.png

2. RR型
   RR型转换方式如下图所示

   
   image.png

3. RL型
   RL型转换方式如下图所示

   
   image.png

4. LR型
   LR型转换方式如下图所示

   
   image.png

时间复杂度

平衡二叉树的查找效率为O(lg2 n)