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

[Oathbinder]

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

[whileFalse]

我感觉你对时间复杂度有误解……

[linxiaoziruo]

二叉平衡树存储文本，key 是行号，value 是行文本。对某行进行操作，找到这行的节点，删除一行就是这个节点的右子树的 key 都减 1，增加一行就是这个节点的右子树的 key 都加 1。这个操作的时间复杂度是 O(n)。说明肯定不能用平衡二叉树解决这个算法问题。也有可能真的是重新设计一下二叉树的 key 可以解决。。。。胡言乱语一大堆，还是没想到解决办法。

[GeruzoniAnsasu]

。。更新行号这个行为已经必定是线性的，除非每次插入时不更新所有行号

这样的话大概需要一个表记录从某行之后的所有行号进行了怎样的偏移，然后在合适的时间一次过全部更新，尽可能减少 O(n)遍历所有元素的次数让复杂度逼近 logn

[Oathbinder]

@whileFalse 有什么误解？
@linxiaoziruo
@GeruzoniAnsasu key 不一定是行号，但是我觉得这个要求本身就自相矛盾不可能实现，还是给教授发邮件吧

[yanaraika]

每个 node 存储子树有多少个节点。find 第 k 行二分严格 O(logn)

[yanaraika]

不需要存储行号作为 key。只要保证第 K 行是树的第 K 个节点就行了

[siyemiaokube]

实验室环境下很多平衡树都能解决这个问题，但是高效的代价就是一旦出问题难以挽救。
举个例子，最简单的实现：更新 key 时，可以不去线性的依次更新，而只需要在一些子树的根节点打上标记，查询至此时再下放标记。

[siyemiaokube]

如果只是算法题的话，这个问题很简单。。
大概是叫做“ lazy-tag ”思想吧，什么平衡树都行，这年头随便一个高中生都会写。。。

[siyemiaokube]

6#说的也对，可以根本不去维护 key 值，每次查询也是 logn 级别