PAT 1123. Is It a Complete AVL Tree (30)

AVL树的插入，旋转。

#include<map>

#include<set>

#include<ctime>

#include<cmath>

#include<queue>

#include<string>

#include<stack>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

int n;

struct X

{

    int val,L,R,hL,hR,fa;

}s[];

int sz,F,root=;

void Insert(int x)

{

    int p=root;

    while()

    {

        if(x<s[p].val)

        {

            if(s[p].L==-)

            {

                sz++;

                s[p].L=sz;

                s[sz].val=x;

                s[sz].fa=p;

                break;

            }

            else p=s[p].L;

        }

        else

        {

            if(s[p].R==-)

            {

                sz++;

                s[p].R=sz;

                s[sz].val=x;

                s[sz].fa=p;

                break;

            }

            else p=s[p].R;

        }

    }

}

void dep(int x)

{

    if(s[x].L!=-) dep(s[x].L);

    if(s[x].R!=-) dep(s[x].R);

    if(s[x].L!=-) s[x].hL = max(s[s[x].L].hL,s[s[x].L].hR)+;

    else s[x].hL=;

    if(s[x].R!=-) s[x].hR = max(s[s[x].R].hL,s[s[x].R].hR)+;

    else s[x].hR=;

}

void dfs(int x)

{

    if(abs(s[x].hL-s[x].hR)>) F=x;

    if(s[x].L!=-) dfs(s[x].L);

    if(s[x].R!=-) dfs(s[x].R);

}

void Left(int x)

{

    int son = s[x].R;

    X tmpA = s[x];

    X tmpB = s[son];

    s[x].R = tmpB.L;

    s[x].fa = son;

    s[son].L = x;

    s[son].fa = tmpA.fa;

    s[tmpB.L].fa = x;

    if(s[son].fa!=-)

    {

        int Fa = s[son].fa;

        if(s[Fa].L==x) s[Fa].L=son;

        else s[Fa].R=son;

    }

}

void Right(int x)

{

    int son = s[x].L;

    X tmpA = s[x];

    X tmpB = s[son];

    s[x].L = tmpB.R;

    s[x].fa = son;

    s[son].R = x;

    s[son].fa = tmpA.fa;

    s[tmpB.R].fa = x;

    if(s[son].fa!=-)

    {

        int Fa = s[son].fa;

        if(s[Fa].L==x) s[Fa].L=son;

        else s[Fa].R=son;

    }

}

void bfs()

{

    queue<int>Q; Q.push(root);

    vector<int>ans;

    while(!Q.empty())

    {

        int h = Q.front(); Q.pop();

        ans.push_back(s[h].val);

        if(s[h].L!=-) Q.push(s[h].L);

        if(s[h].R!=-) Q.push(s[h].R);

    }

    for(int i=;i<ans.size();i++)

    {

        printf("%d",ans[i]);

        if(i<ans.size()-) printf(" ");

        else printf("\n");

    }

}

bool fail;

void check(int x,int id)

{

    if(id>n) fail=;

    if(s[x].L!=-) check(s[x].L,*id);

    if(s[x].R!=-) check(s[x].R,*id+);

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=;i++)

    {

        s[i].val=s[i].L=s[i].R=-;

        s[i].hL = s[i].hR = ;

    }

    int x; scanf("%d",&x); s[].val=x; s[].fa=-;

    for(int i=;i<=n;i++)

    {

        int x; scanf("%d",&x); Insert(x);

        dep(root); F=-; dfs(root);

        if(F==-) continue;

        if(s[F].hL>s[F].hR&&s[s[F].L].hL>s[s[F].L].hR) Right(F);

        else if(s[F].hL<s[F].hR&&s[s[F].R].hL<s[s[F].R].hR) Left(F);

        else if(s[F].hL>s[F].hR&&s[s[F].L].hL<s[s[F].L].hR) Left(s[F].L), Right(F);

        else if(s[F].hL<s[F].hR&&s[s[F].R].hL>s[s[F].R].hR) Right(s[F].R), Left(F);

        for(int j=;j<=sz;j++) if(s[j].fa==-) root=j;

    }

    bfs();

    fail=; check(root,);

    if(fail) printf("NO\n");

    else printf("YES\n");

    return ;

}