BIT: używając binarnego drzewa indeksowanego? [zamknięte]
Binarne drzewo indeksowane ma niewiele lub stosunkowo nie ma teorii do zbadania w porównaniu z innymi strukturami danych. Jedynym miejscem, gdzie jest nauczany zwięźle jest TopCoder tutorial . Chociaż samouczek jest kompletny we wszystkich wyjaśnieniach, nie mogę zrozumieć, że jaka jest intuicja za takim drzewem? I jak udowodnić swoją poprawność?
Zakładam, że dowód jest skomplikowany do wyjaśnienia. Więc kiedy używasz bitu, jakie podejście stosujesz?
1 answers
Znalazłem ta odpowiedź autorstwa @ templatetypedef bardzo jasno wyjaśnia intuicję i dowód binarnego drzewa indeksowanego: Odpowiedź....
Intuicyjnie można myśleć o binarnym drzewie indeksowanym jako skompresowanej reprezentacji drzewa binarnego, która sama w sobie jest optymalizacją standardowej reprezentacji tablicy. Ta odpowiedź idzie w jednym możliwym wyprowadzeniu.
Załóżmy, na przykład, że chcesz przechowywać skumulowane częstotliwości dla łącznie 7 różnych żywioły. Możesz zacząć od wypisania siedmiu wiader, do których będą rozdysponowane liczby:
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
1 2 3 4 5 6 7
Załóżmy teraz, że kumulatywne częstotliwości wyglądają mniej więcej tak:
[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
1 2 3 4 5 6 7
Używając tej wersji tablicy, możesz zwiększyć skumulowaną częstotliwość dowolnego elementu, zwiększając wartość liczby przechowywanej w tym miejscu, a następnie zwiększając częstotliwości wszystkiego, co nadejdzie później. Na przykład, aby zwiększyć łączną częstotliwość 3 po 7 możemy dodać 7 do każdego elementu tablicy na lub po pozycji 3, Jak pokazano tutaj:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
Problem polega na tym, że zajmuje to O (n) czasu, co jest dość powolne, jeśli n jest duże.
Jednym ze sposobów, w jaki możemy myśleć o ulepszeniu tej operacji, byłaby zmiana tego, co przechowujemy w wiadrach. Zamiast zapisywać skumulowaną częstotliwość do danego punktu, można zamiast tego pomyśleć o przechowywaniu tylko kwoty, którą bieżąca częstotliwość wzrosła w stosunku do poprzednie wiadro. Na przykład, w naszym przypadku, przepiszemy powyższe wiadra w następujący sposób:
Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
Teraz możemy zwiększyć częstotliwość w wiadrze w czasie O (1), dodając odpowiednią ilość do tego wiadra. Jednak całkowity koszt przeprowadzenia wyszukiwania staje się teraz O( n), ponieważ musimy ponownie obliczyć sumę w wiadrze, sumując wartości we wszystkich mniejszych wiadrach.
Pierwszy duży wgląd musimy dostać się stąd do binarnego drzewa indeksowane jest następująca: zamiast przeliczać w sposób ciągły sumę elementów tablicy poprzedzających dany element, co by było, gdybyśmy wstępnie obliczyli sumę wszystkich elementów przed określonymi punktami w sekwencji? Gdybyśmy mogli to zrobić, to moglibyśmy obliczyć sumę skumulowaną w pewnym punkcie, po prostu sumując właściwą kombinację tych wstępnie obliczonych Sum.
Jednym ze sposobów na to jest zmiana reprezentacji z tablicy wiadrów na binarne drzewo węzłów. Każdy węzeł zostanie opatrzony adnotacją o wartości, która reprezentuje skumulowaną sumę wszystkich węzłów po lewej stronie danego węzła. Na przykład, załóżmy, że z tych węzłów zbudujemy następujące drzewo binarne:
4
/ \
2 6
/ \ / \
1 3 5 7
Teraz możemy powiększyć każdy węzeł, przechowując skumulowaną sumę wszystkich wartości łącznie z tym węzłem i jego lewym poddanym. Na przykład, biorąc pod uwagę nasze wartości, przechowujemy następujące wartości:
Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
After:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[ +5] [+15] [+52] [ +0]
Biorąc pod uwagę tę strukturę drzewa, łatwo jest określić sumę kumulacyjną do punkt. Idea jest następująca: utrzymujemy licznik, początkowo 0, a następnie wykonujemy normalne wyszukiwanie binarne aż do znalezienia danego węzła. Jak to robimy, mamy również następujące: za każdym razem, że poruszamy się w prawo, dodajemy również w bieżącej wartości do licznika.
Na przykład, załóżmy, że chcemy sprawdzić sumę dla 3. W tym celu wykonujemy następujące czynności:]}
- zacznij od korzenia (4). Licznik wynosi 0.
- idź w lewo do node (2). Licznik wynosi 0.
- przejdź w prawo do węzła (3). Licznik wynosi 0 + 6 = 6.
- Znajdź węzeł (3). Licznik wynosi 6 + 15 = 21.
Możesz sobie wyobrazić również uruchamianie tego procesu w odwrotnej kolejności: zaczynając od danego węzła, inicjalizuj licznik do wartości tego węzła, a następnie idź w górę drzewa do korzenia. Za każdym razem, gdy podążasz za prawym łączem potomnym w górę, Dodaj wartość w węźle, do którego docierasz. Na przykład, aby znaleźć częstotliwość dla 3, możemy wykonać następujące czynności:
- zacznij od węzła (3). Licznik to 15.
- idź w górę do węzeł (2). Licznik wynosi 15 + 6 = 21.
- idź w górę do węzła (1). Licznik 21.
Aby zwiększyć częstotliwość węzła (i, domyślnie, częstotliwości wszystkich węzłów, które przychodzą po nim), musimy zaktualizować zestaw węzłów w drzewie, które zawierają ten węzeł w jego lewym poddrzewie. Aby to zrobić, wykonujemy następujące czynności: zwiększamy częstotliwość dla tego węzła, a następnie zaczynamy podchodzić do korzenia drzewa. Za każdym razem, gdy klikniesz link, który zabierze cię w górę jako lewe dziecko, zwiększ częstotliwość napotkanego węzła poprzez dodanie bieżącej wartości.
Na przykład, aby zwiększyć częstotliwość węzła 1 o pięć, wykonamy następujące czynności:]} 4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[ +5] [+15] [+52] [ +0]
Począwszy od węzła 1, zwiększ jego częstotliwość o 5, aby uzyskać
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[+10] [+15] [+52] [ +0]
Teraz idź do rodzica:
4
[+32]
/ \
> 2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Podążaliśmy za lewym łączem potomnym w górę, więc zwiększamy również częstotliwość tego węzła:
4
[+32]
/ \
> 2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Przechodzimy teraz do jego rodzica:
> 4
[+32]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
4
[+37]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
A teraz skończyliśmy!
Ostatnim krokiem jest konwersja z tego do binarnego drzewa indeksowanego, i to jest miejsce, gdzie możemy zrobić kilka zabawnych rzeczy z liczbami binarnymi. Przepisz każdy indeks wiadra w tym drzewie w postaci binarnej:
100
[+37]
/ \
010 110
[+11] [+80]
/ \ / \
001 011 101 111
[+10] [+15] [+52] [ +0]
Tutaj możemy zrobić bardzo, bardzo fajną obserwację. Weź jedną z tych liczb binarnych i znajdź ostatnią 1, która została ustawiona w liczbie, a następnie upuść ten bit, wraz ze wszystkimi bitami, które przychodzą po nim. Teraz pozostało Ci:
(empty)
[+37]
/ \
0 1
[+11] [+80]
/ \ / \
00 01 10 11
[+10] [+15] [+52] [ +0]
Oto naprawdę, naprawdę fajna obserwacja: jeśli traktujesz 0 jako "lewy", a 1 jako" prawy", pozostałe bity na każdej liczbie określają dokładnie, jak zacząć od początku, a następnie przejść do tej liczby. Na przykład node 5 ma binarny wzór 101. Ostatni 1 jest ostatnim bitem, więc rzucamy go, aby uzyskać 10. Rzeczywiście, jeśli zaczniesz od głównego, idź w prawo (1), a następnie w lewo (0), skończysz na węźle 5!
Powód, dla którego jest to istotne jest to, że nasze operacje wyszukiwania i aktualizacji zależą od ścieżki dostępu od węzła z powrotem do katalogu głównego oraz od tego, czy podążamy za lewym czy prawym łączem potomnym. Na przykład, podczas wyszukiwania, po prostu dbamy o lewe linki, które śledzimy. Podczas aktualizacji dbamy tylko o odpowiednie linki, które śledzimy. To binarne drzewo indeksowane robi to wszystko bardzo wydajnie, używając tylko bitów w indeksie.
Kluczem jest następująca własność tego doskonałego binarnego drzewo:
Dany węzeł n, następny węzeł na ścieżce dostępu z powrotem do katalogu głównego, w którym idziemy w prawo, jest podawany przez pobranie binarnej reprezentacji n i usunięcie ostatniego 1.
Na przykład spójrz na ścieżkę dostępu dla węzła 7, czyli 111. Węzły na ścieżce dostępu do korzenia, które bierzemy, które wymagają podążania prawym wskaźnikiem w górę, to
- Node 7: 111
- Node 6: 110
- Node 4: 100
Wszystkie te są właściwe linki. Jeśli weźmiemy ścieżkę dostępu do węzła 3, czyli 011, i spojrzymy na węzły, w których idziemy w prawo, otrzymamy
- Node 3: 011
- Node 2: 010
- (W związku z tym, że nie jest to możliwe, nie jest to możliwe.]}
Oznacza to, że możemy bardzo, bardzo efektywnie obliczyć sumę skumulowaną do węzła w następujący sposób:
- wypisuje węzeł N w postaci binarnej.
- Ustaw licznik na 0.
- powtórz następujący while N ≠ 0:
- Dodaj wartość w node n.
- Usuń lewy 1 bit Z n.
Podobnie, zastanówmy się, jak zrobilibyśmy krok aktualizacji. Aby to zrobić, chcielibyśmy podążać ścieżką dostępu z powrotem do katalogu głównego, aktualizując wszystkie węzły, w których podążaliśmy lewym łączem w górę. Możemy to zrobić zasadniczo wykonując powyższy algorytm, ale przełączając wszystkie 1 na 0 i 0 Na 1.
Ostatnim krokiem w drzewie binarnym jest zwrócenie uwagi, że ponieważ z tej bitowej sztuczki, nawet nie musimy mieć drzewo przechowywane jawnie już. Możemy po prostu zapisać wszystkie węzły w tablicy o długości n, a następnie użyć technik bitwise twidling do nawigowania po drzewie bezwarunkowo. W rzeczywistości to właśnie robi bitowo indeksowane drzewo-przechowuje węzły w tablicy , a następnie wykorzystuje te bitowo sztuczki, aby skutecznie symulować chodzenie w górę tego drzewa.
Mam nadzieję, że to pomoże!
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-04-13 12:48:30