Ile drzew wyszukiwania binarnego można zbudować z różnych elementów? I jak możemy znaleźć matematycznie udowodnioną na to formułę?Liczba drzew wyszukiwania binarnego nad n odrębnymi elementami
przykład: Jeśli mamy 3 odrębne elementy, np 1, 2, 3, to jest 5 poszukiwania binarnego drzewa.
względu N elementów, z których wiele dwuskładnikowych drzew wyszukiwania, które mogą być wykonane z tych elementów, jest przez n Catalan number (oznaczonego C n). Jest ona równa
Intuicyjnie, kataloński numery reprezentują liczbę sposobów, które można utworzyć strukturę z n elementów, które dokonuje się w następujący sposób:
Ten wzór doskonale pasuje do sposobu, w jaki można zbudować BST z zestawu n elementów. Wybierz jeden element, który będzie użyty jako główny element drzewa. Wszystkie mniejsze elementy muszą iść w lewo, a wszystkie większe elementy muszą iść w prawo. Stamtąd możesz zbudować mniejsze BST z elementów po lewej i po prawej stronie, a następnie połączyć je z węzłem głównym, tworząc ogólny BST. Liczba sposobów, które możesz zrobić z n elementami, jest podana przez C n, a zatem liczba możliwych BST jest podana przez n-ty numer Katalonii.
Mam nadzieję, że to pomoże!
Na przykład dla węzłów 10, 10, 10 liczba drzew wyszukiwania binarnego to 1. Ale liczba katalońska to 5. Ale jeśli wszystkie elementy są różne, to jest OK, myślę. –
@ SukhanovNiсkolay Liczba BST nadal wynosi 5 za 10,10, 10. Kształt drzewa będzie inny. – rents
Niech T (n) będzie liczbą bsts n elementów.
Biorąc pod uwagę n różnych uporządkowanych elementów, ponumerowanych od 1 do n, wybieramy i jako root.
Zostanie otwarty (1..i-1) w lewym poddrzewie dla kombinacji T (i-1) oraz (i + 1..n) w prawym poddrzewie dla kombinacji T (n-i).
Dlatego:
T(n) = sum_i=1^n(T(i-1) * T(n-i))
i oczywiście T (1) = 1
Może warto wspomnieć, że ten cykl się rozwiązuje z n-tym katalońskim numerem. – templatetypedef
@templatetypedef: Czy wiesz, jak wyprowadzić wzór liczby katalitowej, zaczynając od sumy, którą pokazałem? –
@ user1131467 Ta suma powinna być dokładnie liczbą triangulacji wielokąta ponad węzły n + 2, w taki sposób, w jaki zostałem wprowadzony do liczb katalońskich. Naprawiasz krawędź i pozwalasz oscylować nad pozostałymi wierzchołkami n, która pozostawia ci dwa wielokąty o rozmiarach i-1 i n-i. –
Jestem pewien, że to pytanie jest nie tylko policzyć za pomocą wzoru matematycznego .. Wyjąłem trochę czasu i napisał program i wyjaśnienie lub pomysł obliczania tego samego.
Próbowałem rozwiązać go z rekurencją i programowaniem dynamicznym. Mam nadzieję że to pomoże.
Formuła jest już obecne w poprzedniej odpowiedzi:
więc jeśli jesteś zainteresowany w nauce rozwiązania i zrozumienia apporach zawsze można sprawdzić mój artykuł Count Binary Search Trees created from N unique elements
Prawdopodobnie [podobne] (http: // stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possib). –