Nombre de binaires de recherche arbres de plus de n éléments distincts

Combien d'arbres binaires peuvent être construits à partir de n éléments distincts? Et comment pouvons-nous trouver mathématiquement prouvé formule?

Exemple:
Si nous disposons de 3 éléments distincts, à savoir 1, 2, 3,
sont 5 arbres binaires.

Nombre de binaires de recherche arbres de plus de n éléments distincts

Probablement related.

OriginalL'auteur siddstuff | 2013-04-14

  1. 40

    Donnée de n éléments, le nombre d'arbres binaires qui peuvent être fabriqués à partir de ces éléments est donnée par la nième Catalan nombre (notée Cn). Ce qui est égal à

    Nombre de binaires de recherche arbres de plus de n éléments distincts

    Intuitivement, les nombres de Catalan représentent le nombre de façons que vous pouvez créer une structure de n éléments est faite de la manière suivante:

    • Ordre les éléments 1, 2, 3, ..., n.
    • Choisir l'un de ces éléments à utiliser comme un pivot de l'élément. Ceci divise les éléments restants en deux groupes: ceux qui viennent en amont de l'élément et ceux qui viennent après.
    • De manière récursive construire des structures à partir de ces deux groupes.
    • De combiner ces deux structures, ainsi que le seul élément que vous avez supprimées afin d'obtenir la structure finale.

    Ce modèle correspond parfaitement à la façon dont vous pouvez construire un BST à partir d'un ensemble de n éléments. Choisissez l'un des éléments à utiliser comme racine de l'arbre. Tous les petits éléments doivent aller vers la gauche, et tous les grands éléments doivent aller vers la droite. À partir de là, vous pouvez ensuite créer des petits techniciennes se chargent de les éléments à gauche et à droite, puis fusionner avec le nœud racine pour former un ensemble BST. Le nombre de façons que vous pouvez faire cela avec n éléments est donnée par Cn, et donc le nombre de techniciennes se chargent est donnée par la nième Catalan nombre.

    Espérons que cette aide!

    Par exemple pour les nœuds 10, 10, 10 le nombre d'arbres binaires est de 1. Mais le Catalan est 5. Mais si tous les éléments est différent, il est ok je pense.
    Le nombre de techniciennes se chargent reste encore 5 pour 10,10,10. La forme de l'arbre sera différent.

    OriginalL'auteur templatetypedef

  2. 9

    Je suis sûr que cette question n'est pas seulement de compter à l'aide d'une formule mathématique.. j'ai pris un certain temps et a écrit le programme et l'explication ou de l'idée à la base du calcul est le même.

    J'ai essayé de le résoudre avec la récursivité et de la programmation dynamique à la fois. Espérons que cette aide.

    La formule est déjà présent dans la réponse précédente:

    Donc, si vous êtes intéressé par l'apprentissage de la solution et la compréhension de la apporach vous pouvez toujours consulter mon article Le comte Arbres Binaires créés à partir de N éléments uniques

    OriginalL'auteur dharam

  3. 1

    Supposons que T(n) le nombre de techniciennes se chargent de n éléments.

    Donné n distincts ordonnée d'éléments, numérotés de 1 à n, nous sélectionnons j'ai comme la racine.

    Cette feuilles (1..i-1), à gauche dans le sous-arbre de T(i-1) combinaisons et (i+1..n) dans la bonne sous-arbre de T(n-i) combinaisons.

    Donc:

    T(n) = sum_i=1^n(T(i-1) * T(n-i))

    et T(1) = 1

    Il pourrait être bon de mentionner que cette récurrence résout à la nième Catalan nombre.
    Savez-vous comment tirer le catalan formule à partir de la somme que j'ai indiqué?
    Cette somme doit être exactement le nombre de triangulations d'un polygone sur n+2 nœuds, ce qui est la façon dont j'ai été présenté à des nombres de Catalan. Vous fixer un bord et de laisser le pivot se balader sur les autres n sommets, qui vous laisse avec deux polygones de tailles i-1 et n-i.
    Il s'avère que mon somme a un nom. Il est appelé "Segner la relation de récurrence". Un google pour que plus les nombres de catalan va révéler la dérivation.
    La preuve de ce que je sais (à l'aide de fonctions génératrices) est sur le site de Wikipedia. Il y a en fait plusieurs épreuves il en, qui sont toutes très bonnes.

    OriginalL'auteur Andrew Tomazos