数据结构（八）平衡二叉树

太过爱你忘了你带给我的痛 2022-04-22 04:30 229阅读 0赞

### 文章目录 ###

*   *  平衡二叉树
     *   *  0. 为何要使用AVL树？
         *  1. 定义
         *  2. 平衡二叉树的调整
         *   *  0. 遵循原则
             *  1. RR 单旋
             *  2. LL 单旋
             *  3. LR 双旋
             *  4. RL 双旋
         *  练手题

## 平衡二叉树 ##

### 0. 为何要使用AVL树？ ###

二叉搜索树的搜索效率与其树的深度相关，而二叉搜索树的组成又与其插入序列相关，在极端情况下，二叉搜索树退化为一条单链（比如插入序列是 1 2 3 … n），使得搜索效率大大降低，为了避免这种情况出现，我们采用二叉平衡树对插入结点进行调整，使得树的深度尽可能小

### 1. 定义 ###

*  平衡因子  
    BF(T) = h L \_L L \- h R \_R R，其中 h L \_L L、h R \_R R 分别是左右子树的高度
 *  平衡二叉树(AVL 树)  
    空树，或者任一结点左、右子树高度差的绝对值不超过 1，即 |BF(T)|≤1 的树

![20181102110417706.jpg][]

### 2. 平衡二叉树的调整 ###

#### 0. 遵循原则 ####

*  从离插入结点最近的结点调整

#### 1. RR 单旋 ####

当"插入结点"(BR)是"被破坏平衡结点"(A)**右子树**的**右子树**时，即 RR 插入时，采用 RR 旋转调整  
![20181102110800268.jpg][]  
其基本思路是把 B 的左子树腾出来挂到 A 的右子树上，返回 B 作为当前子树的根

示意图：  
![20181102113105538.jpg][]

AVLTree RRRotation(AVLTree A){
        
    	AVLTree B = A->right;   // B 为 A 的右子树  
    	A->right = B->left;    // B 的左子树挂在 A 的右子树上 
    	B->left = A;   //  A 挂在 B 的左子树上 
    	return B;  // 此时 B 为根结点了   
    }

#### 2. LL 单旋 ####

当"插入结点"(BL)是"被破坏平衡结点"(A)**左子树**的**左子树**时，即 LL 插入，采用 RR 旋转调整  
![20181102112405164.jpg][]  
其基本思路是把 B 的右子树腾出来挂到 A 的左子树上，返回 B 作为当前子树的根

示意图：  
![20181102114124904.jpg][]

AVLTree LLRotation(AVLTree A){
        
    	// 此时根节点是 A 
    	AVLTree B = A->left;  // B 为 A 的左子树  
    	A->left = B->right;   // B 的右子树挂在 A 的左子树上 
    	B->right = A;     //  A 挂在 B 的右子树上 
    	return B;  // 此时 B 为根结点了 
    }

#### 3. LR 双旋 ####

当"插入结点"(CL 或者 CR)是"被破坏平衡结点"(A)**左子树**的**右子树**时，即 LR 插入，采用 LR 旋转调整  
![20181102112415831.jpg][]  
基本思想是先将 B 作为根结点进行 **RR 单旋**转化为 LL 插入，再将 A 作为根结点进行 **LL 单旋**（先 RR 再 LL）

示意图：  
![20181102115543530.jpg][]

AVLTree LRRotation(AVLTree A){
        
    	// 先 RR 单旋
    	A->left = RRRotation(A->left);
    	// 再 LL 单旋 
    	return LLRotation(A);
    }

总结：叫 LR 双旋是从上到下看，而实际先 RR 单旋再 LL 单旋是从下往上的过程

#### 4. RL 双旋 ####

当"插入结点"(CL 或者 CR)是"被破坏平衡结点"(A)**右子树**的**左子树**时，即 RL 插入，采用 RL 旋转调整  
![20181102112435166.jpg][]  
基本思想是先将 B 作为根结点进行 **LL 单旋**转化为 RR 插入，再将 A 作为根结点进行 **RR单旋**（先 LL 再 RR）

示意图：  
![20181102115827971.jpg][]

AVLTree RLRotation(AVLTree A){
        
    	// 先 LL 单旋
    	A->right = LLRotation(A->right);
    	// 再 RR 单旋 
    	return RRRotation(A); 
    }

总结：叫 RL 双旋是从上到下看，而实际先 LL 单旋再 RR 单旋是从下往上的过程

### 练手题 ###

[Root of AVL Tree][]

[20181102110417706.jpg]: /images/20220422/c4803639c9f649fab6081c0a09c70d37.png
[20181102110800268.jpg]: /images/20220422/7f68ff9fccfa4a8f8c25248a78fc73cb.png
[20181102113105538.jpg]: /images/20220422/ee4c2c5f69574b0cb4001eb9cc0de816.png
[20181102112405164.jpg]: /images/20220422/35eb266ce2cc4f07ae6e3d8294e9e504.png
[20181102114124904.jpg]: /images/20220422/b689547916494359859c550802bd708f.png
[20181102112415831.jpg]: /images/20220422/caeab68679ff4b39936a2e896fcd0850.png
[20181102115543530.jpg]: /images/20220422/207b4431586f45cd82603b0684c0628d.png
[20181102112435166.jpg]: /images/20220422/3b7f4f2e17ce4831b104c53151d2ba45.png
[20181102115827971.jpg]: /images/20220422/e6762c2e11b149f4a88c943cd5631a2e.png
[Root of AVL Tree]: https://blog.csdn.net/liyuanyue2017/article/details/83653257