5

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.

+0

OK, tylko pytanie pytasz ma odpowiedź na końcu. Jakie jest twoje prawdziwe pytanie? * Jak * uzyskać tę odpowiedź? – vcsjones

+0

Po prostu chciałem wiedzieć, jak dostać się do wysłanej odpowiedzi, widzę to teraz dzięki zamieszczonym komentarzom. – user2473033

Odpowiedz

5

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.

+0

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. –

2

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!

+0

Dzięki za wyjaśnienie! – user2473033

+0

Aby wyjaśnić, że istnieje 20 różnych sposobów umieszczania 6 węzłów w drzewie po źródle głównym? – user2473033

+0

@ user2473033- W rzeczywistości jest 80. Korzeń jest zmuszony być z przodu. – templatetypedef