Range Sum of BST

Q: Jaka jest złożoność czasowa zadania Range Sum of BST?

Przejście, które przycina przeszukiwanie zgodnie z kolejnością w drzewie wyszukiwań, odwiedza k węzłów z zakresu oraz węzły znajdujące się na najwyżej dwóch ścieżkach od korzenia, co daje czas O(h + k) dla drzewa o głębokości h . W najgorszym przypadku, gdy każda wartość mieści się w zakresie, jest to O(n) . Dodatkowa przestrzeń wynosi O(h) na stos lub rekurencję.

Q: Dlaczego w zadaniu Range Sum of BST można pomijać poddrzewa?

W drzewie binarnym wyszukiwań każda wartość po lewej stronie węzła jest mniejsza od niego, a każda wartość po prawej stronie jest większa. Jeśli wartość węzła jest mniejsza lub równa low , żadna wartość po jego lewej stronie nie może znaleźć się w przedziale, a jeśli jest większa lub równa high , żadna wartość po jego prawej stronie nie może się w nim znaleźć. Pominięcie tych stron nigdy nie spowoduje przeoczenia wartości z przedziału.

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

Tak. Przejście drzewa binarnego wyszukiwania w porządku inorder wypisuje wartości w kolejności rosnącej, więc możesz dodawać wartości, gdy osiągną low , i zatrzymać się, gdy tylko któraś przekroczy high . Daje to ten sam wynik, a wcześniejsze zatrzymanie pozwala zaoszczędzić pracę po prawej stronie drzewa, podczas gdy przeszukiwanie z przycinaniem pozwala zaoszczędzić pracę także po lewej.

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

Oba rozwiązania działają. Rekurencja jest krótsza, a tutaj głębokość wynosi najwyżej 14, więc stos wywołań pozostaje niewielki. Jawny stos całkowicie omija limit rekurencji, co ma znaczenie w przypadku wysokiego drzewa o tysiącach poziomów, i właśnie tego używają rozwiązania na tej stronie.

ŁatweDrzewo BST Przechodzenie drzewa

+10

Otrzymujesz drzewo binarnych poszukiwań zapisane w tablicy tree w kolejności poziomami oraz dwie liczby low i high. 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), -1 oznacza puste miejsce, a tablica może kończyć się dodatkowymi wpisami -1. W drzewie binarnych poszukiwań 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.

Napisz funkcję o nazwie rangeSumBST, która zwraca sumę wszystkich wartości węzłów v, dla których low ≤ v ≤ high, albo 0, gdy żadna wartość nie mieści się w tym zakresie.

Funkcja

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

treeinteger-array: drzewo binarne wyszukiwań w kolejności poziomami, z -1 oznaczającym puste miejsce
lowinteger: najmniejsza wartość do zliczenia
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żde tree[i] ma wartość -1 albo wartość spełniającą 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 drzewem wyszukiwania binarnego, 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 znajdują się poza zakresem.

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. Wartość 4 pod indeksem 4 jest prawym dzieckiem 2, więc odpowiedź to 4.

+14 ukrytych testów przy wysłaniu

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

Dodawanie wszystkich wartości z zakresu to zwykłe przechodzenie: odwiedź każdy węzeł i zachowaj te, które pasują. Porządek w drzewie wyszukiwań pozwala zrobić to lepiej. Wartość węzła wskazuje, po której stronie znajdują się mniejsze i większe wartości, dzięki czemu można pominąć całe poddrzewa, nie zaglądając do żadnego węzła w ich obrębie.

Odwiedź każdy węzeł

Intuicja

Najpierw: jak poruszać się po tablicy. Węzeł o indeksie i ma lewe dziecko pod indeksem 2*i+1, a prawe dziecko pod indeksem 2*i+2. Dziecko istnieje tylko wtedy, gdy jego indeks mieści się w tablicy, a wartość pod tym indeksem nie jest równa -1. W [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15] korzeń 20 ma dzieci 8 i 31 pod indeksami 1 i 2, węzeł 12 pod indeksem 4 ma dzieci 10 i 15 pod indeksami 9 i 10, a węzeł 31 ma puste lewe miejsce pod indeksem 5.

A teraz pomysł. Każda wartość z zakresu znajduje się w jakimś węźle, więc przejście, które odwiedza każdy węzeł i dodaje wartości spełniające warunek low ≤ v ≤ high, da właściwą sumę. Użyj stosu indeksów węzłów. Zacznij od korzenia, zdejmij indeks ze stosu, dodaj jego wartość, jeśli mieści się w zakresie, a następnie dodaj na stos każde istniejące dziecko.

To rozwiązanie całkowicie pomija własność drzewa wyszukiwań; działa na dowolnym drzewie binarnym. Odwiedza wszystkie n węzłów, działa w czasie O(n), a stos przechowuje oczekujące dzieci na jednej ścieżce, co wymaga O(h) miejsca dla głębokości h. Gdy zakres obejmuje tylko kilka wartości w drzewie liczącym tysiące węzłów, większość tej pracy idzie na marne.

Algorytm

Umieść indeks korzenia 0 na stosie i ustaw total = 0.
Zdejmij indeks i ze stosu. 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

Przycinaj zgodnie z kolejnością w drzewie wyszukiwań

Intuicja

Zachowaj to samo przechodzenie za pomocą stosu, ale wykorzystaj własności porządku. Załóżmy, że węzeł zawiera v. Jego lewe poddrzewo zawiera wyłącznie wartości mniejsze od v. Jeśli v ≤ low, wszystkie z nich są mniejsze od low, więc lewe poddrzewo nie może nic dodać: pomiń je. Podobnie, jeśli v ≥ high, prawe poddrzewo zawiera wyłącznie wartości większe od high: pomiń je. Dlatego lewe dziecko dodajesz na stos tylko wtedy, gdy v > low, a prawe dziecko tylko wtedy, gdy v < high.

W pierwszym przykładzie, dla zakresu [9, 31], wartość 31 jest równa high, więc prawe dziecko 40 nigdy nie trafia na stos. Wartość 8 jest mniejsza od low, więc jej lewe dziecko 3 zostaje pominięte, a prawe dziecko 12 nadal jest odwiedzane, ponieważ wartości między 8 a 20 mogą należeć do zakresu.

Odwiedzasz węzły o wartościach k należących do zakresu oraz najwyżej dwie ścieżki od korzenia do liścia wzdłuż jego krawędzi, więc czas działania wynosi O(h + k). Gdy zakres obejmuje całe drzewo, nadal jest to O(n), ale wąski zakres w dużym drzewie wymaga odwiedzenia tylko kilkudziesięciu węzłów. Stos wymaga O(h) pamięci.

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 jest 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

Większość błędnych odpowiedzi wynika z nieprawidłowego uwzględnienia granic zakresu lub tablicy.

Używanie porównań ostrych. Uwzględnione są oba końce, więc węzeł równy low lub high jest brany pod uwagę.
Przycinanie o krok za wcześnie. Gdy v jest równe low, można pominąć lewe poddrzewo, ale gdy v ma wartość low + 1, nie można tego zrobić: może ono zawierać samo low.
Zatrzymywanie się na węźle spoza zakresu. Węzeł mniejszy od low może nadal mieć prawe poddrzewo pełne wartości z zakresu, więc pomijaj tylko tę stronę, którą wykluczają reguły porządku.
Odczytywanie indeksu dziecka spoza tablicy. Przed odczytaniem wartości sprawdź 2*i+1 < tree.length i traktuj -1 jako brak dziecka.
Pomylenie przesunięcia w Lua i R, gdzie tablice zaczynają się od 1. Zachowaj indeksy węzłów oparte na 0 na potrzeby obliczeń 2*i+1 i odczytuj tree[i + 1].

Najczęstsze pytania4

Jaka jest złożoność czasowa zadania Range Sum of BST?

Przejście, które przycina przeszukiwanie zgodnie z kolejnością w drzewie wyszukiwań, odwiedza k węzłów z zakresu oraz węzły znajdujące się na najwyżej dwóch ścieżkach od korzenia, co daje czas O(h + k) dla drzewa o głębokości h. W najgorszym przypadku, gdy każda wartość mieści się w zakresie, jest to O(n). Dodatkowa przestrzeń wynosi O(h) na stos lub rekurencję.

Dlaczego w zadaniu Range Sum of BST można pomijać poddrzewa?

W drzewie binarnym wyszukiwań każda wartość po lewej stronie węzła jest mniejsza od niego, a każda wartość po prawej stronie jest większa. Jeśli wartość węzła jest mniejsza lub równa low, żadna wartość po jego lewej stronie nie może znaleźć się w przedziale, a jeśli jest większa lub równa high, żadna wartość po jego prawej stronie nie może się w nim znaleźć. Pominięcie tych stron nigdy nie spowoduje przeoczenia wartości z przedziału.

Czy problem sumy z zakresu w BST można rozwiązać za pomocą przejścia inorder?

Tak. Przejście drzewa binarnego wyszukiwania w porządku inorder wypisuje wartości w kolejności rosnącej, więc możesz dodawać wartości, gdy osiągną low, i zatrzymać się, gdy tylko któraś przekroczy high. Daje to ten sam wynik, a wcześniejsze zatrzymanie pozwala zaoszczędzić pracę po prawej stronie drzewa, podczas gdy przeszukiwanie z przycinaniem pozwala zaoszczędzić pracę także po lewej.

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

Oba rozwiązania działają. Rekurencja jest krótsza, a tutaj głębokość wynosi najwyżej 14, więc stos wywołań pozostaje niewielki. Jawny stos całkowicie omija limit rekurencji, co ma znaczenie w przypadku wysokiego drzewa o tysiącach poziomów, i właśnie tego używają rozwiązania na tej stronie.

Python

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

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane