[Algorytmy] Dynamiczny zbiór przedziałów

matematyka464
Użytkownik
Użytkownik
Posty: 459
Rejestracja: 3 lis 2013, o 12:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 208 razy
Pomógł: 1 raz

[Algorytmy] Dynamiczny zbiór przedziałów

Post autor: matematyka464 »

Witajcie,
tym razem mam napisać dynamiczny zbiór przedziałów domkniętych; np: \(\displaystyle{ [2,6...21,001]}\).
Operacje mają działać w czasie logarytmicznym:
\(\displaystyle{ delete (S, I)}\)
\(\displaystyle{ insert (S, I)}\)
\(\displaystyle{ is (S, x)}\)// czy element x należy do jakiegoś przedziału
\(\displaystyle{ intersection (S, I)}\) // czy przedział \(\displaystyle{ I}\) ma niepuste przecięcie z którymś z przedziałów z \(\displaystyle{ S}\)

Może najpierw powiem jak chciałbym się do tego zabrać.
Drzewo AVL, w węźle trzymam oba końce przedziału, maximum z prawych końców przedziałów w poddrzewie. Kluczem jest lewy koniec przedziału.

Kod: Zaznacz cały

insert (S, [a;b], v){
	| wstawianie jak do zwyklego drzewa AVL
	| gdy juz po potencjalnej rotacji, aktualizujemy maxima
	| zakladam, ze max_p (NULL) = -INF
	v.max_p = max (v.max_p, max_p(lewy(v), max_p(prawy(v));
}

delete (S, [a;b], v){
	| usuwanie tak samo jak zwykle AVL
	| po potencjalnej rotacji aktualizujemy maxima
	v.max_p = max (v.max_p, max_p(lewy(v)), max_p(prawy(p)));
}

is (S, x, v){
	if v.a <= x && v.vb >= x then
		return YES;
	else if is_leaf (v) then return NO
	
	if x >= v.a then
		if x <= max_p(lewy(v)) then
			return YES;
		else
			if !is_leaf (v) then
				return is (S, x, prawy(v));
			else
				return NO;
	else
		return is (S, x, lewy(v));
}


intersetction (S, [a;b], v){
	if v = NULL then
		return NO;
	if [a;b] ma niepsute przecięcie z [v.a;v.b] then
		return YES;
	if v.b < b then
		return intersection (S, [a;b], prawy (v));
	else
		return intersection (S, [a;b], lewy (v));

}
Ostatnio zmieniony 30 gru 2014, o 18:27 przez Afish, łącznie zmieniany 1 raz.
Powód: Kod umieszczaj w znacznikach code.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

[Algorytmy] Dynamiczny zbiór przedziałów

Post autor: norwimaj »

Czy treść należy rozumieć dosłownie, tzn. mamy reprezentować zbiór przedziałów i nic nie wiadomo na temat ich rozłączności? Inny sposób rozumienia treści (trochę naciągany) to taki, że reprezentujemy zbiór będący sumą przedziałów domkniętych.
matematyka464
Użytkownik
Użytkownik
Posty: 459
Rejestracja: 3 lis 2013, o 12:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 208 razy
Pomógł: 1 raz

[Algorytmy] Dynamiczny zbiór przedziałów

Post autor: matematyka464 »

Ten pierwszy sposób, ten drugi zbyt naciągany
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

[Algorytmy] Dynamiczny zbiór przedziałów

Post autor: norwimaj »

Błąd masz w liniach 37--38. Podobnie jak w funkcji is, tak i tu należy uwzględnić przedziały z lewego poddrzewa, sięgające daleko w prawo.
matematyka464
Użytkownik
Użytkownik
Posty: 459
Rejestracja: 3 lis 2013, o 12:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 208 razy
Pomógł: 1 raz

[Algorytmy] Dynamiczny zbiór przedziałów

Post autor: matematyka464 »

Faktycznie jest błąd. Poprawka:

Kod: Zaznacz cały

intersetction (S, [a;b], v){
   if v = NULL then
      return NO;
   if [a;b] ma niepsute przecięcie z [v.a;v.b] then
      return YES;
   if max_p(lewy(v))  >= a then YES
   else return intersection  (S, [a;b], prawy (v));
}
I po raz kolejny. Zapnij pasy i sprawdź proszę warunki końca. is_leaf(x) = true wtw gdy x nie ma synów, ale sam jest poprwanym węzłem (ma klucz)
Ostatnio zmieniony 2 sty 2015, o 01:14 przez matematyka464, łącznie zmieniany 1 raz.
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

[Algorytmy] Dynamiczny zbiór przedziałów

Post autor: Zordon »

W Cormenie jest opisane jak to zrobić przez wzbogacenie drzewa czerwono-czarnego. Z AVL da się analogicznie
matematyka464
Użytkownik
Użytkownik
Posty: 459
Rejestracja: 3 lis 2013, o 12:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 208 razy
Pomógł: 1 raz

[Algorytmy] Dynamiczny zbiór przedziałów

Post autor: matematyka464 »

Generalnie wydaje mi się nawet, że każde wzbogacenie, które można wykonać na AVL można na RBT i tak samo w drugą stronę. Spodziewam się, że ten wątek też może Ciebie zainteresować :)
378211.htm
ODPOWIEDZ