前言
前面介绍的二叉堆，红黑树以及斐波那契堆，其重要的操作都要O(lgn).当特定条件下，能否够规避Ω(lglgn)下界的限制？在本章中，我们将看到：van Emde Boas树支持优先队列操作及一些其他操作，每个操作最后情况运行时间为O(lglgn)。而这种数据结构限制关键字必须为0~n-1的整数且无重复。
基本方法
在介绍van Emde Boas树之前，先了解几种动态集合的存储方法。虽然这些操作虽然无法达到O(lglgn)。
直接寻址
即位图bitmap方法。
insert，delete和member：复杂度O(1)
minimum，maximum，successor和predecessor最坏情况为O(u)
假设最小在u位置，则minimun，要查看0-u-1的位置
叠加的二叉树结构
在bitmap上面加一层位二叉树。当且仅当其子树中任一个叶节点包含1，则其内部结点为1。
每个操作至多沿树进行一趟向上和一趟向下的过程，因此每个操作的最坏情况运行时间为O(lgn)。
这种方法仅仅比红黑树好一点。member操作为O(1).其它的都是O(lgn)
叠加的一棵高度恒定的树
叠加的树度数为u\sqrt{u}u。树的高度则为loguu=1log_{\sqrt{u}} \sqrt{u} = 1loguu=1
每个操作中，最多对两个大小为u\sqrt{u}u位的簇以及summary数组进行搜索，所以每个操作耗费O(u)O(\sqrt{u})O(u)时间
递归结构
我们对叠加树想法进行修改。叠加树用到了大小为u\sqrt{u}u的summary数组，数组的每项都指向一个大小为u\sqrt{u}u的另一个结构。现在使用结构递归，每次递归都已平方根大小缩减全域。（u，u1/2，u1/4，u1/8，…）
即对上述得到summary继续做恒定树
_2summary[2] = {1,1}
_2summary[0] 指向 summary[0],summary[1]
以此类推
原型van Emde Boas结构
根据递归式的思想。我们设计一个递归数据结构来支持这些操作。
以此结构设计，树的高度则为lglgulglgulglgu
原型van Emde Boas结构上的操作
看下原型van Emde Boas各操作复杂度
判断一个值是否在集合中
Prote-vEB-Member(V, x)if V.u == 2return V.A[x]elseProte-vEB-Member(V.cluster[high(x)], low(x))
即O(lglgn)。
查找最小元素
Proto-vEB-Minimum(V)if V.u == 2if V.A[0] == 1return 0else if V.A[1] == 1return 1elsemin-cluster = Proto-vEB-Minimum(V.summary)if min-cluster == NILreturn NILelseoffset = min-cluster = Proto-vEB-Minimum(V.cluster[min-cluster])return index(min-cluster, offset)
根据递归式T(u)=2T(u)+O(1)T(u) = 2T(\sqrt{u})+O(1)T(u)=2T(u)+O(1).利用主方法解得O(lgu).
查找后继
Proto-vEB-Successor(V, x)if V.u == 2if x == 0 and V.A[1] == 1return 1elsereturn NILelseoffset = Proto-vEB-Successor(V.cluster[high(x)], low(x))if offset != NILreturn index(high(x), offset)elsesucc-cluster = Proto-vEB-Successor(V.summary, high(x))if succ-cluster == NILreturn NILelseoffset = Proto-vEB-Minimum(V.cluster[succ-cluster])return index(succ-cluster, offset)
根据递归式T(u)=2T(u)+O(lgu)T(u) = 2T(\sqrt{u})+O(lg\sqrt{u})T(u)=2T(u)+O(lgu).利用主方法解得O(lg u lglg u).
插入元素
Proto-vEB-Insert(V, x)if V.u == 2V.A[x] = 1elseProto-vEB-Insert(V.cluster[high(x)], x)Proto-vEB-Insert(V.summary, high(x))
根据递归式T(u)=2T(u)+O(1)T(u) = 2T(\sqrt{u})+O(1)T(u)=2T(u)+O(1).利用主方法解得O(lgu).
删除元素
删除元素比插入更复杂，插入时总将一个summary位置为1.而删除却不能置为0。
PROTO-vEB-DELETE(V, x)if V.u == 2V.A[x] = 0elsePROTO-vEB-DELETE(V.cluster[high(x)], low(x))inCluster = falsefor i = 0 to sqrt(u) - 1if PROTO-vEB-MEMBER(V.cluster[high(x)], low(i))inCluster = truebreakif inCluster == falsePROTO-vEB-DELETE(V.summary, high(x))
根据递归式T(u)=T(u)+O(ulglgu)T(u) = T(\sqrt{u})+O(\sqrt{u} lglgu)T(u)=T(u)+O(ulglgu).利用主方法解得O(ulglgu)O(\sqrt{u} lglgu)O(ulglgu).
van Emde Boas树
van Emde Boas对 Proto-vEB结构基本上增加了max,min属性。
min存储了veb树中的最小元素max存储了veb树中的最大元素
min和max属性是减少vEB树上这些操作的递归调用次数的关键，这两个属性有4个方面的作用：
minimum和maximum操作不需要递归，因为可以直接返回min和max的值；successor操作可以避免一个用于判断值x的后继是否位于high(x)中的递归调用。这是因为x的后继位于x簇中，当且仅当x严格小于x簇的max。对于prodecessor和min情况，可以对照得到。通过min和max的值，可以在常数时间内告知一棵vEB树是否为空、仅含一个元素或两个以上元素。如何min和max都为NIL，那么vEB树为空，如何min和max 都不为NIL但彼此相等，那么vEB树仅含一个元素。如果min和max都不为NIL且不等，那么vEB树包含两个或两个以上元素。如果一棵vEB树为空，那么可以仅更新它的min和max值为实现插入一个元素。
查找最小元素和最大元素
vEB-Tree-Minimum(V)return V.minvEB-Tree-Maximum(V)return V.max
操作复杂度为O(1)
判断一个值是否在集合中
vEB-Tree-Member(V, x)if x == V.min or x == V.maxreturn trueelse if V.u == 2return falseelsereturn vEB-Tree-Member(V.cluster[high(x)], low(x))
即O(lglg u)。
查找后继和前驱
vEB-Tree-Successor(V, x)if V.u == 2if x == 0 and V.max == 1return 1elsereturn NILelse if V.min != NIL and x < V.minreturn V.minelsemax-low = vEB-Tree-Maximum(V.cluster[high(x)])if max-low != NIL and low(x) < max-lowoffset = vEB-Tree-Successor(V.cluster[high(x)], low(x))return index(high(x), offset)elsesucc-cluster = vEB-Tree-Successor(V.summary, high(x))if succ-cluster == NILreturn NILelseoffset = vEB-Tree-Miniimum(V.cluster[succ-cluster])return index(succ-cluster, offset)vEB-Tree-Predecessor(V, x)if V.u == 2if x == 1 and V.min == 0return 0elsereturn NILelse if V.max != NIL and x > V.maxreturn V.maxelsemin-low = vEB-Tree-Minimum(V.cluster[high(x)])if min-low != NIL and low(x) > min-lowoffset = vEB-Tree-Predecessor(V.cluster[high(x)], low(x))return index(high(x), offset)elsepred-cluster = vEB-Tree-Predecessor(V.summary, high(x))if pred-cluster == NILif V.min != NIL and x > V.maxreturn V.minelsereturn NILelseoffset = vEB-Tree-Minimum(V.cluster[pred-cluster])return index(pred-cluster, offset)
找到值，然后取前后的最大值，最小值即可 ,即O(lglg u)。
插入一个元素
vEB-Empty-Tree-Insert(V, x)V.min = xV.max = xvEB-Tree-Insert(V, x)if V.min == NILvEB-Empty-Tree-Insert(V, x)elseif x < V.minexchange x with x.minif V.u > 2if vEB-Tree-Minimum(V.cluster[high(x)]) == NILvEB-Tree-Insert(V.summary, high(x))vEB-Empty-Tree-Insert(V.cluster[high(x)], low(x))elsevEB-Tree-Insert(V.cluster[high(x)], low(x))if x > V.maxV.max = x
插入时，如果是最大或者最小值 ，从上往下改，不是则不用。即O(lglg u)
删除一个元素
vEB-Tree-Delete(V, x)if V.min == V.maxV.min = NILV.max = NILelse if V.u == 2if x == 0V.min = 1elseV.min = 0V.max = V.minelseif x == V.minfirst-cluster = vEB-Tree-Minimum(V.summary)x = index(first-cluster, vEB-Tree-Minimum(V.cluster[first-cluster]))V.min =xvEB-Tree-Delete(V.cluster[high(x)], low(x))if vEB-Tree-Minimum(V.cluster[high(x)]) == NILvEB-Tree-Delete(V.summary, high(x))if x = V.maxsummary-max = vEB-Tree-Maximum(V.summary)if summary-max == NILV.max = V.minelseV.max = index(summary-max, vEB-Tree-Maximum(V.cluster[summary-max]))elseif x == V.maxV.max = index(high(x), vEB-Tree-Maximum(V.cluster[high(x)]))
插入时，如果是最大或者最小值 ，从上往下改，不是则不用。即O(lglg u)
主要参考
《van Emde Boas Trees》
