Wie viele verschiedene binäre und binäre Suchbäume sind mit 'N' Anzahl der Knoten möglich?

74

Für Binärbäume: Es besteht keine Notwendigkeit, Baumknotenwerte zu berücksichtigen. Ich interessiere mich nur für verschiedene Baumtopologien mit 'N'-Knoten.

Für den binären Suchbaum : Wir müssen Baumknotenwerte berücksichtigen.

Siva
quelle

Antworten:

41

Ich empfehle diesen Artikel von meinem Kollegen Nick Parlante (von damals, als er noch in Stanford war). Die Zählung strukturell unterschiedlicher Binärbäume (Problem 12) hat eine einfache rekursive Lösung (die in geschlossener Form die katalanische Formel ist, die @ codekas Antwort bereits erwähnt hat).

Ich bin mir nicht sicher , wie die Anzahl der strukturell unterschiedliche binäre Suchbäume (BSTs kurz) von der „plain“ Binärbäumen unterscheiden würden - außer , dass, wenn sie von „Baumknotenwerte betrachten“ Sie bedeuten , dass jeder Knoten zB sein kann Jede Zahl, die mit der BST-Bedingung kompatibel ist, dann ist die Anzahl der verschiedenen (aber nicht alle strukturell unterschiedlichen! -) BSTs unendlich. Ich bezweifle, dass meine, ja, bitte klären , was Sie tun , mit einem Beispiel gemein!

Alex Martelli
quelle
1
Die hier bereitgestellte Lösung cslibrary.stanford.edu/110/BinaryTrees.html # 12 stimmt nicht mit der durch die katalanische Zahl berechneten Lösung überein. Das heißt, countTrees (4) sollte 5 sein, nicht 14, oder? Aber es gibt 14 zurück. (Dies ist die Serie 1, 1, 2, 5, 14, 42, 132)
Joyce
1
countTrees (4) ist das fünfte Element in der Serie, da die Serie bei 0 beginnt und
genau
78
  1. Die Gesamtzahl der Binärbäume beträgt = Bildbeschreibung eingeben! [Bildbeschreibung hier eingeben

  2. Die Summierung über i ergibt die Gesamtzahl der binären Suchbäume mit n Knoten. Geben Sie hier die Bildbeschreibung ein

Der Basisfall ist t (0) = 1 und t (1) = 1, dh es gibt eine leere BST und eine BST mit einem Knoten. Geben Sie hier die Bildbeschreibung ein

Im Allgemeinen können Sie also die Gesamtzahl der binären Suchbäume mithilfe der obigen Formel berechnen. Im Google- Interview wurde mir eine Frage zu dieser Formel gestellt. Die Frage war, wie viele binäre Suchbäume mit 6 Eckpunkten insgesamt möglich sind. Die Antwort lautet also t (6) = 132

Ich glaube, ich habe dir eine Idee gegeben ...

Schwarzer Reiter
quelle
6
Beachten Sie, dass 1 und 2 tatsächlich unterschiedliche Ausdrucksformen derselben Formel sind, keine Formeln für unterschiedliche Größen, falls dies nicht klar war.
Todd O'Bryan
1
@Black_Rider - Ich habe die obige Formel ausprobiert, um die Nr. Zu berechnen. von möglichen Bäumen für 100 eindeutige Knoten. Aber es scheitert. Ich habe DP verwendet, um das Problem zu lösen. Den Code finden Sie hier . Die Antwort ist falsch. Die erwartete Antwort lautet 25666077, aber die tatsächliche Ausgabe lautet 7159379471982673992. Können Sie mir dabei helfen?
Dany
Was ist, wenn einige Bäume die gleichen Schlüssel haben? Zum Beispiel ist es für Baum 1, 1, 2, 2 nicht möglich, ähnliche Schlüssel auf einen Scheitelpunkt zu drücken
Evgeny
36

Die Anzahl der Binärbäume kann anhand der katalanischen Zahl berechnet werden .

Die Anzahl der binären Suchbäume kann als rekursive Lösung angesehen werden. dh Anzahl der binären Suchbäume = (Anzahl der linken binären Suchunterbäume) * (Anzahl der rechten binären Suchunterbäume) * (Möglichkeiten zur Auswahl der Wurzel)

In einer BST spielt nur die relative Reihenfolge zwischen den Elementen eine Rolle. Ohne Verlust der Allgemeinheit können wir also annehmen, dass die verschiedenen Elemente im Baum 1, 2, 3, 4, ...., n sind . Es sei auch die Anzahl der BST durch f (n) für n Elemente dargestellt .

Jetzt haben wir mehrere Fälle für die Auswahl der Wurzel.

  1. Wählen Sie 1 als Wurzel, es kann kein Element in den linken Unterbaum eingefügt werden. n-1 Elemente werden in den rechten Unterbaum eingefügt.
  2. Wählen Sie 2 als Wurzel, 1 Element kann in den linken Unterbaum eingefügt werden. Im rechten Teilbaum können n-2 Elemente eingefügt werden.
  3. Wählen Sie 3 als Wurzel, 2 Elemente können in den linken Unterbaum eingefügt werden. n-3 Elemente können in den rechten Unterbaum eingefügt werden.

...... In ähnlicher Weise können für das i-te Element als Wurzel i-1 Elemente links und ni rechts sein.

Diese Unterbäume sind selbst BST, daher können wir die Formel wie folgt zusammenfassen:

f (n) = f (0) f (n-1) + f (1) f (n-2) + .......... + f (n-1) f (0)

Basisfälle, f (0) = 1, da es genau einen Weg gibt, eine BST mit 0 Knoten zu erstellen. f (1) = 1, da es genau 1 Möglichkeit gibt, eine BST mit 1 Knoten zu erstellen.

Endformel

chirag1992m
quelle
13

Wenn nein. von Knoten sind N Dann.

Unterschiedliche Anzahl von BST = Katalanisch (N)
Unterschiedliche Anzahl von strukturell unterschiedlichen Binärbäumen sind = Katalanisch (N)

Unterschiedliche Anzahl von Binärbäumen ist = N! * Katalanisch (N)

Atiq
quelle
10

Eric Lippert hatte kürzlich eine sehr ausführliche Reihe von Blog-Posts darüber: " Jeder Binärbaum gibt es " und " Jeder Baum gibt es " (plus einige weitere danach).

Als Antwort auf Ihre spezielle Frage sagt er:

Die Anzahl der Binärbäume mit n Knoten ergibt sich aus den katalanischen Zahlen , die viele interessante Eigenschaften haben. Die n-te katalanische Zahl wird durch die Formel (2n) bestimmt! / (n + 1)! n!, das exponentiell wächst.

Dean Harding
quelle
5

Verschiedene Binärbäume mit n Knoten:

(1/(n+1))*(2nCn)

wobei C = Kombination, z.

n=6,
possible binary trees=(1/7)*(12C6)=132
Sarang
quelle
4
(2n)!/n!*(n+1)!
karthik
quelle
1
The number of possible binary search tree with n nodes (elements,items) is

=(2n C n) / (n+1) = ( factorial (2n) / factorial (n) * factorial (2n - n) ) / ( n + 1 ) 

where 'n' is number of nodes  (elements,items ) 

Example :

for 
n=1 BST=1,
n=2 BST 2,
n=3 BST=5,
n=4 BST=14 etc
Vinayak
quelle
0

Die richtige Antwort sollte 2nCn / (n + 1) für unbeschriftete Knoten sein, und wenn die Knoten beschriftet sind, dann (2nCn) * n! / (N + 1) .

Turing101
quelle
-1

Binärbaum:

Wir müssen keine Werte berücksichtigen, sondern müssen uns die Struktur ansehen.

Gegeben durch (2 Potenzen n) - n

Beispiel: Für drei Knoten sind es (2 Potenzen 3) -3 = 8-3 = 5 verschiedene Strukturen

binärer Suchbaum:

Wir müssen sogar die Knotenwerte berücksichtigen. Wir nennen es als katalanische Nummer

Gegeben durch 2n C n / n + 1

Maheedhar Pamuru
quelle