Range Sum of BST

Q: Jaka jest złożoność czasowa sumy z zakresu w BST?

Przycięte przejście odwiedza k węzłów z zakresu oraz węzły na co najwyżej dwóch ścieżkach od korzenia: czas O(h + k) dla drzewa o głębokości h oraz O(n) , gdy każda wartość mieści się w zakresie. Stos lub rekurencja zajmuje O(h) miejsca.

Q: Czy problem sumy zakresu w BST można rozwiązać za pomocą przejścia in-order?

Tak. Przejście inorder wypisuje wartości w kolejności rosnącej, więc dodajesz wartości, gdy osiągną low , i zatrzymujesz się przy pierwszej wartości większej niż high . Wczesne zatrzymanie pozwala zaoszczędzić pracę po prawej stronie drzewa; przycinanie pozwala zaoszczędzić ją po obu stronach.

Q: Czy do obliczenia sumy zakresu w BST należy użyć rekurencji czy stosu?

Oba rozwiązania działają. Tutaj głębokość wynosi najwyżej 14, więc rekurencja pozostaje płytka. Jawny stos pozwala uniknąć limitu rekurencji w wysokim drzewie liczącym tysiące poziomów.

ŁatweDrzewo BST Przechodzenie drzewa

+10

Drzewo binarne wyszukiwań jest przechowywane w tablicy tree w porządku poziomami: korzeń znajduje się pod indeksem 0, dzieci węzła pod indeksem i znajdują się pod indeksami 2*i+1 (lewe) i 2*i+2 (prawe), a -1 oznacza puste miejsce. W drzewie binarnym wyszukiwań każda wartość w lewym poddrzewie węzła jest mniejsza od wartości tego węzła, a każda wartość w jego prawym poddrzewie jest większa.

Zwróć sumę wartości wszystkich węzłów v, dla których low ≤ v ≤ high, lub 0, jeśli takich wartości nie ma.

Funkcja

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

treeinteger-array: drzewo wyszukiwań binarnych w porządku poziomami, z -1 oznaczającym puste miejsce
lowinteger: najmniejsza wartość, którą należy policzyć
highinteger: największa wartość do zliczenia
Zwracainteger: suma wartości węzłów od low do high, włącznie

Ograniczenia

1 ≤ tree.length ≤ 32767
Każdy element tree[i] to -1 lub wartość spełniająca warunek 0 ≤ tree[i] ≤ 10⁵.
tree[0] nigdy nie jest równe -1, więc drzewo ma co najmniej jeden węzeł.
Tablica może kończyć się dodatkowymi wpisami -1 za ostatnim węzłem.
Oboje dzieci pustego miejsca również są puste, a głębokość wynosi co najwyżej 14.
Drzewo jest prawidłowym binarnym drzewem wyszukiwania, więc wszystkie jego wartości są różne.
0 ≤ low ≤ high ≤ 10⁵
Odpowiedź mieści się w 32-bitowej liczbie całkowitej ze znakiem.

Przykłady

Wejście: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Wyjście: 88
Wyjaśnienie: Wartości od 9 do 31 to 10, 12, 15, 20 i 31, które sumują się do 88. 3, 8 i 40 nie mieszczą się w tym zakresie.

Wejście: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Wyjście: 0
Wyjaśnienie: Drzewo zawiera 25, 50 i 75, a żadna z tych wartości nie mieści się między 60 a 70, więc suma wynosi 0. Cztery wpisy -1 oznaczają puste miejsca na dzieci węzłów 25 i 75.

Wejście: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Wyjście: 4
Wyjaśnienie: Gdy zarówno low, jak i high mają wartość 4, liczy się tylko węzeł o wartości 4. 4 pod indeksem 4 jest prawym dzieckiem 2, więc odpowiedź to 4.

Pytanie dodatkowe

Gdyby trzeba było odpowiadać na tysiące różnych zapytań (low, high) dotyczących tego samego drzewa, jak można by odpowiadać na każde z nich w czasie O(log n)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Odwiedzenie każdego węzła i dodanie wartości z zakresu jest poprawne. Porządek drzewa wyszukiwań pozwala zrobić mniej: wartość węzła wskazuje, po której stronie znajdują się mniejsze, a po której większe wartości, więc poddrzewo, które nie może zawierać wartości z zakresu, nigdy nie jest przeszukiwane.

Odwiedź każdy węzeł

Intuicja

Dziecko istnieje tylko wtedy, gdy jego indeks znajduje się w tablicy, a wartość pod tym indeksem nie jest równa -1. W pierwszym przykładzie 12 pod indeksem 4 ma dzieci 10 i 15 pod indeksami 9 i 10, a 31 pod indeksem 2 ma puste lewe miejsce pod indeksem 5.

Każda wartość z zakresu znajduje się w jakimś węźle, więc przejście stosowe, które odwiedza każdy węzeł i dodaje wartości spełniające warunek low ≤ v ≤ high, daje poprawną sumę. Ignoruje ono porządek drzewa wyszukiwań, więc odwiedza wszystkie n węzłów, nawet gdy zakres zawiera tylko kilka wartości.

Algorytm

Umieść indeks korzenia 0 na stosie i ustaw total = 0.
Zdejmij indeks i. Jeśli low ≤ tree[i] ≤ high, dodaj tree[i] do total.
Umieść 2*i+1 i 2*i+2 na stosie, jeśli znajdują się w tablicy i nie są równe -1.
Gdy stos będzie pusty, zwróć total.

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

Przycinanie zgodnie z kolejnością w drzewie wyszukiwania

Intuicja

Lewe poddrzewo węzła przechowującego v zawiera wyłącznie wartości mniejsze od v. Jeśli v ≤ low, żadna z nich nie należy do zakresu, więc pomiń to poddrzewo. Jeśli v ≥ high, prawe poddrzewo zawiera wyłącznie wartości większe od high, więc je pomiń. W pierwszym przykładzie 31 jest równe high, więc jego prawe dziecko 40 nigdy nie zostaje dodane na stos. 8 jest mniejsze od low, więc pomijane jest jego lewe dziecko 3, ale odwiedzane jest jego prawe dziecko 12, ponieważ wartości między 8 a 20 mogą należeć do zakresu.

Odwiedzasz k wartości z zakresu oraz węzły leżące na co najwyżej dwóch ścieżkach od korzenia: czas O(h + k) dla głębokości h. Gdy zakres obejmuje całe drzewo, nadal jest to O(n).

Algorytm

Umieść indeks korzenia 0 na stosie i ustaw total = 0.
Zdejmij indeks i ze stosu i odczytaj v = tree[i]. Jeśli low ≤ v ≤ high, dodaj v do total.
Jeśli v > low, umieść lewe dziecko 2*i+1 na stosie, jeśli istnieje.
Jeśli v < high, umieść prawe dziecko 2*i+2 na stosie, jeśli istnieje.
Gdy stos będzie pusty, zwróć total.

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

Pułapki i przypadki brzegowe

Używanie porównań ścisłych. Liczą się oba końce, więc trzeci przykład, w którym low = high = 4, musi uwzględniać 4.
Przycinanie o jeden krok za wcześnie. Dla v = low można pominąć lewe poddrzewo, ale dla v = low + 1 może ono zawierać samo low.
Pomijanie obu stron węzła znajdującego się poza zakresem. 8 w pierwszym przykładzie jest mniejsze niż low, ale jego prawe poddrzewo zawiera 10, 12 i 15.
Odczytywanie dziecka poza końcem tablicy. Przed odczytem sprawdź 2*i+1 < tree.length, a -1 traktuj jako brak dziecka.
W Lua i R tablice zaczynają się od 1: indeksy węzłów pozostaw liczone od 0 na potrzeby działania 2*i+1 i odczytuj tree[i + 1].

Najczęstsze pytania3

Jaka jest złożoność czasowa sumy z zakresu w BST?

Przycięte przejście odwiedza k węzłów z zakresu oraz węzły na co najwyżej dwóch ścieżkach od korzenia: czas O(h + k) dla drzewa o głębokości h oraz O(n), gdy każda wartość mieści się w zakresie. Stos lub rekurencja zajmuje O(h) miejsca.

Czy problem sumy zakresu w BST można rozwiązać za pomocą przejścia in-order?

Tak. Przejście inorder wypisuje wartości w kolejności rosnącej, więc dodajesz wartości, gdy osiągną low, i zatrzymujesz się przy pierwszej wartości większej niż high. Wczesne zatrzymanie pozwala zaoszczędzić pracę po prawej stronie drzewa; przycinanie pozwala zaoszczędzić ją po obu stronach.

Czy do obliczenia sumy zakresu w BST należy użyć rekurencji czy stosu?

Oba rozwiązania działają. Tutaj głębokość wynosi najwyżej 14, więc rekurencja pozostaje płytka. Jawny stos pozwala uniknąć limitu rekurencji w wysokim drzewie liczącym tysiące poziomów.

def rangeSumBST(tree, low, high):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik