BST jest generowany (przez kolejne wstawianie węzłów) z każdej permutacji kluczy z zestawu {1,2,3,4,5,6,7}. Ile permutacji określają drzewa wysokości dwa?Ile permutacji danej macierzy prowadzi do BST o wysokości 2?
Utknąłem na tym prostym pytaniu od dłuższego czasu. Dowolne wskazówki.
Nawiasem mówiąc odpowiedź jest 80.
Zastanów się, jak drzewo byłoby wysokość 2?
-To musi mieć 4 jako root, 2 jako lewe dziecko, 6 Prawo dziecka itp
Jak to 4 jest korzeniem?
-To musi być wstawione jako pierwsze. Mamy więc teraz jedną cyfrę, 6 wciąż może poruszać się w permutacji.
I?
- Po pierwszej wkładce pozostało jeszcze 6 miejsc, 3 po lewej i 3 po prawej podtrees. To 6 wybierz 3 = 20 opcji.
Co teraz?
-Dla lewych i prawych poddrzew, ich korzenie należy najpierw wstawić, następnie kolejność dzieci nie wpływa na drzewo - 2, 1, 3 i 2, 3, 1 daje to samo drzewo. To 2 dla każdego poddrzewa i 2 * 2 = 4 dla lewego i prawego poddrzew.
Tak?
Podsumowując: C (6, 3) * 2 * 2 = 20 * 2 * 2 = 80.
Dlaczego zrobiliśmy C (6,3), ponieważ tylko {1,2,3} może tworzyć lewe poddrzewo, a {5, 6,7} może tworzyć właściwe poddrzewo? Nie mamy wyboru. Proszę wytłumacz. –
Należy zauważyć, że istnieje tylko jeden możliwy kształt tego drzewa - musi być doskonale wyważone . Ma zatem być to drzewo:
4
/ \
2 6
/\ /\
1 3 5 7
Wymaga to 4 do umieszczenia w pierwszej kolejności. Następnie wstawki muszą budować pododniesie o numerach 1, 2, 3 i 5, 6, 7 we właściwej kolejności. Oznacza to, że będziemy musieli wstawić 2 przed 1 i 3 i musimy wstawić 6 przed 5 i 7. Nie ma znaczenia, w jakiej względnej kolejności wstawiamy 1 i 3, o ile są po 2, i podobnie nie ma znaczenia, jaką względną kolejność postawimy na 5 i 7, pod warunkiem, że są po 6. Możesz więc pomyśleć o tym, co musimy wstawić jako 2 XX i 6 YY, gdzie X są dziećmi 2 i Y to dzieci 6. Możemy znaleźć wszystkie możliwe sposoby, aby wrócić do powyższego drzewa poprzez znalezienie wszystkich przeplotów sekwencji 2 XX i 6 YY, a następnie pomnożenie przez cztery (liczba sposobów przypisywania X i Y wartości 1 3, 5 i 7).
Ile jest sposobów przeplatania? Cóż, możesz myśleć o tym jako o liczbie sposobów permutacji sekwencji L L L R R R, ponieważ każda permutacja L L L R R R mówi nam, jak wybrać sekwencję Lewą lub Prawą. Jest 6!/3! 3! = 20 sposobów na zrobienie tego. Ponieważ każdy z tych dwudziestu przeplotów daje cztery możliwe sekwencje insercji, ostatecznie możliwe jest uzyskanie w sumie 20 4 =.
Mam nadzieję, że to pomoże!
Dzięki za wyjaśnienie! – user2473033
Aby wyjaśnić, że istnieje 20 różnych sposobów umieszczania 6 węzłów w drzewie po źródle głównym? – user2473033
@ user2473033- W rzeczywistości jest 80. Korzeń jest zmuszony być z przodu. – templatetypedef
Stworzyłem tabelę dla liczby możliwych permutacji z 1 - 12 elementami, z wysokościami do 12, i uwzględniono podział na root dla każdego, kto próbował sprawdzić, czy ich proces ręczny (opisany w innych odpowiedziach) jest zgodne z rzeczywistymi wartościami.
http://www.asmatteringofit.com/blog/2014/6/14/permutations-of-a-binary-search-tree-of-height-x
OK, tylko pytanie pytasz ma odpowiedź na końcu. Jakie jest twoje prawdziwe pytanie? * Jak * uzyskać tę odpowiedź? – vcsjones
Po prostu chciałem wiedzieć, jak dostać się do wysłanej odpowiedzi, widzę to teraz dzięki zamieszczonym komentarzom. – user2473033