Avec ' N ' no de nœuds, combien d'arbres de recherche binaires et binaires différents sont possibles?

1. Nombre Total des Arbres Binaires sont =

2. La somme de i donne le nombre total d'arbres de recherche binaires avec n nœuds.

Le cas de base est t (0) = 1 et t (1) = 1, c'est-à-dire qu'il y a une BST vide et une BST avec un nœud.

Donc, en général, vous pouvez calculer le nombre total d'arbres de recherche binaires en utilisant la formule ci-dessus. On m'a posé une question dans Google interview liée à cette formule. Question était combien total Non des arbres de recherche binaires sont possibles avec 6 sommets. Donc, la réponse est t (6) = 132

Je pense que je vous ai donné une idée...

Le nombre d'arbres binaires peut être calculé en utilisant le Nombre catalan .

Le nombre d'arbres de recherche binaires peut être considéré comme une solution récursive. c'est à dire, le Nombre d'arbres binaires = (Nombre de Gauche binaire de recherche sous-arbres) * (Nombre de Droit binaire de recherche sous-arbres) * (Façons de choisir la racine)

Dans une BST, seul l'ordre relatif entre les éléments compte. Ainsi, sans aucune perte de généralité, nous pouvons supposer les éléments distincts dans le les arbres sont 1, 2, 3, 4, ...., n . De plus, laissez le nombre DE BST être représenté par f(n) pour n éléments .

Maintenant, nous avons les cas multiples pour choisir la racine.

1. choisissez 1 comme racine, aucun élément ne peut être inséré dans le sous-arbre de gauche. n-1 les éléments seront insérés dans le sous-arbre de droite.
2. Choisissez 2 comme racine, 1 l'élément peut être inséré sur le sous-arbre gauche. n-2 les éléments peuvent être insérés à droite sous-arbre.
3. Choisissez 3 comme racine, 2 l'élément peut être inséré sur le sous-arbre gauche. n-3 les éléments peuvent être insérés dans le sous-arbre de droite.

...... De même, pour les i-ème élément comme la racine, i-1 éléments peuvent être sur la gauche et n-i, sur la droite.

Ces sous-arbres sont eux-mêmes BST, ainsi, nous pouvons résumer la formule comme:

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

Cas de Base, f (0) = 1, car il y a exactement 1 moyen de faire un BST avec 0 nœuds. f (1) = 1, car il y a exactement 1 moyen de faire un BST avec 1 Nœud.

Si non. des nœuds sont alors N.

Différent Non. DE BST = Catalan(n)
Différents Pas. des arbres binaires structurellement différents sont = Catalan(n)

Différent Non. des arbres binaires sont=N!* Catalan (N)

Eric Lippert a récemment eu une série très approfondie de messages de blog à ce sujet: " chaque arbre binaire Il y a" et "chaque arbre il y a" (plus un peu plus après cela).

En réponse à votre question spécifique, il dit:

Le nombre d'arbres binaires avec n nœuds est donné par les nombres catalans, qui ont de nombreuses propriétés intéressantes. Le nième nombre Catalan est déterminé par la formule (2n)! /(n+1)!n!, qui croît de façon exponentielle.

Arbres binaires différents avec n nœuds:

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

Où c = combinaison par exemple.

n=6,
possible binary trees=(1/7)*(12C6)=132

(2n)!/n!*(n+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

Arbre Binaire :

Pas besoin de considérer les valeurs, nous devons regarder la structrue.

Donnée par (2 puissance n) - n

Par exemple: pour trois nœuds, c'est (2 Puissance 3) -3 = 8-3 = 5 structures différentes

Arbre de recherche binaire:

, Nous devons considérer même les valeurs de nœud. Nous l'appelons comme numéro Catalan

Donnée par 2n C n / n+1

La bonne réponse devrait être 2nCn / (n+1) pour les nœuds non étiquetés et si les nœuds sont étiquetés alors (2nCn)*n!/(n + 1) .