sorting - 如何获得b-tree的第n个值

Question

是否有通用伪代码或相关数据结构来获取b 树的第 n^个值？例如，这棵树的第八个值是 13 [1,4,9,9,11,11,12,13]。

如果我有一些在 b 树中排序的值，我想找到第 n^个值而不必遍历整个树。这个问题有更好的结构吗？数据顺序可以随时更新。

Answer 1

您正在寻找订单统计树。它的想法是除了存储在节点中的任何数据之外 - 还将子树的大小存储在节点中，并在插入和删除时保持更新。

由于您正在为每个插入/删除操作“触摸”O(logn)节点 - 使其保持最新状态仍然保持这些O(logn)行为。

FindKth()然后通过消除其较大索引仍小于 的子树k并检查下一个来完成。由于您不需要深入到每个子树的深度，只需直接到所需的子树（并检查该元素路径中的节点） - 您需要“触摸”O(logn)节点，这也可以进行此操作O(logn)。