高级树结构之平衡二叉树（ALV树）

雨点打透心脏的1/2处 2024-03-29 15:02 73阅读 0赞

#### 文章目录 ####

*  平衡二叉树简介
 *  失衡类型&处理办法
 *   *  RR型失衡【左旋调整】
     *   *  调整演示
         *  代码实现
     *  LL型失衡【右旋调整】
     *   *  调整演示
         *  代码实现
     *  RL型失衡【先右旋，后左旋调整】
     *   *  调整演示
         *  代码实现
     *  LR型失衡【先左旋，后右旋调整】
     *   *  调整演示
         *  代码实现
     *  插入操作
     *  综合代码演示

## 平衡二叉树简介 ##

*  在数据有序的情况下，进行动态二叉树的创建时，二叉树会变得非常长。那么在进行查找某个节点的时候，就会变成线性查找。  
    ![在这里插入图片描述][550524a41acb46498b2aa99a9e4b8629.png]
 *  平衡二叉树：***一颗左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树的二叉排序树。***
    
     *  ***注意：空树也是一颗平衡二叉树***
 *  平衡二叉树的性质：
    
     *  平衡二叉树是一颗二叉查找树
     *  任意节点的左右子树也是一颗平衡二叉树
     *  从根节点开始，左右子树的高度差不超过1，否则视为不平衡
 *  平衡因子：***二叉树上结点的左子树的高度减去右子树高度得到的结果***为该节点的平衡因子  
    ![在这里插入图片描述][9fb78274ee5447d0aa6159c46ea9e9f1.png]
 *  通过平衡因子的计算，可以判断二叉树是否失衡  
    ![在这里插入图片描述][b6f460bee1db4ef08c8bb12af18f55e5.png]
 *  为此，我们需要对失衡的二叉树进行调整使其保持平衡

## 失衡类型&处理办法 ##

*  为了保证二叉树的平衡，需要将其进行旋转来维持平衡，去纠正最小不平衡子树即可

### RR型失衡【左旋调整】 ###

*  RR型最小不平衡子树模型  
    ![在这里插入图片描述][19d95ca89e98482d8096f0ae8cb8c382.png]  
    ![在这里插入图片描述][ee1bffb8e81e4113aba77a24a376aa2b.png]

#### 调整演示 ####

*  从根节点开始向右的三个结点进行左旋操作。左旋操作要将这三个结点中间的结点作为新的根节点，其他两个结点变为左右子树  
    ![在这里插入图片描述][5c72f970844f496b850d25e9fc04c3d1.png]

#### 代码实现 ####

### LL型失衡【右旋调整】 ###

*  LL型最小不平衡子树模型  
    ![在这里插入图片描述][62bae1d67a7141e7b3eb74b6ea55539c.png]

![在这里插入图片描述][5259e6d892fa47ee8c99d6e584e11ef5.png]

*  通过计算平衡因子，找到最小不平衡子树  
    ![在这里插入图片描述][bc92cc3b17f046f3bb3dcd3bc558754f.png]

#### 调整演示 ####

*  从根节点开始向左的三个结点进行右旋操作。右旋操作要将这三个结点中间的结点作为新的根节点，其他两个结点变为左右子树  
    ![在这里插入图片描述][ad57ca88ac134b54a9f61cd3ca192800.png]

#### 代码实现 ####

int max(int a,int b) {
        
        return a>b ? a:b;
    }
    
    int getHeight(Node root) {
        
        if(root==NULL) return 0;
        return root->height;
    }
    
    //LL调整:右旋转
    Node rightRotation(Node root) {
        
        Node newNode=root->left;
        root->left=newNode->right;
        newNode->right=root;
        //计算结点高度的时候，不要忘记算上自身的高度
        root->height=max(getHeight(root->left), getHeight(root->right))+1;
        newNode->height=max(getHeight(newNode->left), getHeight(newNode->right))+1;
        return newNode;
    }

### RL型失衡【先右旋，后左旋调整】 ###

*  RL型最小不平衡子树模型  
    ![在这里插入图片描述][e87374d11331447aa398020e05a2e321.png]  
    ![在这里插入图片描述][3bc2a10ff7444130bc94cc72652c5a95.png]

#### 调整演示 ####

*  对于先右边后左边的情况，需要先右旋，后左旋
 *  注意：右旋操作针对两个结点  
    ![在这里插入图片描述][af93b38dd12447c8a01f8584d67eeeb7.png]

#### 代码实现 ####

int max(int a,int b) {
        
        return a>b ? a:b;
    }
    
    int getHeight(Node root) {
        
        if(root==NULL) return 0;
        return root->height;
    }
    
    //RR调整:左旋转
    Node leftRotation(Node root) {
        
        Node newNode=root->right;
        root->right=newNode->left;
        newNode->left=root;
        //计算结点高度的时候，不要忘记算上自身的高度
        root->height=max(getHeight(root->left), getHeight(root->right))+1;
        newNode->height=max(getHeight(newNode->left), getHeight(newNode->right))+1;
        return newNode;
    }
    
    //LL调整:右旋转
    Node rightRotation(Node root) {
        
        Node newNode=root->left;
        root->left=newNode->right;
        newNode->right=root;
        //计算结点高度的时候，不要忘记算上自身的高度
        root->height=max(getHeight(root->left), getHeight(root->right))+1;
        newNode->height=max(getHeight(newNode->left), getHeight(newNode->right))+1;
        return newNode;
    }
    
    
    //RL调整:先右旋，后左旋
    Node rightLeftRotation(Node root) {
        
        //注意这里如果newNode的right指向可以为空，符合案例的要求
        root->right= rightRotation(root->right);
        //然后左旋并返回根节点
        return leftRotation(root);
    }

### LR型失衡【先左旋，后右旋调整】 ###

*  LR型最小不平衡子树模型  
    ![在这里插入图片描述][a313d0a7b1b247af9cf2bc968235df12.png]  
    ![在这里插入图片描述][772d07375d0242a6945b3225c7b672dd.png]

#### 调整演示 ####

*  先左旋，后优旋  
    ![在这里插入图片描述][c57b674e53664aabb62456b3bf75f816.png]

#### 代码实现 ####

int max(int a,int b) {
        
        return a>b ? a:b;
    }
    
    int getHeight(Node root) {
        
        if(root==NULL) return 0;
        return root->height;
    }
    
    //RR调整:左旋转
    Node leftRotation(Node root) {
        
        Node newNode=root->right;
        root->right=newNode->left;
        newNode->left=root;
        //计算结点高度的时候，不要忘记算上自身的高度
        root->height=max(getHeight(root->left), getHeight(root->right))+1;
        newNode->height=max(getHeight(newNode->left), getHeight(newNode->right))+1;
        return newNode;
    }
    
    //LL调整:右旋转
    Node rightRotation(Node root) {
        
        Node newNode=root->left;
        root->left=newNode->right;
        newNode->right=root;
        //计算结点高度的时候，不要忘记算上自身的高度
        root->height=max(getHeight(root->left), getHeight(root->right))+1;
        newNode->height=max(getHeight(newNode->left), getHeight(newNode->right))+1;
        return newNode;
    }
    
    //LR调整:先左旋，后右旋
    Node leftRightRotation(Node root) {
        
        //注意这里如果newNode的left指向可以为空，符合案例的要求
        root->left= leftRotation(root->left);
        //然后右旋并返回根节点
        return rightRotation(root);
    }

### 插入操作 ###

*  插入结点时要注意维护整棵树的平衡因子保证其处于稳定状态，防止其退化。
 *  插入结点的思路大体上与创建二叉排序数类似
 *  同时要注意时刻保持数的平衡性。最后在查入完成后，记得及时更新节点的高度

Node insert(Node root,E element) {
        
        //如果结点为NULL，说明找到了插入的位置
        //小于相对根节点的往左边放
        //大于相对根节点的往右边放
        if(root == NULL) {
        
            root= createNode(element);
        }else if(element < root->element) {
        
            root->left= insert(root->left,element);
            //插入完成之后，计算平衡因子 判断是否失衡 并进行相关的调整
            if(getHeight(root->left) - getHeight(root->right)> 1) {
        
                //然后判断插入的数值在左子树的右边还是左边，如果在左边就是LL调整【右旋】否则就是LR调整【先左旋，后右旋】
                if(element < root->left->element) {
        
                    root= rightRotation(root);//LL型右旋之后，得到新的根节点
                }else {
        
                    root= leftRightRotation(root);//LR型 先左旋后右旋，得到新的根节点
                }
            }
        }else if(element > root->element) {
        
            root->right= insert(root->right,element);
            //插入完成之后，计算平衡因子 判断是否失衡 并进行相关的调整
            if(getHeight(root->left) - getHeight(root->right) < -1) {
        
                //然后判断插入的数值在右子树的右边还是左边，如果在右边就是RR调整【左旋】否则就是RL调整【先右旋，后左旋】
                if(element > root->right->element)
                    root= leftRotation(root);//RR型左旋之后，得到新的根节点
                else
                    root= rightLeftRotation(root);//RL型 先右旋后左旋，得到新的根节点
            }
    
        }
        //最后更新最新的结点的高度
        root->height=max(getHeight(root->left), getHeight(root->right))+1;
        //最后返回root到上一级
        return root;
    }

### 综合代码演示 ###

*  这里将之前各个部分的档案码全部展示出来，有不明白的可以直接粘贴复制进行调试探究
 *  演示二叉树的结构  
    ![在这里插入图片描述][855935daa3da400cbef9e3d2c1164b1d.png]

#include<iostream>
    using namespace std;
    typedef int E;
    typedef struct TreeNode{
        
        E element;
        struct TreeNode * left;
        struct TreeNode * right;
        //每个结点需要记录当前子树的高度，便于计算平衡因子
        int height;
    }* Node;
    
    Node createNode(E element) {
        
        Node node=(Node)malloc(sizeof(struct TreeNode));
        node->left=node->right=NULL;
        node->element=element;
        node->height=1;//树的初始化高度为1
        return node;
    }
    
    int max(int a,int b) {
        
        return a>b ? a:b;
    }
    
    int getHeight(Node root) {
        
        if(root==NULL) return 0;
        return root->height;
    }
    
    //RR调整:左旋转
    Node leftRotation(Node root) {
        
        Node newNode=root->right;
        root->right=newNode->left;
        newNode->left=root;
        //计算结点高度的时候，不要忘记算上自身的高度
        root->height=max(getHeight(root->left), getHeight(root->right))+1;
        newNode->height=max(getHeight(newNode->left), getHeight(newNode->right))+1;
        return newNode;
    }
    
    //LL调整:右旋转
    Node rightRotation(Node root) {
        
        Node newNode=root->left;
        root->left=newNode->right;
        newNode->right=root;
        //计算结点高度的时候，不要忘记算上自身的高度
        root->height=max(getHeight(root->left), getHeight(root->right))+1;
        newNode->height=max(getHeight(newNode->left), getHeight(newNode->right))+1;
        return newNode;
    }
    
    //LR调整:先左旋，后右旋
    Node leftRightRotation(Node root) {
        
        //注意这里如果newNode的left指向可以为空，符合案例的要求
        root->left= leftRotation(root->left);
        //然后右旋并返回根节点
        return rightRotation(root);
    }
    
    //RL调整:先右旋，后左旋
    Node rightLeftRotation(Node root) {
        
        //注意这里如果newNode的right指向可以为空，符合案例的要求
        root->right= rightRotation(root->right);
        //然后左旋并返回根节点
        return leftRotation(root);
    }
    
    Node insert(Node root,E element) {
        
        //如果结点为NULL，说明找到了插入的位置
        //小于相对根节点的往左边放
        //大于相对根节点的往右边放
        if(root == NULL) {
        
            root= createNode(element);
        }else if(element < root->element) {
        
            root->left= insert(root->left,element);
            //插入完成之后，计算平衡因子 判断是否失衡 并进行相关的调整
            if(getHeight(root->left) - getHeight(root->right)> 1) {
        
                //然后判断插入的数值在左子树的右边还是左边，如果在左边就是LL调整【右旋】否则就是LR调整【先左旋，后右旋】
                if(element < root->left->element) {
        
                    root= rightRotation(root);//LL型右旋之后，得到新的根节点
                }else {
        
                    root= leftRightRotation(root);//LR型 先左旋后右旋，得到新的根节点
                }
            }
        }else if(element > root->element) {
        
            root->right= insert(root->right,element);
            //插入完成之后，计算平衡因子 判断是否失衡 并进行相关的调整
            if(getHeight(root->left) - getHeight(root->right) < -1) {
        
                //然后判断插入的数值在右子树的右边还是左边，如果在右边就是RR调整【左旋】否则就是RL调整【先右旋，后左旋】
                if(element > root->right->element)
                    root= leftRotation(root);//RR型左旋之后，得到新的根节点
                else
                    root= rightLeftRotation(root);//RL型 先右旋后左旋，得到新的根节点
            }
    
        }
        //最后更新最新的结点的高度
        root->height=max(getHeight(root->left), getHeight(root->right))+1;
        //最后返回root到上一级
        return root;
    }
    
    void inOrder(Node root) {
        
        if(root==NULL) return ;
        inOrder(root->left);
        cout<<root->element<<" ";
        inOrder(root->right);
    }
    
    int main() {
        
        Node root=NULL;
        root= insert(root,15);
        root= insert(root,20);
        root= insert(root,12);
        root= insert(root,11);
        root= insert(root,13);
        root= insert(root,14);
        inOrder(root);
        return 0;
    }

![在这里插入图片描述][e106a4298be248e8bcca8a218ddc0a23.png]  
![在这里插入图片描述][be0528d0b6294f1faca99928321735c6.png]

[550524a41acb46498b2aa99a9e4b8629.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/e36c448ad4984245b2878bbfbb875db2.png
[9fb78274ee5447d0aa6159c46ea9e9f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/381ef9348d7d4b68a3160c0b91bfbb7d.png
[b6f460bee1db4ef08c8bb12af18f55e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/0fc6c3a0a6484438a06666112a8516a8.png
[19d95ca89e98482d8096f0ae8cb8c382.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/996400b499274aaa804f1514c8caa539.png
[ee1bffb8e81e4113aba77a24a376aa2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/c7bc886749b94353b6d209cbddbf2ca3.png
[5c72f970844f496b850d25e9fc04c3d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/fdb540bfd1004dbbb32ba5e6f0ffe727.png
[62bae1d67a7141e7b3eb74b6ea55539c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/07ff114280734386ab8dc6a24da4afff.png
[5259e6d892fa47ee8c99d6e584e11ef5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/1c6c20a6f71e4606974cbccf91107d64.png
[bc92cc3b17f046f3bb3dcd3bc558754f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/0a52872176dd447e8d244193de1269fa.png
[ad57ca88ac134b54a9f61cd3ca192800.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/778196f7f702442c9a0bd0e275bc46ec.png
[e87374d11331447aa398020e05a2e321.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/f8b845a068484270a6c1960d99745205.png
[3bc2a10ff7444130bc94cc72652c5a95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/eae54ce7ba7e4b188a176e304e4a5207.png
[af93b38dd12447c8a01f8584d67eeeb7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/b0a24d75e3fb4602878240d888d4e87d.png
[a313d0a7b1b247af9cf2bc968235df12.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/e5f257f35f94441fbe35d71c9941e3da.png
[772d07375d0242a6945b3225c7b672dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/dd92f26dc6a94131bf29b665c9400166.png
[c57b674e53664aabb62456b3bf75f816.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/3fa6813872fa4d5e8b9fe6384ce5f373.png
[855935daa3da400cbef9e3d2c1164b1d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/a202207b92294bff823e51bac6c2c17d.png
[e106a4298be248e8bcca8a218ddc0a23.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/c378489a48144b8b95f40967da419a4e.png
[be0528d0b6294f1faca99928321735c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/f391d624121645fc94ae5d05e4d5e2bd.png