18

私は、各ノードが約Nノードを持つLレベルの深さのツリーデータ構造を持っています。ツリー内のノードの総数を計算したい。これを行うには (私が思うに)、子を持つノードの割合を知る必要があります。

N における葉ノードと非葉ノードの比率の正しい用語はどれですか?

3 つのノードの総数を計算する式は何ですか?

更新誰かが答えの1つで分岐要因に言及しましたが、その後消えました。これは私が探していた用語だったと思います。では、式は分岐要因を考慮に入れるべきではないでしょうか?

更新正確な数値ではなく、架空のデータ構造についての見積もりを言うべきでした!

4

6 に答える 6

29

各ノードには約 N 個のサブノードがあり、ツリーの深さは L レベルです。

With 1 level, the tree has 1 node.
With 2 levels, the tree has 1 + N nodes.
With 3 levels, the tree has 1 + N + N^2 nodes.
With L levels, the tree has 1 + N + N^2 + ... + N^(L-1) nodes.

ノードの総数は (N^L-1) / (N-1) です。

わかりました、なぜそれが指数関数的であるかのほんの一例です：

                    [NODE]
                      |
                     /|\
                    / | \
                   /  |  \
                  /   |   \
            [NODE]  [NODE] [NODE]
              |
             /|\
            / | \
于 2009-02-05T10:17:31.220 に答える
1

ツリーがほぼ満杯の場合、つまり、最後の 2 つを除いてすべてのレベルに完全な子が含まれている場合、N^(L-2) と N^(L-1) の間に葉ノードがあり、N^(L -1) および N^L ノードの合計。

ツリーがいっぱいでない場合、完全にバランスの取れていないツリーには 1 つのリーフ ノードがありますが、任意の数の親があるため、リーフ ノードの数を知っていても役に立ちません。

「各ノードには約N個のノードがある」というあなたの声明がどれほど正確なのだろうか-平均分岐係数がわかっている場合、おそらくツリーの予想サイズを計算できます。

リーフと内部ノードの比率を見つけることができ、子の平均数がわかっている場合は、これを (n*ratio)^N = n として概算できます。これはあなたの答えにはなりませんが、私よりも数学が得意な人が、この方程式に L を挿入して、解けるものを与える方法を見つけられるのではないかと思います。

それでも、正確に知りたい場合は、ツリーの構造を繰り返し処理し、ノードをカウントする必要があります。

于 2009-02-05T10:20:27.593 に答える
1

深さ L のノードの量を計算する式は次のとおりです。(N 個のルート ノードがあると仮定)

N L

すべてのノードの数を計算するには、レイヤーごとにこれを行う必要があります。

for depth in (1..L)
    nodeCount += N ** depth

ルート ノードが 1 つしかない場合は、L から 1 を引き、ノードの総数に 1 を加えます。

1 つのノードで葉の量が平均的なケースと異なる場合、これは数に大きな影響を与える可能性があることに注意してください。ツリーの上位になるほど影響が大きくなります。

     * * * N ** 1
    *** *** *** N ** 2
*** *** *** *** *** *** *** *** *** N ** 3

これはコミュニティ ウィキなので、私の恐ろしい代数を自由に変更してください。

于 2009-02-05T10:00:29.210 に答える
0

ツリーの深さ以外に何も知らない場合、合計サイズを計算するための唯一のオプションは、それらを調べて数えることです。

于 2009-02-05T09:59:56.857 に答える