Nombre de BST avec clés dupliquées - algorithme, maths, arbre, arbre de recherche binaire, programmation dynamique

S'il y a n sommet avec des clés distinctes que le nombre de BST donné par Numéro catalan. Mais si certains éléments sont dupliqués, comment pouvons-nous compter le nombre de BST?

Mon idée naïve que si nous avons k éléments égauxentre n, il faut diviser le nombre catalan sur k! (permutations de k éléments). Mais si nous le vérifions sur l'exemple le plus simple (BST construit sur [1, 1, 1]), nous réalisons que c'est une mauvaise idée.

Alors, comment devrions-nous prendre en compte les clés dupliquées lorsque nous comptons le nombre de BST?

Quelle est la BST dans ma question: arbre binaire où toutes les clés de l'enfant gauche sont inférieures à celles de la racine et dans l'enfant de droite toutes les clés sont égales ou égales à celles de la racine.

Réponses:

Les clés dupliquées ne font aucune différence pourle nombre d'arbres distincts. Chaque arbre a une forme distincte, vous n'avez donc même pas besoin des clés pour les différencier. Vous pouvez supprimer les clés tout à fait et les arbres seraient tous différents.

Essayez-le avec votre exemple simple: [1,1,1]. Vous pouvez toujours créer les 5 BST distincts avec ces touches:

    1      1      1      1      1
/      /      /             
1      1      1   1      1      1
/                       /        
1          1             1          1

EDIT pour les nouvelles exigences:

Si les enfants laissés doivent être strictement inférieurs àleurs parents, puis les clés en double forment une liste liée qui fonctionne comme un seul nœud, car vous ne pouvez pas avoir d'enfants à l'intérieur. La liste entière de valeurs égales n'aura qu'une seule forme, un enfant gauche et un enfant droit:

    1
/ 
0   1

1

2

Donc, dans ce cas, vous pouvez simplement soustraire le nombre de clés en double.

Pour N clés avec M doublons, c'est-à-dire N-M clés uniques, il existe des façons catalanes (N-M) de créer l'arborescence.