BIT: Jaka intuicja kryje się za drzewkiem binarnym i jak o tym myśleli?

Drzewo indeksowane binarnie nie ma żadnej literatury lub ma stosunkowo niewiele literatury w porównaniu do innych struktur danych. Jedynym miejscem, w którym jest nauczany, jest samouczek topcodera . Chociaż samouczek jest kompletny we wszystkich objaśnieniach, nie rozumiem intuicji stojącej za takim drzewem? Jak został wymyślony? Jaki jest faktyczny dowód jego poprawności?

Intuicyjnie można myśleć o binarnym drzewie indeksowanym jako skompresowanej reprezentacji drzewa binarnego, która sama jest optymalizacją standardowej reprezentacji tablicowej. Ta odpowiedź dotyczy jednej możliwej pochodnej.

Załóżmy na przykład, że chcesz przechowywać skumulowane częstotliwości dla łącznie 7 różnych elementów. Możesz zacząć od napisania siedmiu wiader, na które zostaną rozdzielone liczby:

[   ] [   ] [   ] [   ] [   ] [   ] [   ]
  1     2     3     4     5     6     7

Załóżmy teraz, że skumulowane częstotliwości wyglądają mniej więcej tak:

[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
  1     2     3     4     5     6     7

Korzystając z 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 nastąpi później. Na przykład, aby zwiększyć łączną częstotliwość 3 o 7, możemy dodać 7 do każdego elementu w tablicy w pozycji 3 lub później, 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) czas, co jest dość wolne, jeśli n jest duże.

Jednym ze sposobów, w jaki możemy myśleć o usprawnieniu tej operacji, jest zmiana tego, co przechowujemy w wiadrach. Zamiast zapisywać skumulowaną częstotliwość do danego punktu, możesz zamiast tego pomyśleć o zapisaniu kwoty, którą wzrosła częstotliwość bieżąca w stosunku do poprzedniego segmentu. Na przykład w naszym przypadku przepisalibyśmy powyższe segmenty 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 ramach segmentu w czasie O (1), po prostu dodając odpowiednią wartość do tego segmentu. Jednak całkowity koszt przeprowadzenia wyszukiwania staje się teraz O (n), ponieważ musimy ponownie obliczyć sumę w segmencie, sumując wartości we wszystkich mniejszych segmentach.

Pierwszym ważnym wglądem, który musimy stąd uzyskać do drzewa indeksowanego binarnie, jest: zamiast ciągle obliczać sumę elementów tablicy poprzedzających dany element, co by było, gdybyśmy wstępnie obliczyli całkowitą sumę wszystkich elementów przed określonym punkty w sekwencji? Gdybyśmy mogli to zrobić, moglibyśmy obliczyć skumulowaną sumę w jednym punkcie, po prostu sumując odpowiednią kombinację tych wstępnie obliczonych sum.

Jednym ze sposobów na to jest zmiana reprezentacji z bycia tablicą wiader 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. Załóżmy na przykład, że konstruujemy następujące drzewo binarne z tych węzłów:

             4
          /     \
         2       6
        / \     / \
       1   3   5   7

Teraz możemy rozszerzyć każdy węzeł, przechowując skumulowaną sumę wszystkich wartości, w tym tego węzła i jego lewego poddrzewa. Na przykład, biorąc pod uwagę nasze wartości, przechowowalibyśmy następujące:

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 ustalić łączną sumę do pewnego momentu. Pomysł jest następujący: utrzymujemy licznik, początkowo 0, a następnie wykonujemy normalne wyszukiwanie binarne, aż znajdziemy dany węzeł. Robiąc to, wykonujemy również następujące czynności: za każdym razem, gdy poruszamy się w prawo, dodajemy również bieżącą wartość do licznika.

Załóżmy na przykład, że chcemy sprawdzić sumę dla 3. Aby to zrobić, wykonaj następujące czynności:

• Zacznij od katalogu głównego (4). Licznik to 0.
• Idź w lewo do węzła (2). Licznik to 0.
• Idź w prawo do węzła (3). Licznik to 0 + 6 = 6.
• Znajdź węzeł (3). Licznik to 6 + 15 = 21.

Można sobie również wyobrazić uruchomienie tego procesu w odwrotnej kolejności: zaczynając od danego węzła, zainicjuj licznik na wartość tego węzła, a następnie przejdź po drzewie do katalogu głównego. Za każdym razem, gdy podążasz w górę za prawym linkiem podrzędnym, dodaj wartość w węźle, do którego dotrzesz. 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ęzła (2). Licznik to 15 + 6 = 21.
• Idź w górę do węzła (4). Licznik to 21.

Aby zwiększyć częstotliwość węzła (i domyślnie częstotliwości wszystkich kolejnych węzłów po nim), musimy zaktualizować zestaw węzłów w drzewie, które zawierają ten węzeł w jego lewym poddrzewie. Aby to zrobić, wykonaj następujące czynności: zwiększ częstotliwość dla tego węzła, a następnie zacznij podchodzić do korzenia drzewa. Za każdym razem, gdy podążasz za linkiem, który traktuje cię jak lewe dziecko, zwiększ częstotliwość napotkanego węzła, dodając bieżącą wartość.

Na przykład, aby zwiększyć częstotliwość węzła 1 o pięć, wykonaj 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 przejdź do jego rodzica:

                 4
               [+32]
              /     \
         > 2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

Połączyliśmy lewy link potomny 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]

To było lewe łącze potomne, więc zwiększamy również ten węzeł:

                 4
               [+37]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

A teraz skończone!

Ostatnim krokiem jest konwersja z tego drzewa na indeksowane binarnie drzewo i tutaj możemy robić zabawne rzeczy z liczbami binarnymi. Przepiszmy indeks każdego segmentu w tym drzewie w formacie binarnym:

                100
               [+37]
              /     \
          010         110
         [+11]       [+80]
         /   \       /   \
       001   011   101   111
      [+10] [+15] [+52] [ +0]

Tutaj możemy dokonać bardzo, bardzo fajnej obserwacji. Weź dowolną z tych liczb binarnych i znajdź ostatnią 1, która została ustawiona w liczbie, a następnie upuść ten bit wraz ze wszystkimi późniejszymi bitami. Pozostały Ci następujące:

              (empty)
               [+37]
              /     \
           0           1
         [+11]       [+80]
         /   \       /   \
        00   01     10   11
      [+10] [+15] [+52] [ +0]

Oto naprawdę fajna obserwacja: jeśli traktujesz 0 jako „lewy” i 1 jako „prawy”, pozostałe bity na każdej liczbie określają dokładnie, jak zacząć od rdzenia, a następnie zejść do tej liczby. Na przykład, węzeł 5 ma wzór binarny 101. Ostatni 1 to ostatni bit, więc upuszczamy go, aby uzyskać 10. Rzeczywiście, jeśli zaczniesz od roota, idź w prawo (1), a następnie w lewo (0), skończysz w węźle 5!

Powodem tego jest to, że nasze operacje wyszukiwania i aktualizacji zależą od ścieżki dostępu od węzła z powrotem do katalogu głównego i tego, czy podążamy za lewym lub prawym linkiem potomnym. Na przykład podczas wyszukiwania dbamy tylko o odpowiednie linki, które podążamy. Podczas aktualizacji dbamy tylko o lewe linki, które obserwujemy. To drzewo indeksowane binarnie robi to wszystko bardzo wydajnie, po prostu używając bitów w indeksie.

Kluczową sztuczką jest następująca właściwość tego doskonałego drzewa binarnego:

Biorąc pod uwagę 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 binarną reprezentację 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 katalogu głównego, które przyjmujemy i które wymagają podążenia prawego wskaźnika w górę, to

• Węzeł 7: 111
• Węzeł 6: 110
• Węzeł 4: 100

Wszystko to 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

• Węzeł 3: 011
• Węzeł 2: 010
• (Węzeł 4: 100, który podąża za lewym linkiem)

Oznacza to, że możemy bardzo, bardzo skutecznie obliczyć sumę skumulowaną do węzła w następujący sposób:

• Zapisz węzeł n binarnie.
• Ustaw licznik na 0.
• Powtórz następujące czynności, gdy n ≠ 0:
  • Dodaj wartość w węźle n.
  • Usuń skrajnie prawy 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 linkiem 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 binarnym drzewie indeksowanym jest zwrócenie uwagi, że z powodu tej sztuczki bitowej nie musimy nawet przechowywać tego drzewa jawnie. Możemy po prostu zapisać wszystkie węzły w tablicy o długości n, a następnie użyć bitowych technik kręcenia, aby niejawnie poruszać się po drzewie. W rzeczywistości to właśnie robi drzewo indeksowane bitowo - przechowuje węzły w tablicy, a następnie używa tych bitowych sztuczek, aby skutecznie symulować chodzenie w górę w tym drzewie.

Mam nadzieję że to pomoże!

Myślę, że oryginalny artykuł Fenwicka jest znacznie jaśniejszy. Powyższa odpowiedź autorstwa @templatetypedef wymaga pewnych „bardzo fajnych obserwacji” dotyczących indeksowania idealnego drzewa binarnego, które są dla mnie mylące i magiczne.

Fenwick po prostu powiedział, że zakres odpowiedzialności każdego węzła w drzewie zapytań będzie zgodny z jego ostatnim ustawionym bitem:

Np. Ponieważ ostatni zestaw bitów 6== 00110jest „2-bitowy”, będzie odpowiedzialny za zakres 2 węzłów. Dla 12== 01100jest to „4-bit”, więc będzie odpowiedzialny za zakres 4 węzłów.

Tak więc, podczas zapytania F(12)== F(01100), usuwamy bity jeden po drugim, otrzymując F(9:12) + F(1:8). Nie jest to prawie rygorystyczny dowód, ale myślę, że jest to bardziej oczywiste, gdy umieści się tak po prostu na osi liczb, a nie na idealnym drzewie binarnym, jakie są obowiązki każdego węzła i dlaczego koszt zapytania jest równy liczbie ustawić bity.

Jeśli nadal nie jest jasne, papier jest bardzo zalecany.