B-Tree增强-order(k)函数，用于按排序顺序显示关键字排名

Question

我在数据结构作业中遇到了一个问题，我和我的同事都不知道，我们甚至不知道从哪里开始！

问题指出，我们应该建议增强B-树；函数顺序（k）-其中k是B-树中的一个键-将在O（logn）中显示键在B-树中所有键的排序顺序中的位置。我们还需要证明，"增强"不会影响B-树的正则抽象函数的复杂性。我们可以使用O（n）额外的空间，其中n是B-树中的键的数量。

进一步的解释：举一个B树为例，它有关键字a B C D E F G H I J K L M N。

• 订单（A）的结果应为"1"
• 订单（N）结果应为"14"
• 订单（I）结果应为"9"

到目前为止我已经明白了：

1. 假设我们被允许使用一个O（n）额外的空间，并且B-树正则空间是0（n），我们应该——可能——使用一个额外的B-树来获得帮助。

2. 事实上，他们提到，我们应该证明增强不会影响正则B树函数的复杂性，在某种程度上，我们必须以某种方式操纵正则抽象B树函数，以不影响它们的正则复杂性。

3. 事实上，我们必须在O（logn）中对（k）进行排序，这表明我们应该以基于高度的方式而不是逐节点的方式遍历B-树。

4. 在某个地方，我们可能必须检查给定的顺序为（k）的k是否真的存在于B-树中，我建议使用B-树的常规抽象搜索函数。

Answer 1

在每个键上，都应该存储额外的数据，记录该节点下有多少键（包括节点本身）。

为了保持这一点，insert（k）函数必须通过新键k的所有祖先返回，并递增它们的值。这将使插入O（logn）+O（logN），它仍然是O（logon），因此不会影响复杂性。delete（k）必须做同样的事情，只是递减值。平衡运营也必须考虑到这一点。

然后，order（k）将沿着树向下移动到k：每次它移动到一个节点时，它都应该将左侧的键数添加到总数中，并返回这个和。

编辑：我更改了节点和键之间"节点"的模糊性，因为它们在B-树中是不同的（一个节点可以包含多个键）。然而，该算法应该推广到大多数树数据结构。

这是B树的算法：

#In python-ish (untested psuedocode)
#root is the root of the tree
#Each node is expected to have an array named "keys",
# which contains the keys in the node.
#Each node is expected to have an array named "child_nodes",
# which contains the children of the node, if the node has children.
#If a node has children, this should be true: len(child_nodes) == len(keys) + 1
def inorder(q):
  order_count = 0
  current_node = root
  while True:
    #if q is after all keys in the node, then we will go to the last child node
    next_child_node_i = len(current_node.keys)
    #now see if q is in between any of the nodes
    #for each key-index in the keys array (ie. if the node contains 3 keys,
    # keyi will be in range [0-2] .)
    for keyi in range(len(current_node.keys)):
      #retrieve the value of the key, so we can do comparison
      current_key = current_node.keys[keyi]
      if current_key < q:
        #We are trying to find which child node to go down to next,
        # for now we will choose the child directly to the left of this key,
        #But we continue to look through the rest of the keys, to find which
        # two keys q lies in between.
        #before we continue, we should count this key in the order too:
        #if this is not a leaf node,
        if len(current_node.children) != 0:
          #retrieve the the recorded child count of the sub-tree
          order_count += current_node.children[keyi].recorded_descendant_key_count
        #add one for the key in this node that we are skipping.
        order_count += 1
        continue
      if q < current_key:
        #We found a key in the current node that is greater than q.
        #Thus we continue to the next level between this and the previous key.
        next_child_node_i = keyi
        break
      #we finally found q,
      if q == current_key:
        #now we just return the count
        return order_count
    #once we are here, we know which keys q lies between
    # (or if it belongs at the beginning or end), and thus which child to travel down to.
    #If this is a leaf node (it has no children),
    # then q was not found.
    if len(current_node.child_nodes) == 0:
      #Possible behaviors: throw exception, or just return the place in the order
      # where q *would* go, like so:
      return order
    #Travel down a level
    current_node = current_node.child_nodes[next_child_node_i]