Z " N " Liczba węzłów, ile różnych binarnych i binarnych drzew Wyszukiwania możliwe?

1. Całkowita liczba drzew binarnych to =

2. Sumując i podaje całkowitą liczbę binarnych drzew wyszukiwania z węzłami N.

Podstawowym przypadkiem jest T (0) = 1 i t(1) = 1, tzn. jest jeden pusty BST i jest jeden BST z jednym węzłem.

Tak więc, ogólnie można obliczyć całkowitą liczbę binarnych drzew wyszukiwania używając powyższej formuły. Zadano mi pytanie w Google Wywiad związany z tą formułą. Pytanie, ile w sumie nie z binarnych drzew wyszukiwania są możliwe z 6 wierzchołkami. Więc odpowiedź to t (6) = 132

Liczbę drzew binarnych można obliczyć za pomocą Liczby Katalońskiej .

Liczba binarnych drzew wyszukiwania może być postrzegana jako rozwiązanie rekurencyjne. to znaczy, liczba binarnych drzew wyszukiwania = (Liczba Left binarnych pod-drzew wyszukiwania) *(Liczba Right binarnych pod-drzew wyszukiwania) * (sposoby wyboru korzenia)

W BST liczy się tylko względny porządek między elementami. Tak więc, bez straty na ogólności, możemy założyć, że poszczególne elementy w drzewa są 1, 2, 3, 4, ...., n . Również niech liczba BST będzie reprezentowana przez f (N) dla n elementów .

Teraz mamy wiele przypadków wyboru korzenia.

1. wybierz 1 jako root, żaden element nie może być wstawiony na lewym drzewie podrzędnym. N-1 elementy zostaną wstawione na prawym drzewie podrzędnym.
2. Wybierz 2 jako root, 1 element można wstawić na lewym Podrzewie. N-2 elementy można wstawiać po prawej stronie sub-tree.
3. Wybierz 3 jako root, 2 element można wstawić na lewym Podrzewie. N-3 elementy mogą być wstawiane na prawym Podrzewie.

...... Podobnie, dla i-th element jako pierwiastek, i-1 elementy mogą być po lewej i n-i po prawej.

Te podzbiory są same w sobie, więc możemy streścić wzór jako:

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

Przypadki bazowe, f (0) = 1, ponieważ istnieje dokładnie 1 sposób na utworzenie BST z 0 węzłami. f (1) = 1, ponieważ istnieje dokładnie 1 sposób na utworzenie BST z 1 węzłem.

Jeśli podano Nie. węzły są wtedy N.

Inny Nie of BST=Catalan (N)
Inne Nie. z różnych strukturalnie drzew binarnych są = Catalan (N)

Inny Nie drzewa binarne są=N!* Kataloński (N)

Eric Lippert miał ostatnio bardzo dogłębną serię wpisów na blogu o tym: "Every Binary Tree There Is " i "Every Tree There Is " (plus kilka kolejnych).

W odpowiedzi na twoje konkretne pytanie mówi:

Liczba drzew binarnych z węzłami n jest określona przez liczby katalońskie , które mają wiele interesujących właściwości. N - ta liczba katalońska jest określona wzorem (2n)! / (n+1)n!, który rośnie wykładniczo.

Różne drzewa binarne z węzłami n:

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

Gdzie C = kombinacja np.

n=6,
possible binary trees=(1/7)*(12C6)=132

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

The number of possible binary search tree with n nodes (elements,items) is

=(2n C n) / (n+1) = ( factorial (2n) / factorial (n) * factorial (2n - n) ) / ( n + 1 ) 

where 'n' is number of nodes  (elements,items ) 

Example :

for 
n=1 BST=1,
n=2 BST 2,
n=3 BST=5,
n=4 BST=14 etc

Poprawna odpowiedź powinna brzmieć 2nCn/(n+1) dla nieoznakowanych węzłów, a jeśli węzły są oznakowane to (2nCn)*n!/(n+1) .

Drzewo binarne:

Nie trzeba brać pod uwagę wartości, musimy spojrzeć na strukturę.

Given by (2 power n) - n

Np: dla trzech węzłów jest to (2 Moc 3) -3 = 8-3 = 5 różnych struktur

Binarne drzewo wyszukiwania:

Musimy wziąć pod uwagę nawet wartości węzłów. Nazywamy ją liczbą katalońską

Podane przez 2n C n / n+1