一种插入、查找后继节点耗时为 lglgu 的算法van Emde Boas Trees

Insert(V,x):
    //先在u中插入元素
    Insert(V.cluster[high(x)],low(x))
    //更新summary
    Insert(V.summary,high(x))
复制代码

Successor(V,x):
    //计算出在那个cluster
    i=high(x)
    //查找当前的cluster是不是有这个元素
    j=Successor(V.cluster[i],low(x))
    if j not exist:
        //先找到i后面的非空的summary
        i=Successor(V.summary,i)
        //从找到的cluster中寻找后继者，Integer.MIN_VALUE表示我不知道具体的位置是那个
        j=Successor(V.cluster[i],Integer.MIN_VALUE)
    return index(i,j)
复制代码

Successor(V,x):
    //最小的元素只存储在V.min
    if x < V.min:
        return V.min
    i=high(x)
    if low(x) < V.cluster[i].max:
        j=Successor(V.cluster[i],low(x))
    else
        i=Successor(V.summary,high(x))
        j=V.cluster[i].min
    return index(i,j)
复制代码

Insert(V,x):
    //先考虑V没有元素存在
    if V.min == None
        V.min=V.max=x
        return
    if x<V.min
        swap(x,V.min)
    if x>V.max
        V.max=x
    //如果当前cluster没有元素
    if V.cluster[high(x)].min == None:
        Insert(V.summary,high(x))  //第一次调用Insert，custer之前没有值，更新summary
    Insert(V.cluster[high(x)],low(x))  //第二次调用Insert,在u中插入元素
复制代码