veb：算法导论 van Emde Boas 树 2024-04-25 23:04:45 0 0 算法导论 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.https://gitee.com/beimuaihui/LayaAir/blob/my_introduction_to_algorithms/src/samples/algorith/C20VEBTree.ts 运行结果 1.[运行结果] 参考https://www.geeksforgeeks.org/van-emde-boas-tree-set-1-basics-and-construction/?ref=lbp 收藏（0）