平衡二叉树【AVL树】——插入、删除

1、平均查找长度（树高）:

 

2、结点的平衡因子=左子树高-右子树高

平衡二叉树结点的平衡因子只可能是0,1或-1

 

2、插入

        2.1  每次调整的对象都是“最小不平衡子树”

 

        2.2  调整最小不平衡子树A

                ①LL【A的左孩子右上旋】：在A的左孩子的左子树中插入导致不平衡

                ②RR【A的右孩子左上旋】：在A的右孩子的右子树中插入导致不平衡

 

 

                ③LR【A的左孩子的右孩子先左上旋再右上旋】：

                                在A的左孩子的右子树中插入导致不平衡

 

                ④RL【A的右孩子的左孩子先右上旋再左上旋】：

                                在A的右孩子的左子树中插入导致不平衡

【注】每次旋转都会导致这个孩子变成爹，爹变成孩子

【注】只有左孩子才能右上旋

           只有右孩子才能左上旋

 

 

 

3、删除