[Algorytmy] suma elementow w drzewie w przedziale w O(logn)

rivit
Użytkownik
Użytkownik
Posty: 163
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 2 razy

[Algorytmy] suma elementow w drzewie w przedziale w O(logn)

Post autor: rivit »

Proszę opisać jak zmodyfikować drzewa BST (przechowujące elementy typu int) tak, by operacja:
int sum(T, x, y)
obliczająca sumę elementów z drzewa o wartościach z przedziału [x, y] działała w czasie O(log n) (gdzie n to rozmiar drzewa T). (Podpowiedź: Warto w każdym węźle drzewa przechowywać pewną dodatkową informację, która upraszcza wykonanie operacji sum i którą można łatwo aktualizować).

Jakoś nie mam pomysłu jak zmodyfikować, myślałem, żeby trzymać dodatkowe pole, które zawiera sume poddrzewa łącznie z samym sobą, ale nie wiem jak później to liczyć.
Prosze o pomoc ;)
Ostatnio zmieniony 1 maja 2019, o 15:53 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Ponury123
Użytkownik
Użytkownik
Posty: 128
Rejestracja: 5 lip 2015, o 14:48
Płeć: Mężczyzna
Lokalizacja: nie wiem
Podziękował: 11 razy
Pomógł: 24 razy

Re: suma elementow w drzewie w podanym przedziale w O(logn)

Post autor: Ponury123 »

Dobry pomysł,(suma dla poddrzewa z lewej i prawej strony oddzielnie) potem wystarczy sprawdzić dla korzenia \(\displaystyle{ R}\) jaki jest w stosunku do przedziału\(\displaystyle{ (x,y)}\)

A) Jeśli jest mniejszy niż \(\displaystyle{ y}\) to idziemy cały czas w lewo, i sprawdzamy czy natkniemy się na wartość mniejszą niż \(\displaystyle{ x}\)

- Jeśli tak, to musimy odjąć wartość sumy dla tego poddrzewa od naszej sumy dla początkowego korzenia \(\displaystyle{ R}\).
- Jeśli doszliśmy do końca i nie znaleźliśmy to znaczy, że całą sumę dla lewego syna korzenia \(\displaystyle{ R}\) możemy zachować.

Co do prawej strony to idziemy tak długo, aż nie znajdziemy wartości większej od \(\displaystyle{ y}\):
- jeśli znajdziemy to cofamy się o jeden poziom wyżej i bierzemy sumę dla lewej strony.
- jeśli nie znajdziemy możemy zachować całą sumę dla prawej strony dla korzenia \(\displaystyle{ R}\)

B) Jeśli jest większy to pomijamy go i cała jego prawą stronę i powielamy kroki A sprawdzając B i C dla jego lewego syna.
C) Jeśli jest mniejszy niż \(\displaystyle{ x}\) to pomijamy go i cała jego lewą stronę, powielamy kroki A sprawdzając B i C dla jego prawego syna.

Co do wartości skrajnych czyli wartość korzenia jest równa \(\displaystyle{ y}\) wtedy dla prawej strony sprawdzamy czy syn jest lub nie taki sam jak rodzić, i tak samo dla \(\displaystyle{ x}\).
Dudenzz
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 8 mar 2009, o 18:21
Płeć: Mężczyzna
Pomógł: 19 razy

[Algorytmy] suma elementow w drzewie w przedziale w O(logn)

Post autor: Dudenzz »

A) Jeśli jest mniejszy niż y to idziemy cały czas w lewo, i sprawdzamy czy natkniemy się na wartość mniejszą niż x
Nie idziemy cały czas w lewo. Naszym zadaniem jest znalezienie największej wartości mniejszej niż x. Wierzchołek, który taką wartość przechowuje wcale nie musi być lewym dzieckiem, tym bardziej "skrajnym" lewym dzieckiem.

Aby rozwiązać to zadanie wystarczy policzyć

\(\displaystyle{ S_{(x,y)} = S_{(-\inf,y>} - S_{(-\inf,x>}}\)

Jeżeli przechowuje się sumy częściowe lewego poddrzewa należy znaleźć wierzchołek, którego wartość jest największą wartością mniejszą lub równą x i zapisać jego sumę częściową jako \(\displaystyle{ S_{(-\inf),x>}}\) oraz wierzchołek, którego wartość jest największą wartością mniejszą lub równą y i zapisać jego sumę częściową jako \(\displaystyle{ S_{(-\inf),y>}}\). Można to zrobić bardzo łatwo wykorzystując zmodyfikowany algorytm wyszukiwania.

Algorytm wyznaczania \(\displaystyle{ S_{(-\inf,x>}}\)

Kod: Zaznacz cały

Nazwa: smin(T,x)
Dodatkowe oznaczenia: L(T) - lewe dziecko; P(T) prawe dziecko, V(T) wartość T, S(T) suma lewego poddrzewa T
Notatka: suma prawego poddrzewa jest obliczana tylko w celu utworzenia drzewa i nie jest wykorzystywana w algorytmie
wejście: wierzchołek R, wartość x
wyjście: suma wartości wierzchołków mniejszych od x w drzewie o korzeniu R

1. Jeżeli V(R) > x:
       a. jeżeli L(R):
             zwróć smin(L(R),x)
       w przeciwnym wypadku
             zwróć 0
    w przeciwnym wypadku:
       a. jeżeli P(R)
             zwróć smin(P(R),x) + S(R) + V(R)
       w przeciwnym wypadku
             zwróć S(R) + V(R)
Można usprawnić przedstawiony algorytm i wykorzystać podobną ideę do obliczenia \(\displaystyle{ S_{<y,\inf)}}\) oraz zastosować wzór \(\displaystyle{ S_{(x,y)} = S - S_{<y,\inf)} - S_{(-\inf,x>}}\)
ODPOWIEDZ