23

一定数のキーまたは値 (配列または何らかのデータ構造に格納されている) と B ツリーの順序が与えられた場合、スペース効率の良い B ツリーを生成するキーの挿入シーケンスを決定できます。

説明のために、次数 3 の b ツリーを考えます。キーを {1,2,3,4,5,6,7} とします。次の順序で要素をツリーに挿入する

for(int i=1 ;i<8; ++i)
{
 tree.push(i);  
}

このようなツリーを作成します

        4
     2      6
   1  3   5   7

http://en.wikipedia.org/wiki/B-treeを参照

しかし、この方法で要素を挿入する

flag = true;
for(int i=1,j=7; i<8; ++i,--j)
{
    if(flag)
    {
        tree.push(i);
        flag = false;
    }
    else
    {
        tree.push(j);
        flag = true;
    }   
}

このようなツリーを作成します

    3 5
1 2  4  6 7

レベルの低下が見られます。

では、スペース消費を削減する挿入シーケンスを決定する特定の方法はありますか?

4

5 に答える 5

6

これは、要素を b ツリーに追加する方法です。

Steve314 に感謝します。バイナリ表現から始めてくれました。

順番に追加する n 個の要素が与えられます。これを m 次の b ツリーに追加する必要があります。それらのインデックス (1...n) を基数 m に変換します。この挿入の主なアイデアは、現在最高の m 基数ビットを持つ数値を挿入し、ノードの分割にもかかわらず、ツリーに追加されたより小さい m 基数より上に保持することです。

1,2,3.. はインデックスなので、それらが指す数字を実際に挿入します。

For example, order-4 tree
      4       8         12           highest radix bit numbers
1,2,3   5,6,7   9,10,11    13,14,15

注文の中央値に応じて、次のようになります。

  • 順序が偶数 -> キーの数が奇数 -> 中央値が中間 (mid median)
  • 順序が奇数 -> キーの数が偶数 -> 左中央値または右中央値

プロモートする中央値 (左/右) の選択によって、要素を挿入する順序が決まります。これは、b ツリーで修正する必要があります。

バケット内のツリーに要素を追加します。最初にバケット要素を追加し、完了したら次のバケットを順番に追加します。メジアンがわかっている場合、バケットは簡単に作成できます。バケット サイズは次数 m です。

I take left median for promotion. Choosing bucket for insertion.
    |  4     |  8      |   12       |    
1,2,|3   5,6,|7   9,10,|11    13,14,|15  
        3       2          1             Order to insert buckets.
  • 左中央値を選択した場合は、右側からツリーにバケットを挿入し、右中央値を選択した場合は、左側からバケットを挿入します。左中央値を選択すると、最初に中央値が挿入され、次にその左側の要素が最初に挿入され、次にバケット内の残りの数値が挿入されます。

例

Bucket median first
12,
Add elements to left
11,12,
Then after all elements inserted it looks like,
|   12       | 
|11    13,14,| 
Then I choose the bucket left to it. And repeat the same process.
Median
     12        
8,11    13,14, 
Add elements to left first
       12        
7,8,11    13,14, 
Adding rest
  8      |   12        
7   9,10,|11    13,14, 
Similarly keep adding all the numbers,
  4     |  8      |   12        
3   5,6,|7   9,10,|11    13,14, 
At the end add numbers left out from buckets.
    |  4     |  8      |   12       |   
1,2,|3   5,6,|7   9,10,|11    13,14,|15

  • 中間中央値 (順序 B ツリーでも) の場合は、単純に中央値を挿入してから、バケット内のすべての数値を挿入します。

  • 右中央値の場合、左からバケットを追加します。バケット内の要素については、最初に中央値を挿入し、次に右要素、次に左要素を挿入します。

ここでは、最大の m 基数を追加しています。その過程で、m 基数のすぐ下のビットで数値を追加し、最大の m 基数が一番上にくるようにしました。ここでは 2 つのレベルしかありません。それ以上のレベルについては、基数ビットの降順で同じプロセスを繰り返します。

最後のケースは、残りの要素が同じ基数ビットであり、基数ビットが小さい数字がない場合です。単純にそれらを挿入して手順を終了します。

3 つのレベルの例を示しますが、長すぎて表示できません。したがって、他のパラメーターを試して、それが機能するかどうかを確認してください。

于 2013-05-20T05:34:18.327 に答える
1

では、スペース消費を削減する挿入シーケンスを決定する特定の方法はありますか?

編集注：質問は非常に興味深いものだったので、Haskellを少し使って答えを改善しようとしています。

Bツリーkのクヌース次数とlistキーのリストを

スペース消費の最小化には、簡単な解決策があります。

-- won't use point free notation to ease haskell newbies
trivial k list = concat $ reverse $ chunksOf (k-1) $ sort list

このようなアルゴリズムは、時間効率の悪いB ツリーを効率的に生成し、左側がアンバランスですが、スペースの消費は最小限に抑えます。

生成するのは効率的ではありませんが、ルックアップのパフォーマンスが向上する (高さ/深さが低い) 重要なソリューションが多数存在します。ご存知のように、すべてはトレードオフです。

B ツリーの深さとスペース消費の両方を最小化する単純なアルゴリズムは次のとおりです (ただし、ルックアップのパフォーマンスは最小化されません!)。

-- Sort the list in increasing order and call sortByBTreeSpaceConsumption 
-- with the result
smart k list = sortByBTreeSpaceConsumption k $ sort list

-- Sort list so that inserting in a B-Tree with Knuth order = k 
-- will produce a B-Tree  with minimal space consumption minimal depth 
-- (but not best performance)
sortByBTreeSpaceConsumption :: Ord a => Int -> [a] -> [a]
sortByBTreeSpaceConsumption _ [] = []
sortByBTreeSpaceConsumption k list
    | k - 1 >= numOfItems = list  -- this will be a leaf
    | otherwise = heads ++ tails ++ sortByBTreeSpaceConsumption k remainder
    where requiredLayers = minNumberOfLayersToArrange k list
          numOfItems = length list
          capacityOfInnerLayers = capacityOfBTree k $ requiredLayers - 1
          blockSize = capacityOfInnerLayers + 1 
          blocks = chunksOf blockSize balanced
          heads = map last blocks
          tails = concat $ map (sortByBTreeSpaceConsumption k . init) blocks
          balanced = take (numOfItems - (mod numOfItems blockSize)) list
          remainder = drop (numOfItems - (mod numOfItems blockSize)) list

-- Capacity of a layer n in a B-Tree with Knuth order = k
layerCapacity k 0 = k - 1
layerCapacity k n = k * layerCapacity k (n - 1)

-- Infinite list of capacities of layers in a B-Tree with Knuth order = k
capacitiesOfLayers k = map (layerCapacity k) [0..]

-- Capacity of a B-Tree with Knut order = k and l layers
capacityOfBTree k l = sum $ take l $ capacitiesOfLayers k

-- Infinite list of capacities of B-Trees with Knuth order = k 
-- as the number of layers increases
capacitiesOfBTree k = map (capacityOfBTree k) [1..]

-- compute the minimum number of layers in a B-Tree of Knuth order k 
-- required to store the items in list
minNumberOfLayersToArrange k list = 1 + f k
    where numOfItems = length list
          f = length . takeWhile (< numOfItems) . capacitiesOfBTree

このsmart関数をlist = [21, 18, 16, 9, 12, 7, 6, 5, 1, 2]使用して、knuth order = 3 の a と B-Tree を指定すると、次[18, 5, 9, 1, 2, 6, 7, 12, 16, 21]のような結果の B-Tree を取得する必要があります。

              [18, 21]
             /
      [5 , 9]
     /   |   \
 [1,2] [6,7] [12, 16]

明らかに、これはパフォーマンスの観点からは最適ではありませんが、(次のような) より良いものを取得すると (計算上および経済的に) はるかにコストがかかるため、許容できるはずです。

          [7 , 16]
         /   |   \
     [5,6] [9,12] [18, 21]
    /
[1,2]

実行したい場合は、前のコードを Main.hs ファイルにコンパイルし、先頭に追加した後に ghc でコンパイルします。

import Data.List (sort)
import Data.List.Split
import System.Environment (getArgs)

main = do
    args <- getArgs
    let knuthOrder = read $ head args
    let keys = (map read $ tail args) :: [Int]
    putStr "smart: "
    putStrLn $ show $ smart knuthOrder keys
    putStr "trivial: "
    putStrLn $ show $ trivial knuthOrder keys
于 2013-05-22T02:17:11.707 に答える
1

残念ながら、すべてのツリーは最悪のシナリオの実行時間を示し、データがこのように昇順で入力される場合は厳密なバランス調整手法が必要です。二分木はすぐに連結リストなどに変わります。

典型的な B-Tree のユースケース (データベース、ファイルシステムなど) では、通常、データが自然により分散され、2 番目の例のようなツリーが生成されると期待できます。

それが本当に懸念される場合は、各キーをハッシュして、値のより広い分布を保証することができます.

for( i=1; i<8; ++i )
    tree.push(hash(i));
于 2013-05-13T06:25:41.843 に答える