如何获得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)节点，从而进行此操作[ C0]。