Range Sum of BST

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

Die beschnittene Traversierung besucht die k Knoten im Bereich sowie die Knoten auf höchstens zwei Pfaden von der Wurzel: O(h + k) Zeit für einen Baum der Tiefe h und O(n) , wenn jeder Wert im Bereich liegt. Der Stapel oder die Rekursion benötigt O(h) Speicherplatz.

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

Ja. Eine Inorder-Traversierung listet die Werte in aufsteigender Reihenfolge auf. Daher fügst du Werte hinzu, sobald sie low erreichen, und hörst beim ersten Wert auf, der größer als high ist. Der frühe Abbruch spart Arbeit auf der rechten Seite des Baums; durch das Beschneiden wird auf beiden Seiten Arbeit gespart.

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

Beides funktioniert. Hier beträgt die Tiefe höchstens 14, daher bleibt die Rekursion flach. Ein expliziter Stack vermeidet das Rekursionslimit bei einem hohen Baum mit Tausenden von Ebenen.

LeichtBinärer Suchbaum Baumdurchlauf

+10

Ein binärer Suchbaum wird im Level-Order-Verfahren im Array tree gespeichert: Die Wurzel befindet sich am Index 0, die Kinder des Knotens am Index i befinden sich bei 2*i+1 (links) und 2*i+2 (rechts), und -1 kennzeichnet eine leere Stelle. 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 größer.

Gib die Summe aller Knotenwerte v mit low ≤ v ≤ high zurück oder 0, wenn es keine solchen Werte gibt.

Funktion

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

treeinteger-array: der binäre Suchbaum in Level-Reihenfolge, mit -1 für eine leere Position
lowinteger: der kleinste zu zählende Wert
highinteger: den größten zu zählenden Wert
Gibt zurückinteger: die Summe der Knotenwerte zwischen low und high, einschließlich low und high

Einschränkungen

1 ≤ tree.length ≤ 32767
Jedes 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 mit zusätzlichen -1-Einträgen enden.
Beide Kindknoten 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. Die 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 am Index 4 ist das rechte Kind von 2, also lautet die Antwort 4.

Weiterführende Frage

Wenn du Tausende verschiedener (low, high)-Abfragen 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

Jeden Knoten zu besuchen und die Werte im Bereich zu addieren, ist korrekt. Die Ordnung im Suchbaum ermöglicht es dir, weniger zu tun: Der Wert eines Knotens zeigt dir, auf welcher Seite sich die kleineren und die größeren Werte befinden, sodass ein Teilbaum, der den Bereich nicht erreichen kann, gar nicht erst geöffnet wird.

Jeden Knoten besuchen

Idee

Ein Kind ist nur dann vorhanden, wenn sein Index innerhalb des Arrays liegt und der Wert dort nicht -1 ist. Im ersten Beispiel hat die 12 an Index 4 die Werte 10 und 15 an den Indizes 9 und 10, und bei der 31 an Index 2 ist die linke Position an Index 5 leer.

Jeder Wert im Bereich befindet sich in einem Knoten. Daher liefert eine Stack-Traversierung, die jeden Knoten erreicht und die Werte mit low ≤ v ≤ high addiert, die richtige Summe. Sie ignoriert die Ordnung des Suchbaums und besucht deshalb alle n Knoten, selbst wenn der Bereich nur wenige Werte enthält.

Algorithmus

Lege den Wurzelindex 0 auf einen Stapel und setze total = 0.
Entferne einen Index i vom Stapel. Wenn low ≤ tree[i] ≤ high gilt, addiere tree[i] zu total.
Lege 2*i+1 und 2*i+2 auf den Stapel, wenn sie innerhalb des Arrays liegen und nicht -1 sind.
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
        if left < n and tree[left] != -1:
            stack.append(left)
        if right < n and tree[right] != -1:
            stack.append(right)
    return total

Beschneiden in der Reihenfolge des Suchbaums

Idee

Der linke Teilbaum eines Knotens mit dem Wert v enthält ausschließlich Werte, die kleiner als v sind. Wenn v ≤ low gilt, liegt keiner davon im Bereich, also überspringe diesen Teilbaum. Wenn v ≥ high gilt, enthält der rechte Teilbaum ausschließlich Werte, die größer als high sind, also überspringe ihn. Im ersten Beispiel ist 31 gleich high, daher wird sein rechtes Kind 40 nie auf den Stack gelegt. 8 liegt unter low, daher wird sein linkes Kind 3 übersprungen, aber sein rechtes Kind 12 wird besucht, weil Werte zwischen 8 und 20 im Bereich liegen können.

Du besuchst die k Werte im Bereich sowie die Knoten auf höchstens zwei Pfaden von der Wurzel aus: O(h + k) Laufzeit bei einer Tiefe von h. Wenn der Bereich den gesamten Baum abdeckt, ist das immer noch O(n).

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 vorhanden ist.
Wenn v < high gilt, lege das rechte Kind 2*i+2 auf den Stapel, sofern es vorhanden ist.
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

Strikte Vergleiche verwenden. Beide Grenzen zählen, daher muss im dritten Beispiel mit low = high = 4 die 4 mitgezählt werden.
Eine Stufe zu früh abschneiden. Bei v = low kann der linke Teilbaum verworfen werden, aber bei v = low + 1 kann er low selbst enthalten.
Beide Seiten eines Knotens außerhalb des Bereichs verwerfen. Die 8 im ersten Beispiel liegt unter low, aber ihr rechter Teilbaum enthält 10, 12 und 15.
Ein Kind hinter dem Ende des Arrays auslesen. Prüfe 2*i+1 < tree.length, bevor du den Wert ausliest, und behandle -1 als kein Kind.
In Lua und R beginnen Arrays bei 1: Behalte für die Berechnung mit 2*i+1 die Knotenindizes bei 0 und lies tree[i + 1] aus.

Häufige Fragen3

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

Die beschnittene Traversierung besucht die k Knoten im Bereich sowie die Knoten auf höchstens zwei Pfaden von der Wurzel: O(h + k) Zeit für einen Baum der Tiefe h und O(n), wenn jeder Wert im Bereich liegt. Der Stapel oder die Rekursion benötigt O(h) Speicherplatz.

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

Ja. Eine Inorder-Traversierung listet die Werte in aufsteigender Reihenfolge auf. Daher fügst du Werte hinzu, sobald sie low erreichen, und hörst beim ersten Wert auf, der größer als high ist. Der frühe Abbruch spart Arbeit auf der rechten Seite des Baums; durch das Beschneiden wird auf beiden Seiten Arbeit gespart.

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

Beides funktioniert. Hier beträgt die Tiefe höchstens 14, daher bleibt die Rekursion flach. Ein expliziter Stack vermeidet das Rekursionslimit bei einem hohen Baum mit Tausenden von Ebenen.

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

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe