算法导论 van Emde Boas 树

结构

vEB(u)表示全域值为{0,1,2,…,u-1} vEB 树min 表示 vEB 树中最小值,该值元素不出现在任何递归的子树(簇) vEB(u↓\sqrt[\downarrow]{u}↓u​)中max 表示 vEB 树中最大值summary 指向 vEB(u↑\sqrt[\uparrow]{u}↑u​)新的树，summary[i]表示子树 cluster[i]的逻辑或cluster[0…u↑\sqrt[\uparrow]{u}↑u​－1]表示u↑\sqrt[\uparrow]{u}↑u​个簇数组，每个数组元素的结构为递归子树结构 vEB(u↓\sqrt[\downarrow]{u}↓u​)任意全域值 x,0<=x<u; high(x)=x/u↓\sqrt[\downarrow]{u}↓u​ ;表示 x 所在的簇号low(x)=x mod u↓\sqrt[\downarrow]{u}↓u​; 表示 x 在簇号中的位置index(x,y) = x u↓\sqrt[\downarrow]{u}↓u​ + y; 根据簇号及簇号在的位置得到一个元素值

操作

插入(V 树 insert 插入 x 值）

如果 V 树是空的，则将 V.min = V.max = x;结束如果 x<V.min，则将 x 与 V.min 交换，继续插入 x(值为旧的 V.min)如果 V.u >2 找到 x 对应的簇 high(x),所在簇的位置 low(x)，x 对应的子树即为 V.cluster[high(x)]如果子树为空，则 V.cluster.min = V.cluster.max = x;V.summary 也要插入 high(x)如果子树不为空，则递归插入到子树中。（summary 信息不用更新因为子树已经存在） 如果 x>V.max，则将 V.max = x;

是否存在(member)

先判断 V.min=x 或者 V.max=x,则返回 true如果 V.u=2;则返回 false否则递归查找子树 V.cluster[high(x)]中的位置 low(x)

后继(successor)

如果 V.u = 2; x=0 ,V.max = 1,则返回 1否则返回 null 如果 x < V.min,则返回 V.min找到 x 对应的子树 V.cluster[high(x)]及子树中的位置 low(x) x 小于子树的最大值，则直接在子树中查找否则在 V.summary 中找出 x 对应的后续簇，在后续簇对应的子树中查找

前驱(predecessor)

如果 V.u = 2 如果 x=1,V.min=0,则返回 0否则返回 null 如果 x > V.max，则返回 V.max找到 x 对应的子树 V.cluster[high(x)]及子树中的位置 low(x) 如果 x 大于子树中的最小值，则在子树中找否则在 V.summary 中找 x 对应的前驱簇， 如果前驱簇为 null 且 x>V.min，则返回 V.min如果前驱簇不为 null，则直接在前驱簇对应的子树中查找最大值

删除(delete)

如果树只有一个元素，则直接将 V.min=V.max = null如果树有两个元素， 如果被删除 x == 0 ,则 V.min = V.max = 1否则 V.min = V.max = 0 树包含两个以上元素 如果 x = V.min，则将 V.min 改为 x 所在簇的最小值,x 也修改为此值V.cluster[high(x)]递归删除 x如果 V.cluster[high(x)].min = null，则将 V.summary[high(x)]也要删除;如果 V.max = x,则要重新找到 V.cluster 中最大值，并赋给 V.max如果 V.max = x,则要同时更新 V.max ＝ V.cluster[high(x)].max

源代码

1./beimuaihui/LayaAir/blob/my_introduction_to_algorithms/src/samples/algorith/C20VEBTree.ts

运行结果

1.[运行结果]

参考

/van-emde-boas-tree-set-1-basics-and-construction/?ref=lbp