PAT甲级1066 Root of AVL Tree

快来打我* 2023-03-13 13:02 45阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]  
常规的AVL树模板题，建好树后直接输出根结点的数据即可

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    struct node{ 
        int data,height;
        node *l,*r;
    };
    int getheight(node* root)//空结点高度0
    { 
        if(root==NULL)return 0;
        else return root->height;
    }
    int getbalancefactor(node* root)//左子树高度减去右子树高度
    { 
        return getheight(root->l)-getheight(root->r);
    }
    void updataheight(node* root)//可引用？
    { 
        root->height=max(getheight(root->l),getheight(root->r))+1;
    }
    void left_rotation(node* &root)//左旋
    { 
        node* temp=root->r;
        root->r=temp->l;
        temp->l=root;
        updataheight(root);
        updataheight(temp);
        root=temp;
    }
    void right_rotation(node* &root)//右旋
    { 
        node* temp=root->l;
        root->l=temp->r;
        temp->r=root;
        updataheight(root);
        updataheight(temp);
        root=temp;
    }
    void insert(node* &root,int x)
    { 
        if(root==NULL)//插入位置
        { 
            root=new node;
            root->data=x;
            root->height=1;
            root->l=root->r=NULL;
            return;
        }
        if(x<root->data)
        { 
            insert(root->l,x);
            updataheight(root);
            if(getbalancefactor(root)==2)
            { 
                if(getbalancefactor(root->l)==1)//LL型
                { 
                    right_rotation(root);
                }
                else//LR型,先对子树旋转
                { 
                    //right_rotation(root);
                    left_rotation(root->l);
                    right_rotation(root);
                }
            }
        }
        else
        { 
            insert(root->r,x);
            updataheight(root);
            if(getbalancefactor(root)==-2)
            { 
                if(getbalancefactor(root->r)==-1)//RR,对根节点左旋
                left_rotation(root);
                else
                { 
                    //left_rotation(root);
                    right_rotation(root->r);
                    left_rotation(root);
                }
            }
        }
    }
    int main()
    { 
        int n,temp;
        cin>>n;
        node* rot=NULL;
        for(int i=0;i<n;i++)
        { 
            cin>>temp;
            insert(rot,temp);
        }
        cout<<rot->data<<endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230312/b51e8809409a45c48815db7f17165d97.png