steker Evo na primjerima s auditornih, nek me netko ispravi ako je nesto krivo.
Ovisno o tome na kojem cvoru se nalazi linijski segment, toliki raspon na x osi pokriva.
1. zadatak
U ovom slucaju to znaci:
- s1 pokriva 7, <7,19>, [19,28>, [28,51> i 51, ukupno: [7,51]
- s2 pokriva [23,28> i [28,+∞>, ukupno: [23,+∞>
- s3 pokriva [19,28> i 28, ukupno: [19,28]
- s4 pokriva [23,28>, [28,35> i 35, ukupno: [23,35]
- s5 pokriva 16, <16,19>, [19,23> i 23, ukupno: [16,23]
- s6 pokriva <-∞,28>, [28,51>, [51,59> i 59, ukupno: <-∞,59]
Nas u zadatku pita za raspon [17,36] pa oznacimo 17 i 36 na x-osi, dakle znamo:
- 17 se nalazi negdje u <16,19>
- 36 se nalazi negdje u <35,51>
Dalje gledamo koji je ukupni raspon 17 (donja granica) i 36 (gornja granica), a to je <16,51>.
Sad u tom intervalu krecemo od listova preko svih cvorova do korijena, usput zapisemo sve linijske segmente kroz koje smo prosli (bez duplikata) i zadatak je rijesen.
2. zadatak
U iducem zadatku imamo zadano u formatu (raspon x) x (raspon y). Raspon y zanemarujemo, bitan nam je samo raspon x. Sve brojeve iz raspona x (bez duplikata) stavljamo na brojevni pravac i iznad svakog broja nacrtamo list (u ovom slucaju je to 7 listova).
Nakon toga izmedju svakog lista nacrtamo po list (6 listova) i jos na pocetku i na kraju po jedan list (za -∞ i +∞). Ukupno imamo 15 listova i krecemo ih povezivati cvorovima. Povezujemo po 2 lista, ali s obzirom na to da je neparan broj listova 1 list ostane sam. Nakon toga povezujemo po 2 cvora i tu ukljucimo i taj zadnji list. Ponavljamo postupak do dok ne dodjemo do korijena.
I jedino sto nam jos ostaje je upisati gdje ide koji linijski segment. To je zapravo obrnuti postupak nego u 1. zadatku. Mozemo upisivati direktno u cvorove i listove, a ako vam je tesko tako, onda korak po korak pocevsi od listova.
Korak po korak npr. za s1:
- U sve listove koji su uz od 6 do 10 upisujemo s1
- Ako listovi/cvorovi sa s1 imaju zajednicki cvor, brisemo s1 iz listova/cvorova i upisujemo s1 u zajednicki cvor
- Ponavljamo prethodni korak do dok vise nema zajednickih cvorova
NAPOMENA: Iako je u zadatku zadano kao da nisu ukljucene granice (x1,x2), tj. <x1,x2>, ja sam rijesila kao da jesu [x1,x2] jer je na taj nacin pokazano na auditornim vjezbama. Molim ako netko zna da napise rjesava li se uvijek kao da su granice ukljucene ili je to krivo pokazano.
