如何获得b树的第n个值
How to get the n-th value of a b-tree
是否有通用伪代码或相关数据结构来获取b树的第nth个值？比如这棵树的第八个值是13[1,4,9,9,11,11,12,13]。
如果我有一些值在 b 树中排序，我想找到第 nth 个值，而不必遍历整个树。这个问题有更好的结构吗？数据顺序随时更新
您正在寻找 order statistics tree。它的想法是，除了存储在节点中的任何数据之外——还存储节点中子树的大小，并在插入和删除时保持更新。
由于您是每个 insert/delete 操作的 "touching" O(logn) 个节点 - 保持更新仍然保持这些 O(logn) 的行为。
FindKth() 然后通过消除其较大索引仍然小于 k 的子树并检查下一个来完成。由于您不需要进入每个子树的深度，只需直接进入所需的子树（并检查该元素路径中的节点） - 您需要 "touch" O(logn) 个节点，也进行此操作 O(logn)。
是否有通用伪代码或相关数据结构来获取b树的第nth个值？比如这棵树的第八个值是13[1,4,9,9,11,11,12,13]。
如果我有一些值在 b 树中排序，我想找到第 nth 个值，而不必遍历整个树。这个问题有更好的结构吗？数据顺序随时更新
您正在寻找 order statistics tree。它的想法是，除了存储在节点中的任何数据之外——还存储节点中子树的大小，并在插入和删除时保持更新。
由于您是每个 insert/delete 操作的 "touching" O(logn) 个节点 - 保持更新仍然保持这些 O(logn) 的行为。
FindKth() 然后通过消除其较大索引仍然小于 k 的子树并检查下一个来完成。由于您不需要进入每个子树的深度，只需直接进入所需的子树（并检查该元素路径中的节点） - 您需要 "touch" O(logn) 个节点，也进行此操作 O(logn)。