Strukture za sve

silencer · **Poslato:** 04.05.2008. 15:20:41

Da znam kako aplet brise, on bi u ovom stablu gde sam dodao 60, koren zamenio sa 35 a mnogo bi lepse bilo da se zameni sa 60 jer bi razlika u visinama bila 0 za svaki cvor.

Kod:

              55
            /     \
         33        70
        /   \     /   \
      20    35   66   80
                /
               60

Nego jel moze neko da mi resi ovaj zadatak:

Kod:

 Pokazati postupak formiranja B stabla celih brojeva reda 2 (ima dva elementa u cvoru), kada se u prazno stablo ubacuju elementi 107, 174, 20, 35, 27, 55, 1, 18, 89, a zatim iz dobijenog stabla izbace elementi 18, 55 i 35. svaki korak svake operacije posebno nacrtati! (13 poena)

Ne znam sta se radi kad je stablo reda 2, znaci ima samo jedan kljuc u cvoru i dva pokazivaca. Sta se radi kada se na 107 ubaci 174, po pravilu bi trebalo da se razdvajaju u dva cvora a da "srednji" kljuc ode u oca. Ovde nema srednjeg kljuca? Help!

Ima li neko link ka apletima za B* i B+ stabla?

silencer · **Poslato:** 04.05.2008. 19:02:27

Shvatio sam u cemu sam gresio:

"Balansirano višegransko stablo traženja reda n+1 u kome svaki čvor različit od korena sadrži najmanje n div 2 ključeva se naziva B-stablo reda n"

Znaci onaj prethodni zadatak gore je u stvari B stablo u kojima cvorovi mogu da imaju maksimalno 3 podstabla a svaki cvor moze da ima max 2 kljuca.

silencer · **Poslato:** 04.05.2008. 21:36:18

Evo da podelim sa vama ono na sta sam naisao sto nije objasnjeno u skripti (ili ja bar nisam nasao):

Dato je ovo B stablo:

Kod:

                             21
                     /                \
                  13                   35,50
                 /   \                /  |   \
               10      15           25  45    70

Brisanjem kljuca 13 dobija se ovo:

Kod:

                             21
                     /                \
                  10,15                 35,50
                                      /  |   \
                                    25  45    70

Ali to stablo vise nije balansirano i onda treba da se uradi ono sto ja nisam nasao u skripti a to je da se uzima kljuc sa one strane gde je visina veca (35) i postavlja se u oca a otac postaje njegov levi sin i preuzima bivseg levog sina od novog oca (25)(slicno kao kod AVL stabla).

Kod:

                             35
                     /                \
                  21                     50
                 /   \                /     \
              10,15   25             45      70

Tako sam ja bar shvatio iz apleta. Moze da posluzi ljudima koji nisu isli na vezbe.

silencer · **Poslato:** 04.05.2008. 22:13:47

A sta se desava kada ne moze da pozajmi kljuc:

Kod:

                             21
                     /                \
                  13                     50
                 /   \                /     \
              10      15             45      70

Izbacuje se 13, ostane ovo:

Kod:

                             21
                     /                \
                 10,15                   50
                                      /     \
                                     45      70

Da bi se izbalansiralo proba se pozajmica kao u pretnodnom primeru, ako je pozajmica nemoguca jednostavno sin dolazi u oca:

Kod:

                            21,50
                     /        |       \
                  10,15      45         70
                           
             

Jel mi dobar monolog

Ima li jos neko da polaze sad u sredu ili sam ja jedini?

bizzare_masta · **Poslato:** 06.05.2008. 11:06:35

polazem i ja ali nemam pojma o cemu ti ovo govoris. Komplikovani su ti ovi primeri, ne znam iz kog roka si ih izvadio.

Umes li da resis ovaj primer koji si postavio?

Kod:

 Pokazati postupak formiranja B stabla celih brojeva reda 2 (ima dva elementa u cvoru), kada se u prazno stablo ubacuju elementi 107, 174, 20, 35, 27, 55, 1, 18, 89, a zatim iz dobijenog stabla izbace elementi 18, 55 i 35. svaki korak svake operacije posebno nacrtati! (13 poena) 

Uspem da ubaci sve, ali izbacivanje je pravi problem.

silencer · **Poslato:** 06.05.2008. 11:47:01

E pa vidis, izbacivanje je problem jer nisu to lepo do tancina objasnili.

Primeri su izvuceni iz ove teme, ne znam tacno iz kog roka je bilo. Ovo gore sto sam objasnio su situacije do kojih se dolazi resavanjem skoro svakog zadatka. Recimo ovaj zadatak:

Ubaciti u B stablo kljuceve 50,70,15,25,21,35,10,13,45 pa izbaciti 13,35,25.

Resi ovaj zadatak pomocu apleta:
http://slady.net/java/bt/view.php?w=800&h=600

i posmatraj sta se desava u situaciji kada se izbacuje 13. To je isti primer kao onaj gore prvi.

A u ovom tvom zadatku zameni privremeno da ti je recimo 107=93 a 174=96 i sa tim vrednostima (ispod 100 jer aplet nece da radi sa vecim) ih guraj u aplet i vidi kako se resava. Bitno je samo da budu u istoj proporciji. Na kraju vrati originalne vrednosti i to ti je resen zadatak.

silencer · **Poslato:** 06.05.2008. 12:12:47

Evo sad sam pogledao ovaj tvoj zadatak i u situacijama kada se izbacuju 18 i 55 imas potpuno iste situacije objasnjene gore a iskoristi aplet pa vidi sam.

silencer · **Poslato:** 06.05.2008. 15:03:58

E ljudi zna li neko u kom kabinetu sutra polazemo jer u rasporedu ne pise nista, samo pise da je usmeni u 201? Verovatno i pismeni?

intermezzo · **Poslato:** 06.05.2008. 15:53:16

pismeni iz marta I grupa:

1. Kada je algoritam kompleksnosti O(n) onda to znaci? (ponudjeni odgovori)(10p)

2. AVL (korak po korak) 25,35,40,10,15,5,80,100(15p)

3. B* stablo (standardno ubacivanje i izbacivanje)(15p)

4. Dat je pokazaivac na koren binarnog stabla ciji cvorovi sadrze cele brojeve i drugi pok na neki cvor u stablu. Napisati f-ju koja ce otstampati sve cvorove koji su na putanji od korena do datog cvora, ukljucujucu i ta dva cvora.(25p)

5. Dat je stek celih brojeva implementiran kao 2-struko spregnuta ciklicna lista. Napisati metodu koja implementira algoritam za ubacivanje novog cvora na vrh staka.(15p)

6. Dati su pokazivaci Glava, koji pokazuje na prvi element 1-dnostruko spegnute liste celih brojeva, i pokazivac Tekuci koji pokazuje na neki element liste. Napisati metodu koja ce izbaciti iz liste element koji je predhodnik elementa na koga pokazuje Tekuci, ako takav element postoji.(20p)

Sretno :cupavi:

intermezzo · **Poslato:** 06.05.2008. 15:55:46

moze li neko napisati kod za 6-ti zadatak.
Hvala unapred :yo:

silencer · **Poslato:** 06.05.2008. 16:35:56

6.

Kod:

public static Cvor Izbaci(Cvor glava, Cvor tekuci)
{
   if (tekuci==glava)
        return null;
   Cvor tmp=glava;
   Cvor tmp1=null;
   while(tmp.next!=tekuci)
      { 
          tmp1=tmp;
          tmp=tmp.next;

       }

    tmp1.next=tekuci;
    return tmp;
}

intermezzo · **Poslato:** 06.05.2008. 17:30:42

silencer, ljudina si

izvini sto te smaram, ali mozes li i 4-ti da odradis nesto sam pokusao ali ne ide

Tnx

silencer · **Poslato:** 06.05.2008. 18:52:54

4.

Kod:

public static void StampajDoCvora(Cvor koren, Cvor cvor)
{
  Cvor tmp=cvor;
  while(VratiRoditelja(koren,tmp)!=null)
       {System.out.println(tmp.data);
        tmp=VratiRoditelja(koren,tmp);
       }
   
 }

public static Cvor VratiRoditelja(Cvor koren,Cvor cvor)
{
   if (koren==null)||(koren==cvor) return null;
   if (koren.levi==cvor||koren.desni==cvor)
        return koren;
   if (VratiRoditelja(koren.levi,cvor))!=null) return VratiRoditelja(koren.levi,cvor);
   if (VratiRoditelja(koren.desni,cvor)!=null) return VratiRoditelja(koren.desni,cvor);
   return null;
}
 

EDIT: sad bi trebalo da je ok , stampa od cvora do korena

silencer · **Poslato:** 06.05.2008. 19:16:27

4.

Kod:

public static void StampajDoCvora(Cvor koren, Cvor cvor)
{
  Cvor tmp=cvor;
  Cvor pom;
  if(VratiRoditelja(koren,tmp)!=null)
    { 
       pom = tmp;
       StampajDoCvora(koren,VratiRoditelja(koren,tmp);
       System.out.println(pom);
     }
  else return;
 }

public static Cvor VratiRoditelja(Cvor koren,Cvor cvor)
{
   if (koren==null)||(koren==cvor) return null;
   if (koren.levi==cvor||koren.desni==cvor)
        return koren;
   if (VratiRoditelja(koren.levi,cvor)!=null) return VratiRoditelja(koren.levi,cvor);
   if (VratiRoditelja(koren.desni,cvor)!=null) return VratiRoditelja(koren.desni,cvor);
   return null;
}
 

EDIT: Trebalo bi da je ok , stampa od korena do cvora.

silencer · **Poslato:** 07.05.2008. 11:25:38

Majski rok I grupa:

Poz!

bizzare_masta · **Poslato:** 07.05.2008. 18:47:46

ne znam kako se vama cini, ali ovaj majski rok je bio bas laganica. Sva sreca pa sam iskoristio ovu priliku da skinem ovaj nezgodan ispit.

intermezzo · **Poslato:** 08.05.2008. 21:05:17

....slazem se sa bizzare_masta jer je rok bio ok. :cupavi:

Silenceru jesi li ti skinuo strukture sa vrata???

silencer · **Poslato:** 20.05.2008. 11:56:34

Da overio sam 9

bizzare_masta · **Poslato:** 20.05.2008. 14:03:34

zna li neko Kostin mejl?
jer ovaj:
dimitrijevic.kostandin@fon.bg.ac.yu

ili sam promasio.
Hvala

smucka · **Poslato:** 19.06.2008. 18:59:51

Kod:

// izbacivanje elementa sa pocetka liste (izbacivanje prvog)
   public int IzbaciSaPocetka()
   {
      if (Prvi != null)
      {
         int a = Prvi.Podatak;
         Prvi = Prvi.Sledeci;
         return a;
      }
      return Integer.MAX_VALUE;
   }

Jel zna neko zasto je ovde za povratni tip metode stavljeno int ???
Ovo je zvanican kod skinut sa sajta..

markom · **Poslato:** 19.06.2008. 19:05:54

Stavljeno je int da bi ti metoda vratila vrednost koja se nalazila u prvom elementu liste koji sada hoces da izbacis. Vrednost cvora zapamtis u promenjivoj a i onda je vratis sa return a. Npr. u test klasi mozes da stavis: System.out.Println("Izbacen je cvor sa vrednoscu " + IzbaciSaPocetka()); i ova linija koda ce ti izbaciti prvi i vratiti koja je vrednost tog izbacenog.

Raaaa · **Poslato:** 19.06.2008. 19:28:30

Jel rekao Kosta sta treba du ce iz teorije oni koji nemaju domace??? Nije valjda d amoram sve one kodove iz skripti da znam :aaa:

smucka · **Poslato:** 19.06.2008. 19:49:02

^^
ali generalno nije greska ako se navede da je tip void?

^
pogledaj rokove od prosle godine: junski, septembar, okt, okt2 i na forumu (tema: strukture za sve, stranica: 23 il 24) imas januar i februar od ove godine..videces da ne moraju kodovi umesto domaceg da se uce! uglavnom su teoretska pitanja!! Lepo je odvojeno, cetvrto i osmo pitanje menjaju I i II domaci....

markom · **Poslato:** 19.06.2008. 19:55:55

Bolje je da odradis ovako kako su oni stavili na sajtu jer ako u listi nemas prvi cvor tj. ako je lista prazna a ti hoces da obrises prvi, onda ce ti ova metoda vratiti Integer.MAX_VALUE odnosno veliki broj i onda ces znati da nemas prvi u listi.

smucka · **Poslato:** 19.06.2008. 20:34:52

Kod:

public void UbaciNaPocetak(int Podatak)
   {
      CvorDSListe novi = new CvorDSListe(Podatak, null, Prvi);
      Prvi = novi;
      if(novi.Sledeci == null) // kreiran je prvi element -> postavi da je on i poslednji
         Poslednji = novi;
      else
         novi.Sledeci.Prethodni = novi;
   }

OK hvala na pomoci..al jos samo malo..nisam pratio prvi deo semestra pa ne znam cake..
Koja je svrha poslednjeg reda u ovom kodu??

FONForum

Strukture za sve

Ko je OnLine