sorting - 如何获取b树的第n个值

Question

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

如果我在 b 树中排序了一些值，我希望找到第 n^th 值，而不必遍历整个树。对于这个问题有更好的结构吗？数据订单随时更新。

Answer 1

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

由于您为每个插入/删除操作“接触”O(logn) 节点 - 保持其最新仍然保持这些的 O(logn) 行为.

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