Avec ' N ' pas de nœuds, de la façon dont beaucoup de différents et Binaires Arbres Binaires possible?

Question

Pour les arbres Binaires: Vous n'avez besoin de considérer nœud de l'arborescence de valeurs, je suis intéressé sur les différentes topologies d'arbre à N nœuds.

Pour les Binaires de Recherche Arbres: de toute évidence, Nous considérons nœud de l'arborescence de valeurs.

Answer 1

1. Nombre Total des Arbres Binaires sont =

2. Sommation sur i donne le nombre total d'arbres binaires à n nœuds.

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

Ainsi, En général, vous pouvez calculer un montant total d'Arbres Binaires à l'aide de la formule ci-dessus. M'a posé une question dans Google entretien liées à la sur cette formule. La Question consistait à déterminer le nombre total d'Arbres Binaires sont possibles avec 6 sommets. Si la Réponse est t(6) = 132

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

Answer 2

Je recommande cet article de mon collègue Nick Parlante (à partir de l'époque où il était encore à l'université de Stanford). Le nombre de structures différentes d'arbres binaires (problème 12) a une simple solution récursive (qui, dans la forme fermée finit par être le Catalan formule @codeka la réponse déjà mentionné).

Je ne suis pas sûr de savoir comment le nombre de structures différentes binaires de recherche arbres (techniciennes se chargent, pour faire court) serait différente de celle de "la plaine" arbres binaires -- sauf que, si par "envisager l'arbre des valeurs de nœud" vous voulez dire que chaque nœud peut être par exemple un nombre quelconque compatible avec le BST, puis le nombre de différent (mais pas tous les structurellement différent!-) Techniciennes se chargent est infini. Je doute que vous dire que, oui, veuillez préciser ce que vous ne voulez dire par un exemple!

Answer 3

Le nombre d'arbres binaires peuvent être calculés en utilisant le catalan nombre.

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

Dans un BST, seul l'ordre relatif entre les éléments de la matière. Donc, sans aucune perte sur la généralité, nous pouvons supposer que les éléments distincts dans l'arbre sont 1, 2, 3, 4, ...., n. Aussi, laissez-le nombre de BST être représenté par f(n) pour n éléments.

Maintenant, nous avons plusieurs cas de choix de la racine.

1. choisissez 1 comme racine, aucun élément peut être inséré sur la gauche du sous-arbre. n-1 éléments seront insérés sur le droit de la sous-arborescence.
2. Choisissez 2 en tant que root, 1 élément peut être inséré sur la gauche du sous-arbre. n-2 éléments peuvent être insérés sur le droit de la sous-arborescence.
3. Choisissez 3 en tant que root, 2 élément peut être inséré sur la gauche du sous-arbre. n-3 éléments peuvent être insérés sur le droit de la sous-arborescence.

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

Ces sous-arbres sont elle-même de la STB, ainsi, nous pouvons résumer la formule:

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

De la Base de cas, f(0) = 1, il y a exactement 1 façon de faire un BST avec 0 nœuds. f(1) = 1, il y a exactement 1 façon de faire un BST avec 1 noeud.

Answer 4

Eric Lippert a récemment vécu une série de posts à ce sujet: "Chaque Arbre Binaire Il y a" et "Chaque Arbre Il y a" (plus quelques plus après).

En réponse à votre question, il dit:

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

Answer 5

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