前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一种插入、查找后继节点耗时为 lglgu 的算法van Emde Boas Trees

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

作者头像
爬蜥
发布2019-07-09 16:02:12
5420
发布2019-07-09 16:02:12
举报
文章被收录于专栏:爬蜥的学习之旅

前提

假设总共有n个int元素,它的值在 {0,1,..,u-1}范围内,可以做到插入、删除、后继节点耗时为 lglgu 。

lglgu 在什么样的场景下才会出现?

如何使得u的存储和删除是常量时间?

使用数组存储所有的元素,数组的index就是要存储的n的值,数组u的值为0,表示当前值没有,1,表示有,这种结构为Bit Vector,如下:

上示中,u=16,目前存储的元素为 {1,9,10,15}

此时,存储和删除的时间都是O(1),查找后继节点的时间为O(u)

在bit vector的基础上,如何加快后继节点的查找速度?

每个cluster的树的构建规则是根据每个值之间的或得到的结果,那么要查找对应的值是否存在,只需要看当前的cluster树的顶点是不是1即可

给每个cluster的树取名为summary

对于构建的树,新插入的元素值在u中的坐标可表示为

i表示在那个cluster,j表示在cluster中的位置,取函数 high(x)=i,low(x)=j

总的耗时时间并不好,再次优化结构

插入

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

它的耗时为

可得,T(u)=O(lgu),没有达到预期的效果

查找后继

代码语言:javascript
复制
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)
复制代码
T(u)=O((lgu)^{lg3})
T(u)=O((lgu)^{lg3})

总的耗时时间并不好,再次优化结构

在查找后继节点的过程中,如果当前的cluster不存在值,就找下一个cluster的元素j=Successor(V.cluster[i],Integer.MIN_VALUE),而根据后继节点的性质,当保存了每个cluster的最小元素的时候,这次查找就可以干掉。 其次,cluster查找的时候,如果能够立马知道,是否能够在当前cluster找到元素,那么就能决定,到底是找当前的clusterj=Successor(V.cluster[i],low(x))还是在下一个i=Successor(V.summary,i),当存储了每个cluster的max元素的下标的时候,如果low(x)<max显然就在当前cluster,否则就是下一个,这样只需要执行1次Successor

代码语言:javascript
复制
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)
复制代码

它的耗时为

T(u)=T(\sqrt u)+O(1)
T(u)=T(\sqrt u)+O(1)

即T(u)=O(lglgu)

插入方式优化

代码语言:javascript
复制
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中插入元素
复制代码

当第一次调用去更新summary的时候,V.cluster[high(x)]肯定是没有值的,那么第二次调用 Insert(V.cluster[high(x)],low(x))的时候,只会执行V.min == None

这里只在V.min中存储了最小值 它的时间为 O(lglgu)

删除实际在这种方式下,它的耗时也是O(lglgu)

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年08月19日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前提
    • lglgu 在什么样的场景下才会出现?
    • 如何使得u的存储和删除是常量时间?
    • 在bit vector的基础上,如何加快后继节点的查找速度?
    • 总的耗时时间并不好,再次优化结构
      • 插入
        • 查找后继
        • 总的耗时时间并不好,再次优化结构
          • 插入方式优化
          相关产品与服务
          对象存储
          对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档