3

3〜4個の構成（3個の要素と4個のポインター）のノードを持つBツリーがあるとします。ルールに従って合法的にツリーを構築すると仮定すると、レイヤーに2つのノードがあり、1つのノードに4つの終了ポインターがあり、もう1つのノードに2つの終了ポインターしかない状況に到達することは可能ですか？

一般的に、適切に使用されたBツリーのバランスに関して私はどのような保証がありますか

4

1 に答える 1

11

バランス（一般的にバランスの取れたツリーデータ構造）の背後にある考え方は、任意の2つのサブツリー間の深さの差が0または1（ツリーに応じて）であるということです。つまり、リーフノードを見つけるために使用される比較の数は常に同じです。

そうです、単に深さが同じであるという理由だけで、あなたはあなたが説明する状況に陥ることができます。各ノードの要素の数は、バランスには関係ありません（ただし、以下を参照してください）。

左側のノードに右側よりも多くの項目がある場合でも、これは完全に合法です（nullポインターは表示されません）。

                 +---+---+---+
                 | 8 |   |   |
                 +---+---+---+
        ________/    |
       /             |
      |              |
+---+---+---+  +---+---+---+
| 1 | 2 | 3 |  | 9 |   |   |
+---+---+---+  +---+---+---+

ただし、3〜4個のBTreeがあることは非常に珍しいことです（実際には、これはBTreeではなく、他のデータ構造であると言う人もいます）。

BTreeを使用すると、通常、各ノードに最大で偶数のキーがあり（たとえば、4〜5ツリー）、分割と結合が容易になります。4〜5のツリーを使用すると、ノードがいっぱいになったときにどのキーを昇格させるかを簡単に決定できます。これは5つの中の1つです。これは、2つのうちの1つである可能性があるため、3-4ツリーではそれほど明確な問題ではありません（4つの要素の明確な中間はありません）。

nまた、ノードに要素と要素の間に含める必要があるルールに従うこともできます2n。さらに（「適切な」BTreeの場合）、リーフノードは、互いに1つだけではなく、すべて同じ深さにあります。

空のBTreeに次の値を追加すると、次のような状況になる可能性があります。

Add           Tree Structure
---          ----------------
 1                  1

 2                 1,2

 5                1,2,5

 6               1,2,5,6

 7                  5
                   / \
                1,2   6,7

 8                  5
                   / \
                1,2   6,7,8

 9                  5
                   / \
                1,2   6,7,8,9
于 2010-10-17T04:55:05.860 に答える