3

データ構造の宿題で、私も同僚も理解できないという質問に遭遇しました。どこから始めればよいのかさえわかりません。

質問は、Bツリーの拡張を提案する必要があると述べています。関数order（k）-ここで、kはBツリーのキーです-O（log n）に、Bツリーのすべてのキーのソートされた順序でキーの位置を表示します。また、「拡張」がBツリーの通常の抽象関数の複雑さに影響を与えないことを示す必要があります。O（n）の余分なスペースを使用できます。ここで、nはBツリーのキーの数です。

詳細な説明：たとえば、キーABCDEFGHIJKLMNを持つBツリーを取り上げます。

  • order（A）の結果は「1」である必要があります。
  • order（N）の結果は「14」である必要があります。
  • order（I）の結果は「9」になります。

私がこれまでに理解したこと：

  1. O（n）の追加スペースの使用が許可されており、Bツリーの正則スペースがO（n）であることを考えると、おそらく、ヘルプのために追加のBツリーを使用する必要があります。

  2. 拡張が通常のBツリー関数の複雑さに影響を与えないことを示す必要があると彼らが述べたという事実は、ある時点で、影響を与えない方法で通常の抽象Bツリー関数を操作する必要がありますそれらの通常の複雑さ。

  3. O（log n）でorder（k）を実行する必要があるという事実は、ノードごとではなく、高さベースの方法でBツリーを通過する必要があることを示しています。

  4. どこかで、おそらく、order（k）の指定されたkが実際にBツリーに存在するかどうかを確認する必要があります。Bツリーの通常の抽象検索機能をお勧めします。

4

1 に答える 1

2

各キーには、そのノードの下にあるキーの数を記録する追加のデータを保存する必要があります（ノード自体を含む）。

これを維持するには、insert（k）関数は、新しいキーkのすべての祖先をさかのぼって移動し、それらの値をインクリメントする必要があります。これにより、挿入O（log n）+ O（log n）が作成されますが、これは引き続きO（log n）であるため、複雑さには影響しません。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]
于 2012-09-10T18:19:35.740 に答える