21

多くのデータ構造は、 「左子、右兄弟」表現と呼ばれる表現を使用して、多元木を二分木として格納します。これは何を意味するのでしょうか？なぜそれを使うのですか？

4

1 に答える 1

77

左子、右兄弟表現（LCRS）は、二分木（各ノードができるツリー構造）を使用して、多元ツリー（各ノードが任意の数の子を持つことができるツリー構造）をエンコードする方法です。最大で2人の子供がいます）。

動機

この表現がどのように機能するかを動機付けるために、次のような単純な多方向ツリーを検討することから始めましょう。

                   A
                 //|\ \
               / / | \  \
              B C  D  E  F
              |   /|\   / \
              G  H I J K   L

（低品質のASCIIアートワークについてお詫びします！）

このツリー構造では、ツリー内の任意のノードからその子のいずれかに下向きにナビゲートできます。たとえば、AからB、AからC、AからDなどに移行できます。

このようなツリーでノードを表現したい場合は、通常、ここでこのようなノード構造/ノードクラスを使用します（C ++で記述）。

struct Node {
    DataType value;
    std::vector<Node*> children;
};

LCRS表現では、各ノードが最大2つのポインターを必要とする方法で多方向ツリーを表現します。これを行うために、ツリーの形状を少し変更します。ツリー内の各ノードにすべての子へのポインターを格納させるのではなく、各ノードにその子の1つ（LCRSでは左端の子）へのポインターのみを格納させることにより、ツリーを少し異なる方法で構造化します。次に、各ノードに、同じ親ノードの子であるツリー内の次のノードである、その右の兄弟へのポインターを格納させます。上記のツリーの場合、次のようにツリーを表すことができます。

            A
           /
          /
         /
        B -> C -> D -> E -> F
       /         /         /
      G         H->I->J   K->L

この新しい構造では、親ノードからそのk番目の子（ゼロインデックス）にナビゲートすることが引き続き可能であることに注意してください。そのための手順は次のとおりです。

  • 現在のノードの左側の子に降ります。（これは、その子のリストの最初のノードです）。
  • その子の右の兄弟ポインターをk回たどります。（これにより、ノードのk番目の子に移動します）。
  • そのノードを返します。

たとえば、ルートノードAの3番目（インデックスがゼロの子）を見つけるには、左端の子（B）に降りてから、3つの右リンク（B、C、D、最後にEにアクセス）をたどります。次に、ノードAの3番目の子を保持するEのノードに到達します。

ツリーをこのように表現する主な理由は、どのノードにも任意の数の子が存在する場合でも、表現には各ノードに最大2つのポインターが必要であるためです。1つは左端の子を格納し、もう1つは右の兄弟を格納します。その結果、はるかに単純なノード構造を使用してマルチウェイツリーを格納できます。

struct Node {
    DataType data;
    Node* leftChild;
    Node* rightSibling;
};

このノード構造は、バイナリツリー内のノードとまったく同じ形状です（データと2つのポインター）。その結果、LCRS表現により、ノードごとに2つのポインターを使用するだけで、任意の多方向ツリーを表現できます。

分析

ここで、マルチウェイツリーの2つの異なる表現の時間と空間の複雑さと、その上でのいくつかの基本的な操作を見てみましょう。

最初の「子の動的配列」表現に必要な合計スペース使用量を確認することから始めましょう。nノードツリーの合計メモリ使用量はどれくらいになりますか？さて、私たちは次のことを知っています：

  1. 各ノードは、子の数に関係なく、格納されている生データ用のスペース（sizeof（data））と動的配列のスペースオーバーヘッドに貢献します。動的配列には、（通常）1つのポインター（割り当てられた配列を指す）、動的配列の要素の総数を表す1つのマシンワード、および（オプションで）配列の割り当てられた容量を表す1つのマシンワードが格納されます。これは、各ノードがsizeof（Data）+ sizeof（Node *）+ 2 * sizeof（machine word）スペースを占めることを意味します。

  2. ツリー内のn個のノードには親があるため、ツリー内のすべての動的配列全体で、子へのn-1個のポインターがあります。これにより、余分な（n --1）* sizeof（Node *）係数が追加されます。

したがって、総スペース使用量は

n・（sizeof（Data）+ sizeof（Node *）+ 2 * sizeof（machine word））+（n --1）* sizeof（Node *）

= n * sizeof（Data）+（2n --1）* sizeof（Node *）+ 2n * sizeof（machine word）

それでは、LCRSツリーと対比してみましょう。LCRSツリーの各ノードは2つのポインター（2 * sizeof（Node *））と1つのデータ要素（sizeof（Data））を格納するため、その合計スペースは次のようになります。

n * sizeof（Data）+ 2n * sizeof（Node *）

そして、ここで勝利が見られます。割り当てられた配列サイズを追跡するために、2n * sizeof（マシンワード）の追加メモリを格納していないことに注意してください。これは、LCRS表現が通常のマルチウェイツリーよりもかなり少ないメモリを使用することを意味します。

ただし、LCRSツリー構造での基本的な操作は、通常のマルチウェイツリーでの対応する操作よりも時間がかかる傾向があります。具体的には、標準形式で表される多方向ツリー（各ノードは子ポインターの配列を格納します）では、1つのノードからそのk番目の子にナビゲートするのに必要な時間は、単一のポインターをたどるのに必要な時間で与えられます。一方、LCRS表現では、これを行うために必要な時間は、k + 1個のポインター（1個の左の子ポインター、次にk個の右の子ポインター）をたどるのに必要な時間によって与えられます。その結果、ツリーの分岐係数が大きい場合、LCRSツリー構造でのルックアップの実行は、対応するマルチウェイツリー構造よりもはるかに遅くなる可能性があります。

したがって、LCRS表現は、データ構造のストレージスペースとアクセス時間の間の時間とスペースのトレードオフを提供するものと考えることができます。LCRS表現では、元のマルチウェイツリーよりもメモリのオーバーヘッドが少なくなりますが、マルチウェイツリーでは、各子の一定時間のルックアップが提供されます。

ユースケース

LCRS表現には時空間のトレードオフが伴うため、LCRS表現は通常、次の2つの基準のいずれかが当てはまらない限り使用されません。

  1. 記憶が非常に少ない、または
  2. ノードの子へのランダムアクセスは必要ありません。

ケース（1）は、驚くほど巨大なマルチウェイツリーをメインメモリに格納する必要がある場合に発生する可能性があります。たとえば、頻繁に更新される多くの異なる種を含む系統樹を保存する必要がある場合は、LCRS表現が適切な場合があります。

ケース（2）は、ツリー構造が非常に特殊な方法で使用されている特殊なデータ構造で発生します。たとえば、マルチウェイツリーを使用する多くのタイプのヒープデータ構造は、LCRS表現を使用してスペースを最適化できます。これの主な理由は、ヒープデータ構造では、最も一般的な操作は次のようになる傾向があることです。

  1. ツリーのルートを削除して、その子のそれぞれを処理するか、または
  2. 一方のツリーをもう一方の子にすることで、2つのツリーを結合します。

操作（1）は、LCRS表現で非常に効率的に実行できます。LCRS表現では、ツリーのルートに正しい子が存在することはありません（兄弟がないため）。したがって、ルートを削除するということは、ルートノードを切り離して、左側のサブツリーに降りることを意味します。そこから、残りのツリーの右の背骨を歩いて各ノードを順番に処理するだけで、各子の処理を実行できます。

操作（2）も非常に効率的に実行できます。上記から、LCRS表現では、ツリーのルートに正しい子がないことを思い出してください。したがって、次のように、LCRS表現で2つのツリーを結合するのは非常に簡単です。このような2本の木から始めます。

    R1             R2
   /               /
 (children 1)    (children 2)

このようにして、木を融合させることができます。

             R1
            /
           R2
          /  \
(children 2) (children 1)

これはO（1）時間で実行でき、非常に簡単です。LCRS表現にこのプロパティがあるという事実は、二項ヒープやランクペアリングヒープなど、多くの種類のヒープ優先度キューが通常LCRSツリーとして表されることを意味します。

お役に立てれば！

于 2012-12-23T23:30:46.947 に答える