gpt4 book ai didi

c - 在 B 树中查找第 k 个键的算法?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:40:44 27 4
gpt4 key购买 nike

我试图了解我应该如何考虑获取 B 树中的第 k 个键/元素。即使它是步骤而不是代码,它仍然会有很大帮助。谢谢

编辑:为清楚起见,我要求 B 树中第 k 个最小的键。

最佳答案

没有使用标准 B 树的有效方法。一般来说,我看到 2 个选项:

  • 将 B 树转换为 order statistic tree 允许在 O(log n) 中进行此操作。

    也就是说,对于每个节点,保留一个变量来表示以该节点为根的子树(该节点、其所有子节点、其所有子节点的子节点等)的大小(元素数量)。

    无论何时进行插入或删除操作,都会相应地更新此变量。您只需要更新已经访问过的节点,因此不会改变这些操作的复杂性。

    获取第 k 个元素将涉及将子元素的大小相加,直到我们到达 k,选择合适的子元素进行访问并减少 k 适当。伪代码:

    select(root, k) // initial call for root

    // returns the k'th element of the elements in node
    function select(node, k)
    for i = 0 to t.elementCount
    size = 0
    if node.child[i] != null
    size = node.sizeOfChild[i]
    if k < size // element is in the child subtree
    return select(node.child[i], k)
    else if k == size // element is here
    && i != t.elementCount // only equal when k == elements in tree, i.e. k is not valid
    return t.element[i]
    else // k > size, element is to the right
    k -= size + 1 // child[i] subtree + t.element[i]
    return null // k > elements in tree

    考虑 child[i] 直接在 element[i] 的左边。

    Wikipedia 上提供的二叉搜索树(不是 B 树)的伪代码可以在这里比上面更好地解释基本概念。

    请注意,节点子树的大小应存储在其父节点中(请注意,我没有使用上面的 node.child[i].size)。将它存储在节点本身中效率会低得多,因为读取节点被认为是 B 树用例的重要或昂贵的操作(必须经常从磁盘读取节点),因此您希望最小化读取的节点数,即使这会使每个节点稍微大一些。

  • 做一个in-order traversal 直到您看到 k 个元素 - 这将花费 O(n)。

    伪代码:

    select(root, *k) // initial call for root

    // returns the k'th element of the elements in node
    function select(node, *k) // pass k by pointer, allowing global update
    if node == null
    return null
    for i = 0 to t.elementCount
    element = select(node.child[i], k) // check if it's in the child's subtree
    if element != null // element was found
    return element
    if i != t.elementCount // exclude last iteration
    if k == 0 // element is here
    return t.element[i]
    (*k)-- // only decrease k for t.element[i] (i.e. by 1),
    // k is decreased for node.child[i] in the recursive call
    return null

关于c - 在 B 树中查找第 k 个键的算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44231825/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com