szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 1 maja 2019, o 12:19 
Użytkownik

Posty: 124
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 ;)
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 1 maja 2019, o 16:04 
Użytkownik

Posty: 66
Lokalizacja: nie wiem
Dobry pomysł,(suma dla poddrzewa z lewej i prawej strony oddzielnie) potem wystarczy sprawdzić dla korzenia R jaki jest w stosunku do przedziału(x,y)

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

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

Co do prawej strony to idziemy tak długo, aż nie znajdziemy wartości większej od 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 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ż 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 y wtedy dla prawej strony sprawdzamy czy syn jest lub nie taki sam jak rodzić, i tak samo dla x.
Góra
Mężczyzna Offline
PostNapisane: 9 maja 2019, o 13:31 
Użytkownik

Posty: 75
Cytuj:
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ć

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 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 S_{(-\inf),y>}. Można to zrobić bardzo łatwo wykorzystując zmodyfikowany algorytm wyszukiwania.

Algorytm wyznaczania S_{(-\inf,x>}
Kod:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 S_{<y,\inf)} oraz zastosować wzór S_{(x,y)} = S - S_{<y,\inf)} -  S_{(-\inf,x>}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Algorytmy][Grafy] Podział grafu na dwa zbiory  matinf  1
 [Algorytmy] rozdzielenie tablicy na dwie względem mediany  gmore  1
 [Algorytmy] Transformata Hougha - obliczenia  Pafcio127  0
 [Algorytmy] Czas działania przy złożoności kwadratowej  Greg102  1
 [C] Sortowanie elementów tablicy rosnąco i malejąco  lobcia  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl