平衡二叉樹【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、删除