Objedninjenje nizova i listi

Objedninjenje nizova i listi 30.10.2006. u 13:48 · pre 243 meseca #1

Da li neko zna algoritam preko koga se može ostvariti tip koji objedinjuje svojstva listi i nizova u smislu da se može elementima pristzpati preko indeksa (ali u logaritamskom vremenu, ne u konstantnom kao kod nizova) a da se umetanje sadržaja u sredinu (kao i vađenje sadržaja iz stringa) vrše takođe u logaritamskom vremenu?

Primer:

Razmotrimo nizove znakova (stringove).

U stringu "kojim" se slovo "m" nalazi na petom mestu. Kada se ivadi podstring "oj" dobija se string "kim" kod koga je slovo "m" na trećem mestu.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Objedninjenje nizova i listi 30.10.2006. u 13:56 · pre 243 meseca #2

Binarno stablo bi moglo da radi ono shto ti zelish ...

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Re: Objedninjenje nizova i listi 30.10.2006. u 17:28 · pre 243 meseca #3

Ako hoces i nesto gotovo da probas u c++-u onda je std::map (skoro) jedino resenje.

Potpis

AKA DDMM

Re: Objedninjenje nizova i listi 30.10.2006. u 18:00 · pre 243 meseca #4

Vec ti je odgovoreno, resenje koje bi ti verovatno odgovaralo je binarano stablo gde je vreme ubacivanja i pristupa podatku "uglavnom" log(n).
Ali, kako u obicnom binarnom stablu, najgori slucaj moze da bude vreme n za ubacivanja i pristup podataka (u najcescim implementacijama to bi se dogodilo kada bi se ubacivao, po odgovarajucem kriterijumu za te podatke, sortirani niz, iako opet u tom slucaju mozes da primenis binarno pretrazivanje trebao bi da znas kada je niz koji se ubacuje sortiran a kada nije), mozda bi umesto njega hteo da razmotris upotrebu balansiranih binarnih stabala.

Re: Objedninjenje nizova i listi 30.10.2006. u 21:08 · pre 243 meseca #5

Rekao bih da niste u pravu. Stablo ima osobine listi, ali ne i nizova. Neka imam stablo sa 10⁷ članova. Kako da nađem u njemu milioniti član "sleva udesno" u stablu u logaritamskom vremenu?

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Objedninjenje nizova i listi 30.10.2006. u 21:27 · pre 243 meseca #6

Pamtish dodatnu informaciju za svaki cvor koja ce ti reci koliko ima cvorova u njegovom podstablu.

recimo da trazish N-ti chlan niza.

Code:

trazi(cvor c, int N){
  if (c.levo.brojSinova < N){
    if (c.levo.brojSinova==N-1) trazeni_cvor=c;
    else trazi(c.desno,N-1-c.levo.brojSinova);
  }
  else trazi(c.levo,N);
}

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Re: Objedninjenje nizova i listi 30.10.2006. u 23:10 · pre 243 meseca #7

Nedeljko, ili ti nisi razumeo moj odgovor ili ja nisam razumeo tvoje pitanje :)
Bolje da prikazem graficki:

Code:

       5                Balansirano binarno stablo ili nebalansirano
     /   \\              binarno stablo u najboljem slucaju.
    3     8             Da bi se pronasao broj 7 vrse se 3 poredjenja.
   / \\   / \\            Vreme pristupa je log2(n).
  2   4 7   9
/           \\
1             10

1                       Nebalansirano binarno stablo u najgorem
\\                      slucaju, npr. kada se u odredjenoj implementaciji
  2                     ubacuje redom sortirani niz od najmanjeg ka vecem
   \\                    gde se prvo proverava da li je podatak koji se
    3                   ubacuje veci od trenutnog a tek onda ako nije da li
     \\                  je manji ili jednak.
      4                 Da bi se pronasao broj 7 vrse se 7 poredjenja.
       \\                Vreme pristupa je n.
        5
         \\
          6
           \\
            7
             \\
              8
               \\
                9
                 \\
                  10

|1|2|3|4|5|6|7|8|9|10|  Obican niz ili lista.
                        Da bi se pronasao broj 7 vrse se 7 poredjenja.
                        Vreme pristupa je n.

Citat:

Neka imam stablo sa 107 članova. Kako da nađem u njemu milioniti član "sleva udesno" u stablu u logaritamskom vremenu?

Ako bas hoces da koristis niz i da clanovima niza pristupas u logaritamskom vremenu, onda niz mora da bude sortiran i da se koristi binarno pretrazivanje (npr. ako je niz sortiran od manjeg ka vecem, podelis niz na pola, ako je podatak koji se trazi jednak trenutnom pretrazivanje se prekida jer je odgovarajuci clan pronadjen, ako je podatak veci od trenutnog clana trazi se u desnoj polovini niza u suprotnom trazi se u levoj polovini nizi, ovo se ponavlja dok se ne pronadje clan koji je jednak podatku koji se trazi ili dok ne preostane samo jedan neodgovarajuci clan koji naravno ne moze dalje da se deli).

Ako ti je ovo isuvise strano, predlazem ti da prvo procitas neku knjigu o algoritmima i strukturama podataka.

Re: Objedninjenje nizova i listi 30.10.2006. u 23:47 · pre 243 meseca #8

Milane, nisi ga razumeo shta hoce.

Dakle, ono shto on zeli je sledece :
kada se to stablo rastavi (i dobije se nekakav niz), zeli da zna koji elemenat je na N-tom mestu. Pazi, niz koji dobijesh ne mora da bude sortiran po vrednosti!!!

U stvari, ono po chemu se ova nasha struktura razlikuje od klasichnog binarnog stabla pretrazivanja je to shto ne postoji kljuch po kom poredimo vrednosti!

Ako nekom nije jasno shta sam hteo da kazem, potrudicu se da malo pojasnim (da ne kucam inache u prazno ako je svima jasno shta je pisac hteo da kaze) :)

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Re: Objedninjenje nizova i listi 31.10.2006. u 00:00 · pre 243 meseca #9

E sada mi jasno sta je hteo, ali ne iz tvoje poslednje poruke :) nego iz primera u tvojoj predposlednjoj poruci, koji sam ovoga puta malo bolje pogledao :)

Re: Objedninjenje nizova i listi 31.10.2006. u 00:16 · pre 243 meseca #10

Da, moj poslednji post je katastrofalno nejasno napisan :)

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Re: Objedninjenje nizova i listi 31.10.2006. u 14:55 · pre 243 meseca #11

Citat:

RooTeR: Pamtish dodatnu informaciju za svaki cvor koja ce ti reci koliko ima cvorova u njegovom podstablu.[/code]

Znam da je dovoljno pamtiti broj čvorova u levom podstablu. Međutim, tu nastaje problem prilikom umetanja i brisanja. Naime, te informacije u čvorovima treba ažurirati prilikom umetanja i brisanja, a broj čvorova kod kojih bi ažuriranje bilo potrebno zavisi linearno od ukupnog broja čvorova. Zbog ažuriranja tih dodatnih informacija vreme umetanja i brisanja ne bi više bilo logaritamsko, već linearno.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Objedninjenje nizova i listi 31.10.2006. u 18:08 · pre 243 meseca #12

Citat:

Nedeljko: Znam da je dovoljno pamtiti broj čvorova u levom podstablu. Međutim, tu nastaje problem prilikom umetanja i brisanja. Naime, te informacije u čvorovima treba ažurirati prilikom umetanja i brisanja, a broj čvorova kod kojih bi ažuriranje bilo potrebno zavisi linearno od ukupnog broja čvorova. Zbog ažuriranja tih dodatnih informacija vreme umetanja i brisanja ne bi više bilo logaritamsko, već linearno.

Ne, broj cvorova koje treba azurirati je log N!
jer kad ubacish neki novi cvor, menjacesh informaciju samo njegovim prethodnicima, a njih ima log N ...

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Re: Objedninjenje nizova i listi 31.10.2006. u 21:22 · pre 243 meseca #13

To bi bilo tako kada ne bi trebalo ažurirati informaciju o broju čvorova levo od datog čvora. Znam ja za razne vrste balansiranih stabala, kao i da ona imaju logaritamske karakteristike nalaženja, umetanja i brisanja, ali ovde čvor nosi još jednu informaciju koju treba ažurirati.

Pretpostavimo da kada u drvo d dodajemo na m-to mesto (sleva udesno) element x dobijamo drvo d'. Sa c1,...,cn označimo niz koji se dobija od drveta d (komp ga naravno neće generisati, ovo je samo oznaka). Tada drvetu d' odgovara niz c1,...,cm-1,x,cm,...cn. Za k>=m je u prvom nizu ck imao k-1 prethodnika, a u novom k. To znači da se za k>=m informacija o broju čvorova levo od čvora koji odgovara elementu ck povećala za jedan, to jest da tu informaciju treba ažurirati u svim čvorovima cm,...,cn, a njih ima n-m+1.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Objedninjenje nizova i listi 31.10.2006. u 22:05 · pre 243 meseca #14

Nisi u pravu!

Recimo da imash ovakvo stablo :

Code:

         x3
        /  \
      x2   x5
     /    /  \
   x1    x4  x6

i ona predstavlja niz : x1, x2, x3, x4, x5, x6

E sad, ti zelish da na trece mesto ubacish elemenat E.
Dakle, niz ce izgledati ovako : x1, x2, E, x3, x4, x5, x6

a stablo ce izgledati ovako :

Code:

         x3
        /  \
      x2    x5
     /  \  /  \
   x1   E x4  x6

E sad, kad ti to E ubacish na svoje mesto, koje cesh cvorove morati da azurirash?
x2 i x3.
x4, x5 i x6 necesh biti potrebe da se azuriraju, jer E nije njihov potomak, pa samim tim i ne utiche na broj cvorova u njihovom podstablu.
Dakle, potrebno je azurirati samo one cvorove u cijem se podstablu nalazi novoubaceni cvor (a takvih cvorova ima log N)!

Mislim da je jednostavnije da se za svaki cvor pamti kompletna velicina njegovog podstabla, a ne samo velicina njegovog levog podstabla!

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Re: Objedninjenje nizova i listi 01.11.2006. u 01:29 · pre 243 meseca #15

Mislim da vam je potrebno neshto kao kolekcija binomnih stabala...imaju dobru osobinu shto uvek znate koliko elemenata se nalazi u datom binomnom stablu(ako je stablo reda k,onda stablo ima 2^k elemenata),a dodavanje se vrshi u O(log n) vremenu gde je n broj chvorova u kolekciji.Ne znam bash sve pojedinosti ali mislim da je ovo ono shto moze da zadovolji vashe potrebe.

Evo i slike kako otprilike izgledaju binomna stabla stepena 0,1,2 i 3...

Mladen.

Re: Objedninjenje nizova i listi 01.11.2006. u 08:38 · pre 243 meseca #16

RooTeR

Sada sam te razumeo. Ja sam mislio da u svakom čvoru pamtim broj svih čvorova levo od njega (nezavisno od toga da li su mu u levom podstablu ili ne). Tako bi u tvom primeru po mojoj definiciji x1 bio levo od x6 i tada bih morao da ažuriram x3-x6 jer bi npr. x6 nakon umetanja bio sedmi po redu, a pre umetanja šesti po redu. Međutim, ako u čvoru pamtiš broj čvorova u njegovim podstablima, onda zaista treba ažurirati samo čvorove na grani umetnutog čvora. Time je problem rešen. Hvala.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Objedninjenje nizova i listi 01.11.2006. u 14:33 · pre 243 meseca #17

@Nedeljko:

Molim i drugi put! :)

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Forum kao aplikacija na telefonu

Srodne teme