[es] - Pretraga binarnog stabla C

tripleqqqqq

Član broj: 315529
Poruke: 22

+1 Profil

^{27.01.2014. u 17:03 - pre 124 meseci}

Pozdrav.
Potrebna mi je pomoc oko algoritma za 'pametnu' pretragu binarnog stabla. Treba da vratim broj cvorova kod kojih je podatak po kome se formira stablo veci od nekog zadatog broja ali tako da ne prolazim kroz sve cvorove. Moze i samo ideja pa cu napisati sam, ne mora ceo kod.

Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6042

+4631 Profil

Re: Pretraga binarnog stabla C

^{27.01.2014. u 18:01 - pre 124 meseci}

Za zadatak i resenje je vazno kako se formira stablo. Ako je stablo slucajnog rasporeda sa slucajnim vrednostima cvorova i listova onda ne mozes da prebrojis bez da posetis sve cvorove.

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić

Odgovor na temu

tripleqqqqq

Član broj: 315529
Poruke: 22

+1 Profil

Re: Pretraga binarnog stabla C

^{27.01.2014. u 22:10 - pre 124 meseci}

Formira se tako sto levo od svakog cvora idu elementi manji od njega a desno veci, balans vec nije bitan, tako da moze i za ne balansirano stablo.

Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
c-bg-d-p4-109.bvcom.net.

+1064 Profil

Re: Pretraga binarnog stabla C

^{27.01.2014. u 23:11 - pre 124 meseci}

Mozes da upises u svaki cvor tezinu levog i tezinu desnog cvora tako sto ces kad prolazis kroz stablo prilikom dodavanja noda
dodati +1 svakom listu kroz koji prolazis. To mi je prvo palo napamet. Kada pretrazujes stablo dodjes do cvora
gde su svi levi manji a svi desni veci od zadatog broja i onda procitas tezinu datog cvora.

Odgovor na temu

tripleqqqqq

Član broj: 315529
Poruke: 22

+1 Profil

Re: Pretraga binarnog stabla C

^{27.01.2014. u 23:36 - pre 124 meseci}

To je odlicno resenje i tada imam minimalni broj provera cvorova pri pretrazi ali mi nije dozvoljeno da menjam strukturu. Cvor mora da sadrzi tacno ono sto mi je zadato. Posto je obicno binarno stablo(nije balansirano) sme da sadrzi samo podatak i pokazivac na levo i desno dete.

Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
c-bg-d-p4-109.bvcom.net.

+1064 Profil

Re: Pretraga binarnog stabla C

^{28.01.2014. u 00:10 - pre 124 meseci}

Ako nemas podatak o tezini leve i desne grane u cvoru, onda moras proci celu granu da bi izracunao tezinu.

Odgovor na temu

tripleqqqqq

Član broj: 315529
Poruke: 22

+1 Profil

Re: Pretraga binarnog stabla C

^{28.01.2014. u 09:25 - pre 124 meseci}

Ako stablo izgleda ovako i ja hocu da nadjem broj cvorova vecih od 14, zasto onda moram da prodjem i kroz 5,1,8? Zasto ne mogu da kad dodjem do prvog manjeg proverim samo desno od njega i onda se vracam gore, ka roditelju?

Code:

                        20
                       /   \
                      15   21
                     /  \    \
                    5  17    28
                   / \      / \
                  1   8   24  30
                         / \
                        23  26

Odgovor na temu

Burgos
Nemanja Borić
Amazon Web Services
Berlin

Član broj: 12484
Poruke: 1947
..106.109.adsl.dyn.beotel.net.

Sajt: stackoverflow.com/users/1..

+480 Profil

Re: Pretraga binarnog stabla C

^{28.01.2014. u 10:23 - pre 124 meseci}

Možeš i to je jedina optimizacija koju mogu da vidim.

Odgovor na temu

tripleqqqqq

Član broj: 315529
Poruke: 22

+1 Profil

Re: Pretraga binarnog stabla C

^{28.01.2014. u 10:43 - pre 124 meseci}

Pa da, ali kako?

Odgovor na temu

tripleqqqqq

Član broj: 315529
Poruke: 22

+1 Profil

Re: Pretraga binarnog stabla C

^{28.01.2014. u 16:36 - pre 124 meseci}

resio sam, evo kako ako nekog interesuje.

Code:

void trazi(drvo* p, int k, int* broj)
{
    if(p)
    {
        if(p->broj > k)
        {
            (*broj)++;
            trazi(p->levi,k,broj);
        }
        trazi(p->desni,k,broj);
    }
}

Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
c-bg-d-p4-109.bvcom.net.

+1064 Profil

Re: Pretraga binarnog stabla C

^{28.01.2014. u 19:26 - pre 124 meseci}

Citat:

tripleqqqqq:
Ako stablo izgleda ovako i ja hocu da nadjem broj cvorova vecih od 14, zasto onda moram da prodjem i kroz 5,1,8? Zasto ne mogu da kad dodjem do prvog manjeg proverim samo desno od njega i onda se vracam gore, ka roditelju?

A sta ako je stablo ovakvo?

Code:

                        20
                       /   \
                      16   21
                     /  \    \
                   5   17     28
                   / \           / \
                 1   8        24  30
                       \       / \
                       15   23  26

Odgovor na temu

tripleqqqqq

Član broj: 315529
Poruke: 22

+1 Profil

Re: Pretraga binarnog stabla C

^{28.01.2014. u 22:36 - pre 124 meseci}

Radi i u tom slucaju, on stigne do petice, i ona nije manja od 14 i tada rekurzivno poziva istu funkciju za desnu granu, desna grana je 8, posto 8 takodje nije manje od 14 opet poziva istu funkciju za desnu granu, tu uveca brojac za 1 jer je 15 vece od 14 i poziva za levu granu, ali sada je p = NULL jer leva grana ne postoji i onda se vraca na gore.

Odgovor na temu