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

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 ;)

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.

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ł?

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.

0

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

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.

1

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

0

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

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

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