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

Odpowiedz Nowy wątek
2019-04-30 23:53
0

Proszę opisać jak zmodyfikować drzewa czerwono-czarne (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). Pozostałe operacje na powstałym drzewie powinny mieć złożoność taką samą jak w standardowym drzewie czerwono-czarnym. (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 ;)

Pozostało 580 znaków

2019-05-01 00:22
1

To nie ma znaczenia czy to drzewo RB, ważniejsze, że ty drzewo BST. W takim wypadku szukasz pierwszego elementu, który jest zawarty w przedziale [x, y]. Jak go już masz, to wiesz jaka jest górna granica sumy. W tym momencie szukasz w jego poddrzewie elementu mniejszego od x oraz większego od y i wartości sum jakie tam są przechowane odejmujesz od pierwotnej sumy i masz wynik.

Pozostało 580 znaków

2019-05-01 01:28
0

Rozumiem, to że trzeba znaleźć pierwszą liczbę, która zwiera się w przedziale. Jednak drugiej części nie rozumiem.
Załóżmy ze mam takie drzewo (wartosci w nawiasach to sumy):
title
Przedział, który chcę zsumować to [2,4]
czyli zajmujemy się poddrzewem, którego korzeniem jest 4.
El mniejszy od 2 (x) to 1, a większego od 4 (y) nie ma.

Pierwotna suma to 10.
Czyli wynikiem jest 10 - 6 = 4, a miało wyjść 9.

Mógłbyś rozwinąc trochę twoj pomysł?

edytowany 2x, ostatnio: newbier123, 2019-05-01 01:42

Pozostało 580 znaków

2019-05-01 12:53
0

W twoim przypadku to drzewo nie wygląda na zbalansowane, bo odległość między najdalszym liściem (5) jest większa niż dwukrotność najbliższego liścia (2). Więc to RB coś nie zadziałało.

Pozostało 580 znaków

2019-05-01 12:54
0

Sam napisałeś, że nie ma znaczenia czy to RB czy nie :o

Pozostało 580 znaków

2019-05-01 13:28
0

Drzewo nie musi być RB by było zbalansowane, drzewa RB są samo balansujące, to całkiem spora różnica. Późno było i zapomniałem napisać, że musi to być zbalansowane drzewo. Ja znalazłem jeszcze jeden problem w tym co napisałem, ale to już jest mniejszy problem, bo ogólny zarys idei masz. Praktycznie jedyna różnica jest taka jakich elementów potem szukasz w początkowym poddrzewie.

Pozostało 580 znaków

2019-05-01 14:46

Jesteś pewny że to zadziała? nawet jak drzewo będzie zbalansowane:

      4
    /    \
   2        6
 /   \     / \
1     3   5   7

to dla przedziału [3,5] da wynik 28 - 6 - 18 = 4, a powinno być 12 ;)

Moje pierwsze skojarzenie to było sumowanie z drzewa przedziałowego i wydaje mi się że wystarczy je trochę zmodyfikować by działało dla dowolnego drzewa binarnego. Zresztą idea jest bardzo podobna do tego co zaproponowałeś.

1) Znajdujemy lewy koniec przedziału w drzewie.
2) Jeśli nasz znaleziony koniec przedziału, ma prawe poddrzewo, to sumę z prawego poddrzewa dodajemy do wyniku + wartość elementu przechowywanego w lewym krańcu.
3) Idziemy w górę drzewa aż do pierwszego elementu w przedziale - elementu który jest najwyżej w drzewie i należy do przedziału (pierwszego/najwyższego elementu nie przetwarzamy)
4) i tak dla każdego odwiedzonego węzła, jeśli weszliśmy do niego z lewej stron, dodajemy do wyniku prawe poddrzewo + wartość węzła
5) symetrycznie robimy dla prawej strony i końca przedziału (wchodzimy z prawej to dodajemy sumę z lewego podrzewa + wartość węzła)
6) na końcu dodajemy jeszcze wartość z z pierwszego/najwyższego elementu w drzewie, jeśli on nie jest końcem przedziału

algorytm sumowania dla drzewa przedziałowego jest tutaj ładnie opisany:
http://was.zaa.mimuw.edu.pl/?q=node/9

edytowany 3x, ostatnio: neves, 2019-05-01 14:59

Pozostało 580 znaków

2019-05-01 14:51
0

Lewy koniec przedziału znaczy liczbę najbliższą temu lewemu końcu, która zawiera się w przedziale, tak?

a dodatkową informacją w przechowywaną w drzewie jest suma prawego poddrzewa? - newbier123 2019-05-01 15:06
nie, przechowuje dokładnie to co myślałeś, sumę poddrzewa z samym sobą - neves 2019-05-01 15:15

Pozostało 580 znaków

2019-05-01 15:12
1

przykład dla przedziału [2,16], trójkąty oznaczają sumy poddrzewa
title
== 1 etap
1) lewy koniec +2 do wyniku
2) weszliśmy z prawej strony -> nie robimy nic
3) weszliśmy z lewej -> dodajemy: prawa suma +9, węzeł +3
== 2 etap
4) prawy koniec +16 do wyniku
5) weszliśmy z prawej strony -> dodajemy: lewa suma +14, węzeł +15
6) weszliśmy z lewej strony -> nie robimy nic
7) weszliśmy z lewej strony -> nie robimy nic
8) weszliśmy z prawej strony -> dodajemy: lewa suma +47, węzeł +13
== 3 etap
9) no i na koniec dodajemy najwyższy wierzchołek +6

edytowany 5x, ostatnio: neves, 2019-05-01 15:28

Pozostało 580 znaków

2019-05-01 17:30
0

Dziękuje Ci bardzo!
Udało się.
Jednak coś czuje, że kod nie jest jakiś dobry i można by go skrócić, masz pomysł?
https://pastebin.com/Fsfs3iVW

Nie chodzi mi o sztuczki językowe czy coś, ale może da się jakoś ładniej :D

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0