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