BIT: Was ist die Intuition hinter einem binär indizierten Baum und wie wurde darüber nachgedacht?

99

Ein binär indizierter Baum hat im Vergleich zu anderen Datenstrukturen sehr wenig oder relativ wenig Literatur. Der einzige Ort, an dem es unterrichtet wird, ist das Topcoder-Tutorial . Obwohl das Tutorial in allen Erklärungen vollständig ist, kann ich die Intuition hinter einem solchen Baum nicht verstehen? Wie wurde es erfunden? Was ist der tatsächliche Beweis für seine Richtigkeit?

Nikunj Banka
quelle
4
Ein Artikel auf Wikipedia behauptet, dass diese Bäume Fenwick genannt werden .
David Harkness
2
@ DavidHarkness- Peter Fenwick hat die Datenstruktur erfunden, daher werden sie manchmal Fenwick-Bäume genannt. In seiner Originalarbeit (zu finden unter citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917 ) nannte er sie binär indizierte Bäume. Die beiden Begriffe werden häufig synonym verwendet.
Templatetypedef
1
Die folgende Antwort vermittelt eine sehr schöne "visuelle" Vorstellung von binär indizierten Bäumen. Cs.stackexchange.com/questions/42811/… .
Rabih Kodeih,
1
Ich weiß, wie du dich fühlst, als ich den Artikel zum ersten Mal las, schien es nur wie Zauberei.
Rockstar5645

Antworten:

168

Intuitiv können Sie sich einen binär indizierten Baum als komprimierte Darstellung eines Binärbaums vorstellen, der selbst eine Optimierung einer Standardarraydarstellung darstellt. Diese Antwort geht in eine mögliche Ableitung.

Angenommen, Sie möchten kumulative Häufigkeiten für insgesamt 7 verschiedene Elemente speichern. Sie könnten damit beginnen, sieben Eimer aufzuschreiben, auf die die Zahlen verteilt werden:

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

Nehmen wir nun an, dass die kumulativen Frequenzen ungefähr so ​​aussehen:

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

Mit dieser Version des Arrays können Sie die kumulative Häufigkeit eines Elements erhöhen, indem Sie den Wert der an dieser Stelle gespeicherten Zahl erhöhen und anschließend die Häufigkeit aller nachfolgenden Elemente erhöhen. Um beispielsweise die kumulative Häufigkeit von 3 um 7 zu erhöhen, können wir jedem Element im Array an oder nach Position 3 7 hinzufügen, wie hier gezeigt:

[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

Das Problem dabei ist, dass es O (n) Zeit braucht, was ziemlich langsam ist, wenn n groß ist.

Eine Möglichkeit, über eine Verbesserung dieses Vorgangs nachzudenken, besteht darin, das zu ändern, was wir in den Eimern aufbewahren. Anstatt die kumulative Frequenz bis zum angegebenen Punkt zu speichern, können Sie auch nur den Betrag speichern, um den sich die aktuelle Frequenz im Vergleich zum vorherigen Bucket erhöht hat. In unserem Fall würden wir beispielsweise die obigen Buckets wie folgt umschreiben:

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

Jetzt können wir die Frequenz innerhalb eines Buckets in der Zeit O (1) erhöhen, indem wir nur den entsprechenden Betrag zu diesem Bucket hinzufügen. Die Gesamtkosten für eine Suche werden jetzt jedoch zu O (n), da die Gesamtsumme im Bucket neu berechnet werden muss, indem die Werte in allen kleineren Buckets aufsummiert werden.

Die erste wichtige Erkenntnis, die wir von hier aus zu einem binär indizierten Baum gewinnen müssen, ist die folgende: Anstatt die Summe der Array-Elemente, die einem bestimmten Element vorausgehen, fortlaufend neu zu berechnen, was wäre, wenn wir die Gesamtsumme aller Elemente vor dem Bestimmten vorausberechnen würden Punkte in der Reihenfolge? Wenn wir das tun könnten, könnten wir die kumulative Summe zu einem bestimmten Zeitpunkt herausfinden, indem wir einfach die richtige Kombination dieser vorberechneten Summen zusammenfassen.

Eine Möglichkeit, dies zu tun, besteht darin, die Darstellung von einem Array von Buckets in einen binären Baum von Knoten zu ändern. Jeder Knoten wird mit einem Wert versehen, der die kumulative Summe aller Knoten links von diesem Knoten darstellt. Angenommen, wir erstellen den folgenden Binärbaum aus diesen Knoten:

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

Jetzt können wir jeden Knoten erweitern, indem wir die kumulative Summe aller Werte einschließlich dieses Knotens und seines linken Teilbaums speichern. Anhand unserer Werte würden wir beispielsweise Folgendes speichern:

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]

Aufgrund dieser Baumstruktur ist es einfach, die kumulative Summe bis zu einem Punkt zu bestimmen. Die Idee ist die folgende: Wir pflegen einen Zähler, anfangs 0, und führen dann eine normale binäre Suche durch, bis wir den fraglichen Knoten finden. Dabei haben wir auch Folgendes zu tun: Jedes Mal, wenn wir uns nach rechts bewegen, addieren wir den aktuellen Wert zum Zähler hinzu.

Angenommen, wir möchten die Summe für 3 nachschlagen. Dazu gehen wir wie folgt vor:

  • Beginnen Sie an der Wurzel (4). Zähler ist 0.
  • Gehe nach links zum Knoten (2). Zähler ist 0.
  • Gehe nach rechts zum Knoten (3). Zähler ist 0 + 6 = 6.
  • Finden Sie den Knoten (3). Zähler ist 6 + 15 = 21.

Sie können sich vorstellen, diesen Prozess auch in umgekehrter Reihenfolge auszuführen: Beginnen Sie an einem bestimmten Knoten, initialisieren Sie den Zähler auf den Wert dieses Knotens und gehen Sie dann den Baum zur Wurzel hinauf. Wenn Sie einem rechten untergeordneten Link nach oben folgen, fügen Sie den Wert an dem Knoten hinzu, an dem Sie ankommen. Um beispielsweise die Frequenz für 3 zu ermitteln, könnten wir Folgendes tun:

  • Beginnen Sie am Knoten (3). Zähler ist 15.
  • Gehe nach oben zu Knoten (2). Zähler ist 15 + 6 = 21.
  • Gehe nach oben zu Knoten (4). Zähler ist 21.

Um die Häufigkeit eines Knotens (und implizit die Häufigkeit aller darauf folgenden Knoten) zu erhöhen, müssen wir die Menge der Knoten in der Baumstruktur aktualisieren, die diesen Knoten in seinem linken Teilbaum enthalten. Dazu gehen wir wie folgt vor: Erhöhen Sie die Frequenz für diesen Knoten und gehen Sie dann zur Wurzel des Baums. Wenn Sie einem Link folgen, der Sie als linkes Kind aufnimmt, erhöhen Sie die Häufigkeit des Knotens, auf den Sie stoßen, indem Sie den aktuellen Wert hinzufügen.

Um beispielsweise die Frequenz von Knoten 1 um fünf zu erhöhen, gehen Sie wie folgt vor:

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

Erhöhen Sie ab Knoten 1 seine Frequenz um 5, um zu erhalten

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

Nun gehe zu seinem Elternteil:

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

Wir sind einem Link für ein linkes Kind nach oben gefolgt, also erhöhen wir auch die Frequenz dieses Knotens:

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

Wir gehen jetzt zu seinem Elternteil:

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

Das war ein linker untergeordneter Link, also erhöhen wir diesen Knoten ebenfalls:

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

Und jetzt sind wir fertig!

Der letzte Schritt ist die Konvertierung in einen binär indizierten Baum. Hier können wir einige lustige Dinge mit Binärzahlen machen. Lassen Sie uns jeden Bucket-Index in diesem Baum in Binärform umschreiben:

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

Hier können wir eine sehr, sehr coole Beobachtung machen. Nehmen Sie eine dieser Binärzahlen und suchen Sie die allerletzte 1, die in der Zahl festgelegt wurde, und lassen Sie das Bit zusammen mit allen nachfolgenden Bits fallen. Ihnen bleibt nun Folgendes übrig:

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

Hier ist eine wirklich, wirklich coole Beobachtung: Wenn Sie 0 als "links" und 1 als "rechts" behandeln, geben die verbleibenden Bits auf jeder Zahl genau an, wie Sie an der Wurzel beginnen und dann zu dieser Zahl gehen. Zum Beispiel hat Knoten 5 das binäre Muster 101. Die letzte 1 ist das letzte Bit, also lassen wir das fallen, um 10 zu erhalten. Wenn Sie an der Wurzel beginnen, gehen Sie nach rechts (1), dann gehen Sie nach links (0), Sie enden auf Knoten 5!

Der Grund dafür ist, dass unsere Such- und Aktualisierungsvorgänge vom Zugriffspfad vom Knoten zurück zum Stamm und davon abhängen, ob wir linken oder rechten untergeordneten Links folgen. Während einer Suche kümmern wir uns beispielsweise nur um die richtigen Links, denen wir folgen. Während eines Updates kümmern wir uns nur um die Links, denen wir folgen. Dieser binär indizierte Baum erledigt dies alles sehr effizient, indem er nur die Bits im Index verwendet.

Der Schlüsseltrick ist die folgende Eigenschaft dieses perfekten Binärbaums:

Bei gegebenem Knoten n wird der nächste Knoten auf dem Zugriffspfad zurück zu der Wurzel, in der wir nach rechts gehen, gegeben, indem die binäre Darstellung von n genommen und die letzte 1 entfernt wird.

Schauen Sie sich zum Beispiel den Zugriffspfad für Knoten 7 an, der 111 ist. Die Knoten auf dem Zugriffspfad zu der Wurzel, die wir nehmen und bei denen einem rechten Zeiger nach oben gefolgt wird, sind

  • Knoten 7: 111
  • Knoten 6: 110
  • Knoten 4: 100

All dies sind richtige Links. Wenn wir den Zugriffspfad für Knoten 3 verwenden, der 011 ist, und uns die Knoten ansehen, auf denen wir nach rechts gehen, erhalten wir

  • Knoten 3: 011
  • Knoten 2: 010
  • (Knoten 4: 100, der einem linken Link folgt)

Dies bedeutet, dass wir die kumulative Summe zu einem Knoten sehr, sehr effizient wie folgt berechnen können:

  • Schreiben Sie den Knoten n binär aus.
  • Stellen Sie den Zähler auf 0.
  • Wiederholen Sie den folgenden Vorgang, während n ≠ 0 ist:
    • Fügen Sie den Wert am Knoten n hinzu.
    • Lösche das am weitesten rechts stehende 1 Bit von n.

Überlegen wir uns in ähnlicher Weise, wie wir einen Aktualisierungsschritt durchführen würden. Zu diesem Zweck möchten wir dem Zugriffspfad zurück zum Stammverzeichnis folgen und alle Knoten aktualisieren, auf denen wir einem Link nach oben gefolgt sind. Wir können dies tun, indem wir im Wesentlichen den obigen Algorithmus ausführen, aber alle Einsen auf Nullen und Nullen auf Einsen schalten.

Der letzte Schritt im binär indizierten Baum besteht darin, zu beachten, dass wir aufgrund dieses bitweisen Tricks nicht einmal mehr den Baum explizit speichern müssen. Wir können einfach alle Knoten in einem Array der Länge n speichern und dann die bitweisen Twiddling-Techniken verwenden, um implizit im Baum zu navigieren. Genau das macht der bitweise indizierte Baum - er speichert die Knoten in einem Array und simuliert dann mithilfe dieser bitweisen Tricks effizient das Aufwärtsgehen in diesem Baum.

Hoffe das hilft!

templatetypedef
quelle
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Hjulle
Du hast mich im zweiten Absatz verloren. Was meinst du mit kumulativen Häufigkeiten von 7 verschiedenen Elementen?
Jason Goemaat
20
Dies ist bei weitem die beste Erklärung, die ich bisher zu diesem Thema gelesen habe, unter all den Quellen, die ich im Internet gefunden habe. Gut gemacht !
Anmol Singh Jaggi
2
Wie ist Fenwick so schlau geworden?
Rockstar5645
1
Dies ist eine sehr gute Erklärung, hat aber das gleiche Problem wie jede andere Erklärung, und Fenwicks eigene Arbeit liefert keinen Beweis!
DarthPaghius
3

Ich denke, dass das Originalpapier von Fenwick viel klarer ist. Die Antwort von @templatetypedef erfordert einige "sehr coole Beobachtungen" über die Indizierung eines perfekten Binärbaums, die für mich verwirrend und magisch sind.

Fenwick sagte einfach, dass der Verantwortungsbereich jedes Knotens im Abfragebaum dem zuletzt gesetzten Bit entsprechen würde:

Verantwortlichkeiten für Fenwick-Baumknoten

Da das zuletzt gesetzte Bit von 6== 00110beispielsweise ein "2-Bit" ist, ist es für einen Bereich von 2 Knoten verantwortlich. Für 12== 01100ist es ein "4-Bit", daher ist es für einen Bereich von 4 Knoten verantwortlich.

Wenn wir also F(12)== abfragen F(01100), werden die Bits einzeln entfernt und abgerufen F(9:12) + F(1:8). Dies ist bei weitem kein strenger Beweis, aber ich denke, dass es offensichtlicher ist, wenn man es so einfach auf der Zahlenachse und nicht auf einem perfekten Binärbaum ausdrückt, welche Aufgaben jeder Knoten hat und warum die Abfragekosten gleich der Anzahl von sind Bits setzen.

Wenn dies immer noch unklar ist, wird das Papier sehr empfohlen.

ihadanny
quelle