Gesamtanzahl der Knoten in einer Baumdatenstruktur?

Question

Ich habe eine Baumdatenstruktur, die L-Ebenen ist tief, jeder Knoten hat über N-Knoten. Ich möchte die Gesamtzahl der Knoten im Baum berechnen. Um dies zu tun (denke ich), muss ich wissen, wie viel Prozent der Knoten Kinder haben werden.

Wie lautet der korrekte Ausdruck für dieses Verhältnis von Blattknoten zu Nicht-Blattknoten in N?

Was ist die Formel für die Ausarbeitung der Gesamtzahl der Knoten in den drei?

aktualisieren Jemand erwähnt Faktor Branching in einen der Antwort, aber es verschwand. Ich denke, das war der Begriff, nach dem ich gesucht habe. Sollte also eine Formel den Verzweigungsfaktor nicht berücksichtigen?

Update Ich hätte eine Schätzung über eine hypothetische Datenstruktur, nicht die genaue Zahl sagen sollen!

Answer 1

Ok, jeder Knoten hat etwa N Unterknoten und der Baum ist L Ebenen tief.

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. 

Die Gesamtzahl der Knoten ist (N^L-1)/(N-1).

Ok, nur ein kleines Beispiel, warum ist es exponentiell:

    [NODE] 
         | 
        /|\ 
        /| \ 
       /| \ 
       / | \ 
      [NODE] [NODE] [NODE] 
       | 
      /|\ 
      /| \ 

Answer 2

Wenn Sie nichts anderes als die Tiefe des Baumes wissen, dann ist Ihre einzige Option für die Berechnung der Gesamtgröße, sie durchzugehen und zu zählen.

Answer 3

Die Formel für die Anzahl von Knoten in der Tiefe L Berechnung ist: (vorausgesetzt, dass es N Wurzelknoten sind)

N ^L

die Anzahl aller Knoten zu berechnen, man dies tun muss, für jede Schicht:

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

Wenn nur 1 Wurzelknoten ist, subtrahieren 1 von L und fügen Sie 1, um die Gesamtknotenpunkte zählen.

Beachten Sie, dass sich die Anzahl der Blätter in einem Knoten vom durchschnittlichen Fall unterscheidet, was sich auf Ihre Anzahl auswirken kann. Je weiter oben im Baum, desto mehr Auswirkungen.

Dies ist Community-Wiki, also fühlen Sie sich frei, meine entsetzliche Algebra zu ändern.

Answer 4

Wenn Ihr Baum etwa voll ist, dass jede Ebene ist seine volle Ergänzung der Kinder mit Ausnahme der letzten zwei, Sie dann haben zwischen N^(L-2) und N^(L-1) Blattknoten und zwischen N^(L-1) und N^L Knoten insgesamt.

Wenn Ihr Baum nicht voll ist, hilft die Kenntnis der Anzahl der Blattknoten nicht, da ein völlig unsymmetrischer Baum einen Blattknoten aber beliebig viele Elternknoten hat.

Ich frage mich, wie genau Ihre Aussage "jeder Knoten hat über N Knoten" ist - wenn Sie den durchschnittlichen Verzweigungsfaktor kennen, können Sie vielleicht die erwartete Größe des Baumes berechnen.

Wenn Sie das Verhältnis von Blättern zu internen Knoten finden, und Sie die durchschnittliche Anzahl der Kinder kennen, können Sie dies als (n * Verhältnis) annähern^N = n. Das wird dir deine Antwort nicht geben, aber ich frage mich, ob jemand mit besserer Mathematik als ich einen Weg finden kann, um L in diese Gleichung einzufügen und dir etwas lösliches zu geben.

Wenn Sie jedoch genau wissen wollen, müssen Sie über die Struktur des Baums iterieren und Knoten zählen, wie Sie gehen.

Answer 5

Nur um einen Tippfehler in der ersten Antwort zu korrigieren: die Gesamtzahl der Knoten für einen Baum der Tiefe L ist (N^(L + 1) -1)/(N-1) ... (das heißt, an die Macht L + 1 anstatt nur L).

Dies kann wie folgt dargestellt werden. Zuerst nimmt unseren Satz:

1 + N^1 + N^2 + ... + N^L = (N^(L + 1) -1)/(N-1)

Multiply beide Seiten von (N-1):

(N-1) (1 + N^1 + N^2 + ... + N^L) = N^(L + 1) -1.

die linke Seite auf:

N^1 + N 2 + N^^ 3 + ... + N^(L + 1) - 1 - N^1 - N^2 - ... - N^L.

Alle Terme N^1 bis N^L werden annulliert, was N^(L + 1) -1 ergibt. Dies ist unsere rechte Seite, also ist die ursprüngliche Gleichheit wahr.