V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Oathbinder
V2EX  ›  算法

如何设计一个二叉平衡树的 key

  •  
  •   Oathbinder · 2019-01-29 10:19:35 +08:00 · 2886 次点击
    这是一个创建于 1885 天前的主题,其中的信息可能已经有所发展或是发生改变。

    用一个二叉平衡树按行存储文本,一个行号对应一行内容,给定一个行号即可获取该行内容并且可以在任意行前插入一行或删除一行,要求插入和删除操作的复杂度为 O(logn)。如果没有复杂度的要求这事很简单,key 是行号 value 是该行内容,但是这样的话每次插入和删除都要把这行之后的 key 全更新一遍,那么复杂度肯定高于 O(logn)。所以说这个问题的关键就在于如何设计一个 key 能够让二叉树的增删改查的复杂度为 O(logn)。

    9 条回复    2019-01-29 14:02:45 +08:00
    whileFalse
        1
    whileFalse  
       2019-01-29 10:29:43 +08:00
    我感觉你对时间复杂度有误解……
    linxiaoziruo
        2
    linxiaoziruo  
       2019-01-29 11:01:02 +08:00
    二叉平衡树存储文本,key 是行号,value 是行文本。对某行进行操作,找到这行的节点,删除一行就是这个节点的右子树的 key 都减 1,增加一行就是这个节点的右子树的 key 都加 1。这个操作的时间复杂度是 O(n)。说明肯定不能用平衡二叉树解决这个算法问题。也有可能真的是重新设计一下二叉树的 key 可以解决。。。。胡言乱语一大堆,还是没想到解决办法。
    GeruzoniAnsasu
        3
    GeruzoniAnsasu  
       2019-01-29 11:14:29 +08:00
    。。更新行号这个行为已经必定是线性的,除非每次插入时不更新所有行号

    这样的话大概需要一个表记录从某行之后的所有行号进行了怎样的偏移,然后在合适的时间一次过全部更新,尽可能减少 O(n)遍历所有元素的次数让复杂度逼近 logn
    Oathbinder
        4
    Oathbinder  
    OP
       2019-01-29 11:38:21 +08:00
    @whileFalse 有什么误解?
    @linxiaoziruo
    @GeruzoniAnsasu key 不一定是行号,但是我觉得这个要求本身就自相矛盾不可能实现,还是给教授发邮件吧
    yanaraika
        5
    yanaraika  
       2019-01-29 11:44:58 +08:00
    每个 node 存储子树有多少个节点。find 第 k 行二分严格 O(logn)
    yanaraika
        6
    yanaraika  
       2019-01-29 11:45:59 +08:00
    不需要存储行号作为 key。只要保证第 K 行是树的第 K 个节点就行了
    siyemiaokube
        7
    siyemiaokube  
       2019-01-29 13:56:24 +08:00 via iPhone
    实验室环境下很多平衡树都能解决这个问题,但是高效的代价就是一旦出问题难以挽救。
    举个例子,最简单的实现:更新 key 时,可以不去线性的依次更新,而只需要在一些子树的根节点打上标记,查询至此时再下放标记。
    siyemiaokube
        8
    siyemiaokube  
       2019-01-29 14:00:30 +08:00 via iPhone
    如果只是算法题的话,这个问题很简单。。
    大概是叫做“ lazy-tag ”思想吧,什么平衡树都行,这年头随便一个高中生都会写。。。
    siyemiaokube
        9
    siyemiaokube  
       2019-01-29 14:02:45 +08:00 via iPhone
    6#说的也对,可以根本不去维护 key 值,每次查询也是 logn 级别
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   950 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 21:21 · PVG 05:21 · LAX 14:21 · JFK 17:21
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.