Drzewo BST - ilość konfiguracji

[priorytet26]

Witam.

Macie pomysł jak oszacować ile może być różnych konfiguracji drzewa BST zbudowanego z 5 różnych liczb?
Wygląd drzewa zależy od kolejności wprowadzania, więc można utworzyć 5! różnych wariancji wprowadzanego ciągu, ale są takie konfiguracje np. dla dwóch ostatnich elementów bedacymi liściami tego samego rodzica że nie ma znaczenia który liść pierwszy wprowadzimy. Tak wiec drzew będzie napewno mniej niż 5!

Pomóżcie mi oszacować prawidłowa wartość.

[adambak]

to nie jest takie proste chyba..
\(\displaystyle{ P(n)}\) - ilość drzew BST o \(\displaystyle{ n}\) elementach..
\(\displaystyle{ P(0)=1}\) (bo puste drzewo), \(\displaystyle{ P(1)=1}\)
\(\displaystyle{ P(n)= \sum_{k=1}^{n} P(k-1)P(n-k)}\), a do szacowania się przydadzą liczby Catalana.. tych drzew będzie wykładniczo dużo.

-- 12 lut 2012, o 16:18 --

teraz ciut wyjaśnienia.. mamy elementy: \(\displaystyle{ a_1<...<a_n}\) do rozmieszczenia na drzewie BST.. wiadomo, że odwiedzając wierzchołki tego drzewa metodą inorder kolejność będzie własnie taka (kolejno indeksy jeśli przyjmiemy to co wyżej napisałem).. wobec tego jeśli \(\displaystyle{ a_k}\) jest korzeniem drzewa to w jego lewym poddrzewie mamy elementy \(\displaystyle{ a_1,...,a_{k-1}}\), a elementy w jego prawym poddrzewie to: \(\displaystyle{ a_{k+1},...,a_n}\).. wobec tego jeśli \(\displaystyle{ a_k}\) jest korzeniem drzewa i mamy \(\displaystyle{ n}\) elementów w drzewie to ilość tych drzew BST to iloczyn liczby drzew BST jaką możemy utworzyć z elementów w lewym poddrzewie i liczby drzew BST jaką możemy utworzyć z elementów w prawym poddrzewie..

teraz ten wzór chyba powinien być bardziej jasny..

[abc666]

a do szacowania się przydadzą liczby Catalana.. tych drzew będzie wykładniczo dużo.

To będą właśnie liczby Catalana

[adambak]

no racja
bo ja wyszedłem od konstrukcji tego mojego wzorku i potem dopiero z nimi go skojarzyłem..