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?
algorithms
binary-trees
trees
Nikunj Banka
quelle
quelle
Antworten:
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:
Nehmen wir nun an, dass die kumulativen Frequenzen ungefähr so aussehen:
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:
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:
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:
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:
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:
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:
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:
Erhöhen Sie ab Knoten 1 seine Frequenz um 5, um zu erhalten
Nun gehe zu seinem Elternteil:
Wir sind einem Link für ein linkes Kind nach oben gefolgt, also erhöhen wir auch die Frequenz dieses Knotens:
Wir gehen jetzt zu seinem Elternteil:
Das war ein linker untergeordneter Link, also erhöhen wir diesen Knoten ebenfalls:
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:
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:
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:
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
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
Dies bedeutet, dass wir die kumulative Summe zu einem Knoten sehr, sehr effizient wie folgt berechnen können:
Ü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!
quelle
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:
Da das zuletzt gesetzte Bit von
6==00110beispielsweise ein "2-Bit" ist, ist es für einen Bereich von 2 Knoten verantwortlich. Für12==01100ist es ein "4-Bit", daher ist es für einen Bereich von 4 Knoten verantwortlich.Wenn wir also
F(12)== abfragenF(01100), werden die Bits einzeln entfernt und abgerufenF(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.
quelle