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

Pour les arbres binaires: Il N'est pas nécessaire de considérer les valeurs des nœuds d'arbre, Je ne m'intéresse qu'aux différentes topologies d'arbre avec des nœuds 'N'.

Pour L'Arbre de recherche binaire: nous devons considérer les valeurs de nœud d'arbre.

62
demandé sur Guy Coder 2010-06-15 07:51:08

10 réponses

Je recommande Cet article de mon collègue Nick Parlante (de retour quand il était encore à Stanford). Le nombre d'arbres binaires structurellement différents (problème 12) a une solution récursive simple (qui sous forme fermée finit par être la formule catalane que la réponse de @codeka a déjà mentionnée).

Je ne sais pas comment le nombre d'arbres binaires structurellement différents search (BSTs pour faire court) différerait de celui des arbres binaires "simples" - sauf que, si par "considérez les valeurs de nœud d'arbre" vous voulez dire que chaque nœud peut être par exemple n'importe quel nombre compatible avec la condition BST, puis le nombre de différents (mais pas tous structurellement différents!-) Techniciennes se chargent est infini. Je doute que vous vouliez dire cela, alors, veuillez clarifier ce que vousFaites avec un exemple!

35
répondu Alex Martelli 2010-06-15 04:02:45
  1. Nombre Total des Arbres Binaires sont = entrez la description de l'image![entrez la description de l'image ici

  2. La somme de i donne le nombre total d'arbres de recherche binaires avec n nœuds. entrez la description de l'image ici

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. entrez la description de l'image ici

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...

66
répondu Black_Rider 2012-10-17 15:53:06

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.

La Formule Finale

22
répondu chirag1992m 2014-07-02 15:08:55

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)

10
répondu Atiq 2013-10-20 11:55:14

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.

9
répondu Dean Harding 2010-06-15 03:56:47

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
5
répondu Sarang 2011-10-13 21:09:57
(2n)!/n!*(n+1)!
4
répondu karthik 2011-11-24 05:44:23
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
1
répondu Vinayak 2012-07-07 13:44:46

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

-1
répondu Maheedhar Pamuru 2014-08-18 17:45:56

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) .

-1
répondu HIRAK MONDAL 2018-08-22 13:17:37