2-3-4 Tree

2-3-4 Tree 介绍

Conclusion
2-3-4 is great regarding memory and time complexity. Why isn’t it widely used?
You may have noticed that while understanding 2-3-4 Tree is easy but implementing such a tree is complicated due to multiple node types and frequent switching of node types at each insertion and deletion. Also, Red-Black trees are an isometry of 2-3-4 Trees but are structured as a binary search tree that makes several operations easier to implement.
Hence, 2-3-4 trees are studied to understand the theory behind Red-Black trees but in practice, Red-Black trees are more widely used than 2-3-4 trees.

（这玩意实现起来太费劲了！还好平时学的线段树都是二叉树，而不是三叉四叉的，2333）

插入函数(按执行顺序)：

1. 若当前为4-node节点
   1. 考虑将中间的数拿出来放到father节点里，并将剩下两个数拆开分成连个2-node节点（若将中间的数放到father节点里后又构成了一个4-node节点，则不需要继续拆分）
   2. 如果当前节点为根节点，即没有father节点，则考虑新建一个root节点
2. 若当前节点为叶子节点，则直接插入
3. 其他情况从当前节点向下找位置迭代

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 5e3+10;
const int mod = 1e9+7;
const double eps = 1e-9;

struct Node{
    bool r; //是否为根节点
    int f, fa, s; //f表示类型（2-3-4 node），fa表示父节点，s表示已有的儿子个数（为0则表示叶节点）
    int son[4], data[3]; //儿子节点，data表示值域
}node[maxn*100];

int n, root, tot; //tot为总节点数

void bfs(int now) { //前序遍历
    for(int i=0; i<node[now].f-1; ++i) printf("%d ", node[now].data[i]);
    puts("");
    for(int i=0; i<node[now].f; ++i) {
        if(node[now].son[i]) {
            bfs(node[now].son[i]);
        }
    }
}

void insert(int a, int now); //要插入的值为a(不是下面的aa)

void push_up(int a, int aa, int now) { //将a这个值放到父节点中来，要插入的值为aa
    if(a) { //为了区分当前节点是否为新建的root节点，如果不是的话则执行下面的插入
        int pos=0;
        for(; pos<node[now].f-1&&a>node[now].data[pos]; ++pos); //找到插入的位置
        for(int i=node[now].f-1; i>pos; --i) node[now].data[i]=node[now].data[i-1]; //把后面的值往后挪个位置
        node[now].data[pos]=a;
        for(int i=node[now].f; i>pos+1; --i) node[now].son[i]=node[now].son[i-1]; //把后面的儿子节点往后挪个位置
        node[now].son[pos+1]=tot; //插入新建的儿子节点
        node[now].f++;
        node[now].s++;
    }
    int pos=0; //这里跟下面insert函数里面的插入是一样的
    for(; pos<node[now].f-1&&aa>node[now].data[pos]; ++pos);
    if(node[now].son[pos]==0) {
        node[now].s++;
        node[now].son[pos]=++tot;
        node[tot].f=2; node[tot].data[0]=aa;
        node[tot].fa=now;
    }
    else insert(aa,node[now].son[pos]);
}

void insert(int a, int now) {
    if(node[now].f==4) { //如果为4-node节点，则考虑拆分
        int pu=node[now].data[1]; //中间的值
        ++tot;
        node[tot].f=node[now].f=2;
        node[tot].data[0]=node[now].data[2];
        node[now].data[2]=0;
        if(node[now].son[2]) node[tot].son[0]=node[now].son[2], node[node[now].son[2]].fa=tot, node[tot].s++;//虽然把儿子节点转移到tot里了，但别忘了更改儿子的父节点！这个地方也卡了好久
        if(node[now].son[3]) node[tot].son[1]=node[now].son[3], node[node[now].son[3]].fa=tot, node[tot].s++;
        node[now].s-=node[tot].s;
        node[now].son[2]=node[now].son[3]=0;
        if(!node[now].r) { //如果当前节点不是根节点，则将中间的值正常地加入到到父节点中
            node[tot].fa=node[now].fa;
            push_up(pu,a,node[now].fa);
        }
        else { //如果是根节点的话，手动处理好根节点的细节
            node[now].r=0;
            root=++tot; node[tot].r=1; //换根
            node[now].fa=node[tot-1].fa=tot; //别忘了更新父节点
            node[tot].f=2; node[tot].s=2; //新的根节点一定是2-node的，毕竟只有一个值
            node[tot].son[0]=now, node[tot].son[1]=tot-1; //两个儿子加入新的根节点
            node[tot].data[0]=pu;
            push_up(0,a,tot); //用0表示没有值需要加入这个父节点，但还得从父节点（也就是新的根节点）开始寻找a的位置
        }
    }
    else if(node[now].s==0) { //如果当前节点为叶子节点，则直接插入
        node[now].data[node[now].f-1]=a;
        node[now].f++;
        sort(node[now].data,node[now].data+node[now].f-1);
    }
    else { //其余情况，正常的迭代
        int pos=0;
        for(; pos<node[now].f-1&&a>node[now].data[pos]; ++pos);
        if(node[now].son[pos]==0) { //如果这个位置没有儿子，则新建一个儿子
            node[now].s++;
            node[now].son[pos]=++tot;
            node[tot].f=2; node[tot].data[0]=a;
            node[tot].fa=now;
        }
        else insert(a,node[now].son[pos]);
    }
}

void solve(int cas) {
    for(int i=0; i<=tot; ++i) { //多组数据，按照用过的节点进行初始化，节省时间
        node[i].r=0; node[i].f=node[i].fa=node[i].s=0;
        memset(node[i].son,0,sizeof(node[i].son));
        memset(node[i].data,0,sizeof(node[i].data));
    }
    n=read();
    tot=1, root=1;
    scanf("%d", &node[root].data[0]); node[root].r=1, node[root].f=2; //根节点特殊处理一下
    for(int i=1; i<n; ++i) insert(read(),root); //插入剩下的n-1个值
    printf("Case #%d:\n", cas);
    bfs(root); //前序遍历一波就完事了，2333
}

int main() {
	//ios::sync_with_stdio(false);
    int T=read(), t=T;
    while(T--) solve(t-T); 
}