Range Sum of BST

Q: Wie hoch ist die Zeitkomplexität von Range Sum of BST?

Eine Traversierung, die mithilfe der Suchbaumordnung Teilbäume abschneidet, besucht die k Knoten im Bereich sowie die Knoten auf höchstens zwei Pfaden von der Wurzel aus. Die Laufzeit beträgt für einen Baum der Tiefe h O(h + k) . Im ungünstigsten Fall, wenn jeder Wert im Bereich liegt, ist sie O(n) . Der zusätzliche Speicherbedarf beträgt O(h) für den Stack oder die Rekursion.

Q: Warum kannst du Teilbäume bei Range Sum of BST überspringen?

In einem binären Suchbaum ist jeder Wert links von einem Knoten kleiner als dieser, und jeder Wert rechts davon ist größer. Wenn der Wert des Knotens höchstens low ist, kann nichts auf seiner linken Seite den Bereich erreichen, und wenn er mindestens high ist, kann nichts auf seiner rechten Seite den Bereich erreichen. Wenn diese Seiten übersprungen werden, wird kein Wert im Bereich übersehen.

Q: Kann Range Sum of BST mit einer Inorder-Traversierung gelöst werden?

Ja. Eine Inorder-Traversierung eines binären Suchbaums listet die Werte in aufsteigender Reihenfolge auf. Daher kannst du Werte addieren, sobald sie low erreichen, und aufhören, sobald ein Wert high überschreitet. Das ergibt dasselbe Ergebnis, und der frühe Abbruch spart Arbeit auf der rechten Seite des Baums, während die Suche mit Beschneidung auch auf der linken Seite Arbeit spart.

Q: Solltest du für die Bereichssumme eines BST Rekursion oder einen Stack verwenden?

Beides funktioniert. Rekursion ist kürzer, und hier beträgt die Tiefe höchstens 14, sodass der Aufrufstapel klein bleibt. Ein expliziter Stapel umgeht die Rekursionsgrenze vollständig. Das ist bei einem hohen Baum mit Tausenden von Ebenen wichtig und wird in den Lösungen auf dieser Seite verwendet.

LeichtBinärer Suchbaum Baumdurchlauf

+10

Du erhältst einen binären Suchbaum, der im Array tree in Ebenenreihenfolge gespeichert ist, sowie zwei Zahlen low und high. Die Wurzel befindet sich am Index 0, die Kinder des Knotens am Index i befinden sich an den Indizes 2*i+1 (links) und 2*i+2 (rechts), -1 kennzeichnet eine leere Stelle, und das Array kann mit zusätzlichen -1-Einträgen enden. In einem binären Suchbaum ist jeder Wert im linken Teilbaum eines Knotens kleiner als der Wert des Knotens, und jeder Wert in seinem rechten Teilbaum ist größer.

Schreibe eine Funktion namens rangeSumBST, die die Summe aller Knotenwerte v mit low ≤ v ≤ high zurückgibt, oder 0, wenn kein Wert in diesem Bereich liegt.

Funktion

rangeSumBST(tree: integer-array, low: integer, high: integer) → integer

treeinteger-array: den binären Suchbaum in Ebenenreihenfolge, wobei -1 für eine leere Stelle steht
lowinteger: der kleinste zu zählende Wert
highinteger: der größte Wert, der gezählt werden soll
Gibt zurückinteger: die Summe der Knotenwerte zwischen low und high, einschließlich beider Werte

Einschränkungen

1 ≤ tree.length ≤ 32767
Jeder tree[i] ist -1 oder ein Wert mit 0 ≤ tree[i] ≤ 10⁵.
tree[0] ist niemals -1, daher hat der Baum mindestens einen Knoten.
Das Array kann nach dem letzten Knoten noch zusätzliche -1-Einträge enthalten.
Beide Kinder einer leeren Stelle sind ebenfalls leer, und die Tiefe beträgt höchstens 14.
Der Baum ist ein gültiger binärer Suchbaum, daher sind alle seine Werte eindeutig.
0 ≤ low ≤ high ≤ 10⁵
Die Antwort passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Ausgabe: 88
Erklärung: Die Werte von 9 bis 31 sind 10, 12, 15, 20 und 31, was zusammen 88 ergibt. 3, 8 und 40 liegen außerhalb des Bereichs.

Eingabe: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Ausgabe: 0
Erklärung: Der Baum enthält 25, 50 und 75, und keiner davon liegt zwischen 60 und 70, daher ist die Summe 0. Die vier -1-Einträge sind die leeren Kindpositionen von 25 und 75.

Eingabe: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Ausgabe: 4
Erklärung: Wenn low und high beide 4 sind, zählt nur ein Knoten mit dem Wert 4. Die 4 an Index 4 ist das rechte Kind von 2, also lautet die Antwort 4.

+14 versteckte Tests beim Einreichen

Weiterführende Frage

Wenn du Tausende verschiedener Abfragen (low, high) für denselben Baum beantworten müsstest, wie könntest du jede einzelne in O(log n) Zeit beantworten?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Alle Werte im Bereich zu addieren, ist eine einfache Traversierung: Besuche jeden Knoten und behalte die passenden. Die Ordnung des Suchbaums ermöglicht es dir, effizienter vorzugehen. Der Wert eines Knotens zeigt dir, auf welcher Seite die kleineren und größeren Werte liegen, sodass ganze Teilbäume übersprungen werden können, ohne auch nur einen einzigen Knoten darin anzusehen.

Besuche jeden Knoten

Idee

Zuerst: wie man sich im Array bewegt. Der Knoten am Index i hat sein linkes Kind bei 2*i+1 und sein rechtes Kind bei 2*i+2. Ein Kind ist nur dann vorhanden, wenn sein Index innerhalb des Arrays liegt und der Wert dort nicht -1 ist. In [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15] hat die Wurzel 20 die Knoten 8 und 31 an den Indizes 1 und 2; der Knoten 12 am Index 4 hat die Knoten 10 und 15 an den Indizes 9 und 10, und der Knoten 31 hat an Index 5 eine leere Position links.

Nun zur Idee. Jeder Wert im Bereich befindet sich in einem Knoten. Eine Traversierung, die jeden Knoten erreicht und die Werte mit low ≤ v ≤ high addiert, ergibt also die richtige Summe. Verwende einen Stapel mit Knotenindizes. Beginne an der Wurzel, nimm einen Index vom Stapel, addiere seinen Wert, falls er im Bereich liegt, und lege jedes vorhandene Kind auf den Stapel.

Das ignoriert die Eigenschaft des Suchbaums vollständig; es funktioniert bei jedem Binärbaum. Dabei werden alle n Knoten besucht: O(n) Zeit. Der Stapel enthält die noch zu bearbeitenden Kinder entlang eines Pfads: O(h) Speicherplatz bei einer Tiefe von h. Wenn der Bereich nur wenige Werte in einem Baum mit Tausenden von Knoten umfasst, ist der Großteil dieser Arbeit vergeudet.

Algorithmus

Lege den Wurzelindex 0 auf einen Stack und setze total = 0.
Entferne einen Index i vom Stack. Wenn low ≤ tree[i] ≤ high, addiere tree[i] zu total.
Lege 2*i+1 und 2*i+2 auf den Stack, wenn sie sich innerhalb des Arrays befinden und nicht -1 sind.
Wenn der Stack leer ist, gib total zurück.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append(left)
        if right < n and tree[right] != -1:
            stack.append(right)
    return total

Mit der Suchbaum-Reihenfolge beschneiden

Idee

Behalte dieselbe Stapeldurchquerung bei, aber nutze die Ordnung. Angenommen, ein Knoten enthält v. Sein linker Teilbaum enthält nur Werte, die kleiner als v sind. Wenn v ≤ low, liegt jeder dieser Werte unter low, daher kann der linke Teilbaum nichts beitragen: Überspringe ihn. Ebenso enthält der rechte Teilbaum, wenn v ≥ high, nur Werte über high: Überspringe ihn. Den linken Kindknoten legst du also nur dann auf den Stapel, wenn v > low, und den rechten Kindknoten nur dann, wenn v < high.

Im ersten Beispiel mit dem Bereich [9, 31] ist 31 gleich high, also wird sein rechter Kindknoten 40 nie auf den Stapel gelegt. 8 liegt unter low, daher wird sein linker Kindknoten 3 übersprungen, während sein rechter Kindknoten 12 weiterhin besucht wird, weil Werte zwischen 8 und 20 im Bereich liegen können.

Die besuchten Knoten sind die k Werte im Bereich sowie höchstens zwei Wurzel-Blatt-Pfade entlang seiner Grenzen, daher beträgt die Laufzeit O(h + k). Wenn der Bereich den gesamten Baum umfasst, ist sie weiterhin O(n), aber ein enger Bereich in einem großen Baum berührt nur einige Dutzend Knoten. Der Stapel benötigt O(h) Speicherplatz.

Algorithmus

Lege den Wurzelindex 0 auf einen Stapel und setze total = 0.
Nimm einen Index i vom Stapel und lies v = tree[i]. Wenn low ≤ v ≤ high gilt, addiere v zu total.
Wenn v > low gilt, lege das linke Kind 2*i+1 auf den Stapel, sofern es existiert.
Wenn v < high gilt, lege das rechte Kind 2*i+2 auf den Stapel, sofern es existiert.
Wenn der Stapel leer ist, gib total zurück.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        # Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
        if value > low and left < n and tree[left] != -1:
            stack.append(left)
        if value < high and right < n and tree[right] != -1:
            stack.append(right)
    return total

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen an den Grenzen des Bereichs oder des Arrays.

Strikte Vergleiche verwenden. Beide Enden sind eingeschlossen, daher zählt ein Knoten, der gleich low oder high ist.
Zu früh um einen Schritt beschneiden. Wenn v gleich low ist, kann der linke Teilbaum übersprungen werden, aber wenn v low + 1 ist, geht das nicht: Er kann low selbst enthalten.
Bei einem Knoten außerhalb des Bereichs anhalten. Ein Knoten unterhalb von low kann immer noch einen rechten Teilbaum voller Werte im Bereich haben. Überspringe daher nur die Seite, die durch die Ordnungsregeln ausgeschlossen ist.
Einen Kindindex hinter dem Ende des Arrays auslesen. Prüfe 2*i+1 < tree.length, bevor du den Wert ausliest, und behandle -1 als nicht vorhandenes Kind.
Den Versatz in Lua und R verwechseln, wo Arrays bei 1 beginnen. Verwende für die 2*i+1-Berechnung weiterhin 0-basierte Knotenindizes und lies tree[i + 1] aus.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Range Sum of BST?

Eine Traversierung, die mithilfe der Suchbaumordnung Teilbäume abschneidet, besucht die k Knoten im Bereich sowie die Knoten auf höchstens zwei Pfaden von der Wurzel aus. Die Laufzeit beträgt für einen Baum der Tiefe h O(h + k). Im ungünstigsten Fall, wenn jeder Wert im Bereich liegt, ist sie O(n). Der zusätzliche Speicherbedarf beträgt O(h) für den Stack oder die Rekursion.

Warum kannst du Teilbäume bei Range Sum of BST überspringen?

In einem binären Suchbaum ist jeder Wert links von einem Knoten kleiner als dieser, und jeder Wert rechts davon ist größer. Wenn der Wert des Knotens höchstens low ist, kann nichts auf seiner linken Seite den Bereich erreichen, und wenn er mindestens high ist, kann nichts auf seiner rechten Seite den Bereich erreichen. Wenn diese Seiten übersprungen werden, wird kein Wert im Bereich übersehen.

Kann Range Sum of BST mit einer Inorder-Traversierung gelöst werden?

Ja. Eine Inorder-Traversierung eines binären Suchbaums listet die Werte in aufsteigender Reihenfolge auf. Daher kannst du Werte addieren, sobald sie low erreichen, und aufhören, sobald ein Wert high überschreitet. Das ergibt dasselbe Ergebnis, und der frühe Abbruch spart Arbeit auf der rechten Seite des Baums, während die Suche mit Beschneidung auch auf der linken Seite Arbeit spart.

Solltest du für die Bereichssumme eines BST Rekursion oder einen Stack verwenden?

Beides funktioniert. Rekursion ist kürzer, und hier beträgt die Tiefe höchstens 14, sodass der Aufrufstapel klein bleibt. Ein expliziter Stapel umgeht die Rekursionsgrenze vollständig. Das ist bei einem hohen Baum mit Tausenden von Ebenen wichtig und wird in den Lösungen auf dieser Seite verwendet.

Python

def rangeSumBST(tree, low, high):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]
low = 9
high = 31

Erwartet