Computing Probabilité d'un STbr

Question

Salut à tous permet de dire que nous allons insérer A, B, C dans un STbr (Binary arbre de recherche) un ordre aléatoire, il y aurait 5 résultats

B 
A C 

A 
    B 
    C 

    C 
B 
A 

    C 
A 
B 

A 
    C 
B 

a) Quelle serait la probabilité d'obtenir ces arbres? b) Quelle serait la probabilité si nous avons ajouté un « D » et il ressemblait à ceci:

A 
B 
    C 
    D 

pire probabilité de cas? Merci pour votre temps!

Answer 1

La première chose à remarquer est que vous avez initialement 3 éléments.

Vous pouvez construire BST comme un processus récursif. Tout d'abord, vous sélectionnez la racine puis récursivement vous construisez les sous-arbres gauche et droit - les deux sont déterminés par la racine. Si vous avez n articles, la probabilité que vous en sélectionnez un comme racine de l'arbre est clairement 1/n (je suppose que aléatoire signifie uniformément aléatoire et indépendamment des choix précédents).

Bien sûr, si vous avez 1 élément ou 0 élément, il n'y a qu'un seul arbre possible, donc la probabilité de construire cet arbre est égale à 1.

Cas 1:

B 
A C 

Pr = Pr(select B as a root of a whole tree) 
    * Pr(tree consisting of 1 element because only A is less than B) 
    * Pr(tree consisting of 1 element because only C is greater than B) 
    = 1/3 * 1 * 1 = 1/3 

Cas 2:

A 
    B 
    C 

Pr = Pr(select A as a root of a whole tree) 
    * Pr(tree of 0 elements because none of elements is less than A) 
    * Pr(select B as a root of tree of elements greater than A) 
    * Pr(tree of 0 elements because none of remaining elements is less than B) 
    * Pr(tree of 1 element because C is greater than B) 
    = 1/3 * 1 * 1/2 * 1 * 1 = 1/6 

Cas 3, 4, 5:

Construire l'un de ces arbres est analogue à la Case 2 car ils partagent la même structure - vous pouvez calculer les probabilités et les vérifier.

Résumé

Bien sûr, chaque possible BST sur 3 éléments est indiqué ci-dessus, de sorte que la probabilité de ces arbres devrait résumer à 1, nous allons le vérifier:

Pr(Case 1) + 4 * Pr(Case 2) = 1/3 + 4 * 1/6 = 1/3 + 4/6 = 1 

Vous pouvez comprendre la réponse à votre deuxième question en examinant la méthode ci-dessus.