konverzija jednostruko povezane liste u binarno stablo...

konverzija jednostruko povezane liste u binarno stablo... 20.02.2010. u 22:17 · pre 203 meseca #1

Moze li neko da me uputi kako da realizujem stablo koje sadrzhi elemente lancane liste, ali tako da se svi elementi predstave kao listovi stabla, dok cvorovi pokazuju na ukupan broj elemenata u podstablu datog chvora ali samo u levoj grani, te se do elementa liste dolazi preko datih chvorova stabla po principu, ako je trazena pozicija eleemnta manja ili jednaka od vrednosti cvora, idemo levo, inace umanjujemo poziciju za vrednost kljucha datog chvora i idemo desno.

Pretrazio sam po netu i nigde ne mogu da nadjem resenje, tj algoritam kojim se na ovakav nachin prevodi lista u stablo, molim za pomoc.

lista je jednostruko povezana.

primer:

Code:

lista: A -> B -> C ->D -> E -> F

nakon prevodjenja dobijamo ovo:

                     4
                    /\
                   /  \
                  /    \
                 2      1
                / \    / \
               /   \   E  F
              /     \
             1       \
            / \       \1
           /   \      /\
          /     \    /  \
         A       B  C   D

Re: konverzija jednostruko povezane liste u binarno stablo... 21.02.2010. u 12:42 · pre 203 meseca #2

Uspeo sam neshto, ali ne umem da dokazhem matematicki.

Mislim da bi moglo da se reshi ako znamo visinu stabla, ako uzmemo da je koren stabla:

Code:

2^int(log(n)/log(2))

pod uslovom da je log(n)%log(2) nije jednako nula,

a ako jeste onda se uzima da je koren 2^(log(n)/log(2)-1),

cime dobijamo potpuno stablo.

Dakle to je koren, a onda rekurzivno idemo inorder metodom prvo kroz levo podstablo a onda kroz desno, s tim da se za desno radi malo drugacije, chvor koji sledi imace kljuch (ukupno-koren)/2 pod uslovom da je to upravo prvo desno dete root elementa.
Nadam se da neko ima kvalitetnije resenje.

Re: konverzija jednostruko povezane liste u binarno stablo... 21.02.2010. u 23:52 · pre 203 meseca #3

Postoji više od jednog rešenja. Recimo za slučaj {A, B, C, D, E, F} i ovo su ispravna stabla:

Code:

   1                        5
  / \                      / \
A   1                    4   F
    / \                  / \
   B   1                3   E
      / \              / \
     C   1            2   D
        / \          / \
       D   1        1   C
          / \      / \
         E   F    A   B

Da li tebi treba balansirano stablo?

Re: konverzija jednostruko povezane liste u binarno stablo... 22.02.2010. u 06:21 · pre 203 meseca #4

Pravi razliku između binarnih drveta i binarnih za pretraživanje. Ova druga dalje mogu biti balansirana na razne načine (AVL, RB, itd.). Na Wikipediji mozes naći uputstva, za detalje uzmi neku knjigu:
http://en.wikipedia.org/wiki/Binary_tree
http://en.wikipedia.org/wiki/Binary_search_tree
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
http://en.wikipedia.org/wiki/AVL_tree
http://en.wikipedia.org/wiki/Red-black_tree

Potpis

Sveti Avgustin: "Dobar hrišćanin treba da se kloni matematičara i svih onih koji daju lažna proročanstva. Postoji opasnost da su matematičari već sklopili pakt sa Đavolom, da pomrače čovekov um i da ga okuju okovima pakla."

Re: konverzija jednostruko povezane liste u binarno stablo... 22.02.2010. u 12:15 · pre 203 meseca #5

Citat:

Mihajlo Cvetanović: Postoji više od jednog rešenja. Recimo za slučaj {A, B, C, D, E, F} i ovo su ispravna stabla:

Code:

   1                        5
  / \                      / \
A   1                    4   F
    / \                  / \
   B   1                3   E
      / \              / \
     C   1            2   D
        / \          / \
       D   1        1   C
          / \      / \
         E   F    A   B

Da li tebi treba balansirano stablo?

ako se ne varam na ovaj nachin koji si predstavio dobili bi samo heap? ili greshim? To jeste ispravno ali nije ono shto se zahteva, dakle potrebno je formirati stablo minimalne visine. Dakle nije stablo pretrazivanja, nije AVL, dakle jedno je sigurno, uvek ce da naginje na levu stranu, jer se uvek prvo puni leva, osim ako nije potpuno.

Idemo tako da su listovi sa leva na desno elementi liste (1,2,3...) tako da ako imamo u listi npr 6 elemenata, kao ona skica gore, onda se utvrdi da li log(6) mod log(2) daje ostatak, a posto daje primenjuje se da je koren element koji se nalazi na poziciji 2^int(log(6)/log(2))=2^2=4.

dok je visina stabla odredjena kao int(log(6)/log(2)) +1= 3.

te je maksimalni broj chvorova u stablu sa 3 nivoa 2^3=8. To dakle znaci da smo postigli cilj, jer smo upotrebili stablo minimalne visine i poredjali elemente liste. Prednosti su naravno ogromne kod pretrazivanja vezanih lista koje imaju duzine par desetina hiljada elemenata, jer je vremenska kompleksnost logoritamska. Za 10 000 podataka bice visna stabla log(10000)/log(2)+1 = 14, dakle nama je potrebno stablo visine 14 i tu mozhemo da smestimo oko 16 000 eleemnata, dok sa visinom 13 samo oko 8000, te je ocigledno slaba izbalansiranost, ali ovde to i nije cilj.

Re: konverzija jednostruko povezane liste u binarno stablo... 22.02.2010. u 13:16 · pre 203 meseca #6

Hm, hm, znači ovako nekako:

Algoritam ide od početka liste i "jede" elemente praveći podstablo. To podstablo je veličine podstabla koje je stvoreno u prethodnom koraku. Dva podstabla se spajaju u novo podstablo, i sve počinje iz početka.

U tvom primeru prvo se pravi podstablo A (visine 1). Zatim se pravi podstablo B i spaja s postojećim u (A,B) (visine 2). Zatim se pravi (C,D) i spaja s postojećim u ((A,B),(C,D)) (visine 3). Zatim se pravi novo, od preostalih elemenata, (E,F) i spaja s postojećim u krajnje stablo (((A,B),(C,D)),(E,F)).

Slutim da bi tu mogla neka rekurzija da se uradi, jer se svako podstablo pravi na identičan način. Ulaz rekurzivne funkcije je visina stabla i iterator niza. Ako je visina nula onda vraćamo sledeći element niza kao najmanje moguće stablo. Ako nije nula onda pozivamo funkciju dva puta rekurzivno, sa dekrementiranom visinom, i rezultate spajamo u novo stablo koje vraćamo.

Da bi se sve lepo zarolalo potrebna je i jedna kontrolna funkcija koja gradi stablo postepeno. Početni parametar glavne petlje kreće od nule i inkrementira se u svakom koraku. Petlja se izvršava sve dok ima elemenata niza, a u petlji pozivamo rekurzivnu funkciju i rezultat spajamo s onim što već imamo.

Znači glavna funkcija radi iterativno, a pomoćna radi rekurzivno, ali obe spajaju dva podstabla u novo podstablo. Kad više nema elemenata to podstablo je u stvari rezultujuće stablo.

Ovaj algoritam nije baš elegantan, jer imamo dve funkcije koje rade sličan posao, ali ovo je na prvu loptu. Verovatno ima i elegantnije rešenje.

Uzgred, rezultat rekurzivne funkcije treba da bude par podataka, pointer na novo podstablo, i broj elemenata u podstablu. Ovaj broj elemenata može da se računa, ali efikasnije je da se kešira (a treba ti taj podatak). Drugim rečima rekurzivna funkcija ima sledeći potpis: std::pair<Stablo*,int> rekurzivna_funkcija(int visina, Lista*).

Re: konverzija jednostruko povezane liste u binarno stablo... 22.02.2010. u 17:38 · pre 203 meseca #7

evo probacu da demonstriram pseoudo kodom:

Code:

koren=new ChvorStabla;

kljuch= log(lista->getUkupno())%log(2) == 0 ? 2^(log(lista->getUkupno())/log(2)-1) :  2^(log(lista->getUkupno())/log(2));

koren->kljuch=kljuch;

generishi(&koren,&lista);

void generishi(ChvorStabla **trenutni_chvor, ChvorListe **lista){

    if (*trenutni_chvor == null) return; //ako nema korena STOP

    if(*trenutni_chvor->kljuch == 1) { //ako smo stigli do nivo lista idemo sa kacenjem levog elementa


        //korak 1: kachimo na levi list vrednost sa vrha steka i bukvalno prelazimo na korak 2:
        *trenutni_chvor->levi = kreirajCvhro(*lista->pop());

    }else { //ako trenutni nivo nije 1 silazimo rekurzivno kroz levu granu i kachimo chvorove

        *trenutni_chvor->levi=kreirajCvhro(*trenutni_chvor->kljuch/2);
        *trenutni_chvor = *trenutni_chvor->levi;

        generishi(trenutni_chvor,lista);

    }
    //nakon shto smo kreirali levu granu trenutnog stabla/podstabla prelazimo na kreiranje desne
    //ili ako je koren jednak jednici kachimo odmah jedan element sa vrha steka ulanchane liste

    if(*trenutni_chvor->kljuch == 1){

                //ako smo stigli na nivo lista u stablu kachimo i desno dete
                //(element iz ulanchane liste koji je trenutno na vrhu steka),
                //a ako je stek kojim sluchajem prazan kachi se 0
                //kachimo element liste na desni list stabla i ponishtavamo i "ponishtavamo"
                //trenutni rekurzivni poziv izlaskom iz funkcije te se vracamo jedan nivo navishe
        *trenutni_chvor->desni = kreirajCvhro(*lista->pop());

        return;

    }else if(*trenutni_chvor->otac != null){
                // ako dati element nije koren onda
                //primenjujemo klasichno deljenje
                //vrednosti kljucha sa 2 i kreiramo desni chvor

        *trenutni_chvor->desni=kreirajCvhro(*trenutni_chvor->kljuch/2);
        *trenutni_chvor = *trenutni_chvor->desni;

        generishi(trenutni_chvor,lista);

    }else{

    // ali ako jeste u tom sluchaju treba od ukupnog broja elemenata u
    // listi oduzeti kljuch korena, tj ukupan broj chvorova u levoj grani,
    // te samim tim dobijamo preostale koje treba da nakachimo, medjutim mozhe se
    // desiti da je to neparan broj te u tom sluchaju dodajemo jedan element kako bi
    // smo doshli do broja deljivog sa 2

        *trenutni_chvor->desni=kreirajCvhro((*lista->getUkupno()-*trenutni_chvor->kljuch)%2 == 0 ?
                 (*trenutni_chvor->kljuch-*lista->getUkupno())/2  :
                 (*lista->getUkupno()+1-*trenutni_chvor->kljuch)/2);

        *trenutni_chvor = *trenutni_chvor->desni;

        generishi(trenutni_chvor,lista);

    }

    return;
}

Dakle jedna rekurzija po inorder principu...

Re: konverzija jednostruko povezane liste u binarno stablo... 22.02.2010. u 18:19 · pre 203 meseca #8

Tako nekako... valjda... mada je ne bih imao toliko aritmetike (logaritmovanje, modulovanje, deljenje, sabiranje, oduzimanje...). Kad dođeš do kraja liste završio si posao, nema potrebe da se nešto tu računa. Ovaj pseudokod mi deluje nekako mnogo zaguljeno. Ako imaš neku grešku dobro ćeš se preznojiti dok je ne nađeš. Situaciju komplikuje i to što umesto povratne vrednosti funkcije menjaš same parametre koji su pointer na pointer. Ja sad ne mogu mnogo da se udubljujem u kod, ali ako ti ovo bude radilo onda okej.

Zapravo kad malo razmislim, malo mi čudno, šta se dešava s parametrom trenutni_chvor pošto rekurzivno pozoveš funkciju generishi? Zar vrednost ne bi trebalo da se vrati na ono što je bilo pre poziva?

Re: konverzija jednostruko povezane liste u binarno stablo... 22.02.2010. u 19:20 · pre 203 meseca #9

Probajte ovo:

Code (ruby):

def r_add t, e, max = nil

  return e if t.nil?

  if !t.is_a?(Array)

    return false if max == 1

    return [1, t, e]

  end

  if s = r_add(t[2], e, t[0])

    return [t[0], t[1], s]

  end

  return false if t[0]*2 == max

  return [t[0]*2, t, e]

end

my_tree = nil

[:a, :b, :c, :d, :e, :f, :g, :h, :i].each do |val|

  my_tree = r_add my_tree, val

  puts my_tree.inspect

end

$ ruby main.rb
:a
[1, :a, :b]
[2, [1, :a, :b], :c]
[2, [1, :a, :b], [1, :c, :d]]
[4, [2, [1, :a, :b], [1, :c, :d]], :e]
[4, [2, [1, :a, :b], [1, :c, :d]], [1, :e, :f]]
[4, [2, [1, :a, :b], [1, :c, :d]], [2, [1, :e, :f], :g]]
[4, [2, [1, :a, :b], [1, :c, :d]], [2, [1, :e, :f], [1, :g, :h]]]
[8, [4, [2, [1, :a, :b], [1, :c, :d]], [2, [1, :e, :f], [1, :g, :h]]], :i]

_{//edit: uprostio malo

//edit: i još malo, izbacio klasu da ne bi bunila narod}

Re: konverzija jednostruko povezane liste u binarno stablo... 22.02.2010. u 22:47 · pre 203 meseca #10

Citat:

Mihajlo Cvetanović: Tako nekako... valjda... mada je ne bih imao toliko aritmetike (logaritmovanje, modulovanje, deljenje, sabiranje, oduzimanje...). Kad dođeš do kraja liste završio si posao, nema potrebe da se nešto tu računa. Ovaj pseudokod mi deluje nekako mnogo zaguljeno. Ako imaš neku grešku dobro ćeš se preznojiti dok je ne nađeš. Situaciju komplikuje i to što umesto povratne vrednosti funkcije menjaš same parametre koji su pointer na pointer. Ja sad ne mogu mnogo da se udubljujem u kod, ali ako ti ovo bude radilo onda okej.

Zapravo kad malo razmislim, malo mi čudno, šta se dešava s parametrom trenutni_chvor pošto rekurzivno pozoveš funkciju generishi? Zar vrednost ne bi trebalo da se vrati na ono što je bilo pre poziva?

Upravu si, bash sam se lepo spetljao. Treba tehnicki drugacije izvesti sa pointerima samo sam zamrsio i zakomplikovao a uz to potpuno odstupio od koncepta. Izvinjavam se. Algoritam ostaje ali tehnicki mora drugacije da se izvede.

Zapravo uz manje izmene mozhe i na ovaj nachin, te po ceni da dobijem zescu kritiku zbog eventualnih bagova ili same tehnike, ipak sam odlucio da okacim kod, i svaka konstruktivna kritika je dobro dosla. Dakle sledi c++ kod za demonstraciju rada algoritma:

Code:

#include <cmath>
#include <conio.h>
#include <iostream>
#include <ctime>
#include <stdlib.h>

using namespace std;

struct ChvorStabla{

    int kljuch;
    ChvorStabla *levi;
    ChvorStabla *desni;
    ChvorStabla *otac;
};

class ChvorListe{

    int *niz;
    int ukupno;
    ChvorListe(const ChvorListe&);
    ChvorListe operator =(const ChvorListe&);

public:
    ChvorListe(int ukupno=6):ukupno(ukupno){

        try{

            srand(time(0));
            niz=new int[ukupno];

            for (int i=0; i<ukupno; i++) niz[i]=rand()%100;

        }catch(...){

            delete niz;
            throw "Alociranje neuspeshno";
        }

    }

    ~ChvorListe(){
        delete[] niz;
        delete niz;
    }

    int getUkupno(){

        return ukupno;
    }

    void izlistaj(){
        for(int i=0;i<ukupno;i++) cout<<niz[i]<<" ";
        cout<<endl;
    }

    int pop(){

        if(ukupno == 0) return 0;

        int element=niz[ukupno-1];
        delete &niz[ukupno-1];
        ukupno--;
        return element;
    }
};

void kreirajChvorLevi(int el,ChvorStabla **chvor){

    (*chvor)->levi=new ChvorStabla;
    (*chvor)->levi->kljuch=el;
    (*chvor)->levi->levi=0;
    (*chvor)->levi->desni=0;
    (*chvor)->levi->otac=*chvor;
}

void kreirajChvorDesni(int el,ChvorStabla **chvor){

    (*chvor)->desni=new ChvorStabla;
    (*chvor)->desni->kljuch=el;
    (*chvor)->desni->levi=0;
    (*chvor)->desni->desni=0;
    (*chvor)->desni->otac=*chvor;

}

void generishi(ChvorStabla **trenutni_chvor, ChvorListe *lista){

    ChvorStabla *tmp;

    if(lista->getUkupno()==0) return;

    if (*trenutni_chvor == 0) return;

    if((*trenutni_chvor)->kljuch == 1) {

        kreirajChvorLevi(lista->pop(),trenutni_chvor);

    }else {

        kreirajChvorLevi((*trenutni_chvor)->kljuch/2,trenutni_chvor);

        tmp=*trenutni_chvor;

        *trenutni_chvor = (*trenutni_chvor)->levi;

        generishi(trenutni_chvor,lista);

        *trenutni_chvor=tmp;

    }

    if((*trenutni_chvor)->kljuch == 1){

        kreirajChvorDesni(lista->pop(),trenutni_chvor);

        return;

    }else if((*trenutni_chvor)->otac != 0){

        kreirajChvorDesni((*trenutni_chvor)->kljuch/2, trenutni_chvor);

        tmp=*trenutni_chvor;

        *trenutni_chvor = (*trenutni_chvor)->desni;

        generishi(trenutni_chvor,lista);

        *trenutni_chvor=tmp;

    }else{

        int kljuch = pow(2,int(log10(lista->getUkupno())/log10(2)));

        kreirajChvorDesni(kljuch,trenutni_chvor);

        *trenutni_chvor = (*trenutni_chvor)->desni;

        generishi(trenutni_chvor,lista);

    }

    return;
}

void izlistajPreorder(ChvorStabla *stablo,int &h){

    if( stablo == 0) return;

    h++;
    cout<<stablo->kljuch<<endl;
    izlistajPreorder(stablo->levi,h);
    izlistajPreorder(stablo->desni,h);

}
int nadji(int pozicija,ChvorStabla *stablo){

    while(stablo->kljuch != 0){

        if(pozicija <= stablo->kljuch ) {

            if(pozicija == 1  && stablo->levi==0 && stablo->desni==0) {

                return stablo->kljuch;
            }

            stablo=stablo->levi;

        }else {

            pozicija=pozicija - stablo->kljuch;
            stablo=stablo->desni;
            if(pozicija == 1 && stablo->levi==0 && stablo->desni==0) return stablo->kljuch;

        }
    }

    return -1;
}

int main(){

    try{

        ChvorListe *lista;
        int max;
        cout<<"kapacitet liste: ";
        cin>>max;

        lista=new ChvorListe(max);

        cout<<"sadrzhaj liste: "<<endl;
        lista->izlistaj();
        getch();

        ChvorStabla *koren=new ChvorStabla;
        ChvorStabla *trenutni;
        int kljuch= (log10(lista->getUkupno())) / (log10(2))-int((log10(lista->getUkupno())) / (log10(2))) == 0 ? pow(2,int(log10(lista->getUkupno())/log10(2))-1) :  pow(2,int(log10(lista->getUkupno())/log10(2)));

        koren->kljuch=kljuch;
        koren->levi=0;
        koren->desni=0;
        koren->otac=0;

        trenutni=koren;
        generishi(&trenutni,lista);

        int h=0;
        izlistajPreorder(koren,h);

        int poz;
        cout<<endl<<endl<<"Trazena pozicija: ";
        cin>>poz;
        cin.ignore(1000,'\n');
        cout<<"Rezultat pretrage: "<< nadji(poz,koren)<<endl;
        getch();

    }catch(const char* e){

        cout<<e;
        getch();
    }
}

Izvinjavam se zbog duzhine koda. Kritike su dobrodoshle. Pretpostavljam da je moglo i mnogo prostije od ovoga.

Forum kao aplikacija na telefonu

Srodne teme