平衡树

RRLee · 2025-07-23 10:05:22 · 个人记录

#include<bits/stdc++.h>
using namespace std;
int cnt=1;
struct tree{
    int num,left,head,right,t;
};
tree a[10000];
void find(int p,int q){
    if(a[p].num>=a[q].num){
        if(a[p].left==0){
            a[p].left=q;
            a[q].head=p;
        }
        else find(a[p].left,q);
        if(a[p].t>a[a[p].left].t){
            a[a[p].left].head=a[p].head;
            if(a[a[p].head].left==p) a[a[p].head].left=a[p].left;
            else a[a[p].head].right=a[p].left;
            a[p].head=a[p].left;
            a[p].left=a[a[p].head].right;
            a[a[p].head].right=p;
        }
    }
    else{
        if(a[p].right==0){
            a[p].right=q;
            a[q].head=p;
        }
        else find(a[p].right,q);
        if(a[p].t>a[a[p].right].t){
            a[a[p].right].head=a[p].head;
            if(a[a[p].head].left==p) a[a[p].head].left=a[p].right;
            else a[a[p].head].right=a[p].right;
            a[p].head=a[p].right;
            a[p].right=a[a[p].head].left;
            a[a[p].head].left=p;
        }
    }

}
void prt(int p){
    if(a[p].left>0) prt(a[p].left);
    cout<<a[p].num<<" ";
    if(a[p].right>0) prt(a[p].right);
}
int main(){
    int n,h,i,j,k;
    cin>>n>>h;
    a[1].head=1;
    a[1].num=h;
    a[cnt].left=0;
    a[cnt].right=0;
    a[cnt].t=-1;
    for(i=1;i<n;i++){
        cnt++;
        cin>>a[cnt].num;
        a[cnt].left=0;
        a[cnt].right=0;
        a[cnt].t=rand()%1000;
        find(1,cnt);
    }
    prt(1);
}