Liczba możliwych ścieżek wyszukiwania podczas wyszukiwania w BST

Mam następujące pytanie, ale nie mam na to odpowiedzi. Byłbym wdzięczny, jeśli moja metoda jest poprawna:

P: Podczas wyszukiwania wartości klucza 60 w drzewie wyszukiwania binarnego węzły zawierające wartości klucza 10, 20, 40, 50, 70, 80, 90 są przemieszczane, niekoniecznie w podanej kolejności. Ile jest możliwych różnych zamówień, w których te kluczowe wartości mogą wystąpić na ścieżce wyszukiwania z węzła głównego zawierającego wartość 60?

(A) 35 (B) 64 (C) 128 (D) 5040

Z tego pytania rozumiem, że wszystkie podane węzły muszą być uwzględnione w przejściu i ostatecznie musimy dotrzeć do klucza 60. Na przykład jedna taka kombinacja to:

10, 20, 40, 50, 90, 80, 70, 60.

Ponieważ musimy przejść przez wszystkie podane powyżej węzły, musimy zacząć od 10 lub 90. Jeśli zaczniemy od 20, nie osiągniemy 10 (od 60> 20 i przejdziemy prawe poddrzewo 20)

Podobnie, nie możemy zacząć od 80, ponieważ nie będziemy w stanie osiągnąć 90, ponieważ od 80> 60 przejdziemy do lewego sub-drzewa 80 i tym samym nie osiągniemy 90.

Weźmy 10. Pozostałe węzły to 20, 40, 50, 70, 80, 90. Następny węzeł może mieć wartość 20 lub 90. Nie możemy wziąć innych węzłów z tego samego wcześniej wspomnianego powodu.

Jeśli rozważymy podobnie, na każdym poziomie mamy dwie możliwości. Ponieważ jest 7 węzłów, dwie opcje dla pierwszych 6 i brak wyboru dla ostatniej. Więc są całkowicie

$2*2*2*2*2*2*1$ permutacje = = $2^6$ $64$

Czy to poprawna odpowiedź?
Jeśli nie, jakie jest lepsze podejście?
Chciałbym uogólnić. Jeśli podano węzłów, wówczas całkowita możliwa ścieżka wyszukiwania wynosiłaby $n$ $2^{n-1}$

— avi
źródło

Odpowiedzi:

Jeśli szukasz klucza 60 docieramy numer mniej niż 60 lat, idziemy w prawo (tam gdzie są większe numery) i nigdy nie spotkać numery mniej niż . Argument ten można powtórzyć, więc liczby 10, 20, 40, 50 muszą wystąpić podczas wyszukiwania w tej kolejności. $K$ $K$

Podobnie, jeśli szukasz kluczu 60 osiągniemy liczbę większa niż 60, możemy przejść leftt (gdzie liczby są mniejsze) i nigdy numery spełniają większy niż . Dlatego liczby 90, 80, 70 muszą występować podczas wyszukiwania w tej kolejności. $K$ $K$

Sekwencje 10, 20, ~~30,~~ 40, 50 i 90, 80, 70 można następnie tasować razem, o ile ich podsekwencje pozostają nienaruszone. Zatem możemy mieć 10, 20, 40, 50, 90, 80, 70, ale także 10, 20, 90, 30, 40, 80, 70, 50.

Teraz możemy obliczyć liczbę, wybierając pozycję dużych i małych liczb. Zobacz komentarz Aryabhata. Mamy dwie sekwencje liczb 4 i 3. Ile sposobów mogę je przetasować? W ostatnich 7 pozycjach muszę wybrać 3 pozycje dla większych liczb (i pozostałe 4 dla mniejszych liczb). Mogę wybrać te na sposoby. Po ustaleniu tych pozycji znamy pełną sekwencję. Np. Mój pierwszy przykład ma pozycje SSSSLLL, a drugi ma SSLSLL S. $7 \choose 3$

Prosisz o uogólnienie. Zawsze liczby mniejsze niż liczba znaleziona, a liczby większe są ustalane w ich względnej kolejności. Mniejsze liczby muszą rosnąć, liczby arger muszą spadać. Liczba to . $x$ $y$ $x+y \choose y$

PS (edytowane). Podziękowania dla Gillesa, który zauważył, że 30 nie wchodzi w grę.

— Hendrik Jan
źródło

Z pewnością chciałbym spróbować. Ponieważ nr s 90,80,70 musi być razem, rozważmy je jako pojedynczy nr. i może być umieszczony w 6 miejscach: _ 10 _ 20 _ 30 _ 40 _ 50 _ Więc to Jeśli według tej samej analogii, nie s [10,20,30,40,50] 4 miejsca, to Ale to musi być podzielone przez często występujące kombinacje (których nie jestem w stanie zrozumieć)

2^{6}

$2^6$

2^{4}

$2^4$

— avi 5'13

@avi Nie, nie muszą być razem, tylko w tej kolejności: 10, 20, 90, 30, 40, 80, 70, 50 jest w porządku.

— Hendrik Jan

@avi: Spróbuj myśleć w ten sposób: duży i mały. Teraz masz 8 miejsc, 5 małych i 3 duże. Jak je wypełniasz? 8 wybierz 3. Co przychodzi do 56, i przypuszczam, że to, co Hendrik też dostał.

— Aryabhata

@HendrikJan W pierwotnym pytaniu nie było 30, było tylko 7 wartości. A 7 wybierz 3 to (A).

— Gilles 'SO - przestań być zły'

@HendrikJan - czy możesz mi to wyjaśnić: zawsze liczby mniejsze niż liczba znaleziona, a liczby większe są ustalane w ich względnej kolejności

x

$x$

y

$y$

— avi

Konwertujemy ruchy na tekst. Daje się do zrozumienia, że podczas wyszukiwania przemierzyliśmy te węzły

jak widać, czerwone są większe niż 60, a niebieskie mniejsze niż 60.

Ścieżka do węzła 60 obejmowała te węzły. Tak więc jednym z możliwych rozwiązań tego problemu jest każde inne rozwiązanie będzie zawierać tylko te ruchy. bo w tym samym czasie w węźle możemy uzyskać kierunki jako S lub L w porównaniu, a ponieważ biorąc pod uwagę, że te węzły zostały napotkane, oznacza to, że wskazówki zostały wybrane z tego zestawu.

{S, S, S, S, L, L, L}

$\{S,S,S,S,L,L,L\}$

Stąd całkowita liczba możliwych rozwiązań = wszystkie permutacje tego zestawu, co daje odpowiedzi = opcja A

\frac{7!}{4! \times 3!} = 35

$\frac{7!}{4! \times 3!} = 35$

— amarVashishth
źródło