Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

binarno drvo , pretrazivanje

[es] :: Pascal / Delphi / Kylix :: binarno drvo , pretrazivanje

[ Pregleda: 3390 | Odgovora: 10 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

miniplazma

Član broj: 240037
Poruke: 68
*.crnagora.net.



Profil

icon binarno drvo , pretrazivanje13.05.2010. u 23:27 - pre 168 meseci
Cvor binarnog drveta je tipa student(drvo^.info je tipa student a student = record ime:string[30];index:integer;end;
Drvo je uredjeno prema broju indeksa.Kako napisati funkciju find_node koja vraca pokazivac na cvor sa tom informacijom?Ovo je moje rešenje,ali ne radi (ako nadje cvor u lijevom podstablu,svejedno ide u desno)

Code:
function find_node(var t:drv;ime:string):drv;

begin
    if t=nil then find_node:=nil
    else
        if t^.info.ime=ime then find_node:=t
            else
               begin
                find_node:=find_node(t^.left,ime);
                if t^.info.ime <>ime then
                find_node:=find_node(t^.right,ime);
               end;
end;
 
Odgovor na temu

savkic
Igor Savkić

Moderator
Član broj: 92186
Poruke: 2739



+92 Profil

icon Re: binarno drvo , pretrazivanje14.05.2010. u 00:37 - pre 168 meseci
Code:

function find_node(var t: drv; const ime: string): drv;
begin
  if t = nil then
    Result := nil
  else
    if t^.info.ime = ime then
      Result := t
    else begin
      Result := find_node(t^.left, ime);
      if not Assigned(Result) then
        Result := find_node(t^.right, ime);
    end;
end;

 
Odgovor na temu

miniplazma

Član broj: 240037
Poruke: 68
*.crnagora.net.



Profil

icon Re: binarno drvo , pretrazivanje14.05.2010. u 12:29 - pre 168 meseci
Hvala
Radi,samo umjesto result napišem find_node (jer free pascal neće da kompajlra)
I možeš li mi da mi objasni šta znači naredba
Code:
if not Assigned(Result)
 
Odgovor na temu

miniplazma

Član broj: 240037
Poruke: 68
*.crnagora.net.



Profil

icon Re: binarno drvo , pretrazivanje14.05.2010. u 13:25 - pre 168 meseci
I još jedno pitanje :) Procedura za brisanje čvora drveta,imam neke greške ne mogu da provalim šta

Code:
procedure brisi(var t:drv;ime:string);
var
    p,q,r:drv;
begin
    p:=find_node(t,ime);
    if p<>nil then
    if p^.left=nil then t:=p^.right
        else
            if p^.right=nil then t:=p^.left
                else
                    begin
                        q:=p^.left;
                        r:=q;
                        while q^.right<>nil do
                            begin
                                r:=q;
                                q:=q^.right;
                            end;
                        p^.info:=q^.info;
                        r^.right:=q^.left;
                        p:=q;
                    end;

    dispose(p);
end;
 
Odgovor na temu

sasaz2008

Član broj: 200415
Poruke: 204
*.adsl.eunet.rs.



+4 Profil

icon Re: binarno drvo , pretrazivanje14.05.2010. u 18:01 - pre 168 meseci
Ne možeš iz binarnog stabla tako lako da ukloniš čvor.

Šta zapravo želiš da uradiš?
Da li želiš da brisanjem čvora ukloniš i naslednike?
Ili samo taj čvor i potom reizbalansiraš celo stablo?

 
Odgovor na temu

savkic
Igor Savkić

Moderator
Član broj: 92186
Poruke: 2739



+92 Profil

icon Re: binarno drvo , pretrazivanje14.05.2010. u 20:30 - pre 168 meseci
> I možeš li mi da mi objasni šta znači naredba
> if not Assigned(Result)

if Result = nil then
 
Odgovor na temu

miniplazma

Član broj: 240037
Poruke: 68
*.crnagora.net.



Profil

icon Re: binarno drvo , pretrazivanje14.05.2010. u 22:15 - pre 168 meseci
brise se čvor na koji pokazuje pokazivač p
ako nema sinova samo se izbrise;
ako ima lijevog sina,a nema desnog ,na njegovo mjesto dolazi lijevi sin
ako ima desnog sina a nema desnog,na njegovo mjesto dolazi desni sin
ako ima i lijevog i desnog sina,pokazivac q pokazuje na lijevog sina p,i zatim trazi krajnjeg desnog sina.tada u info polje cvora koji se brise upisuje info krajnjeg desnog(tj onog na koji pokazuje q),za pokazivac r(pokazuje na oca od q) kao lijevog sina stavlja lijevo podstablo q;p pokazuj gdje i q.i na kraju oslobadja cvor na koji pokazuje p

Citat:
Ili samo taj čvor i potom reizbalansiraš celo stablo?

Da ,to treba da uradi
 
Odgovor na temu

sasaz2008

Član broj: 200415
Poruke: 204
*.adsl.eunet.rs.



+4 Profil

icon Re: binarno drvo , pretrazivanje15.05.2010. u 15:04 - pre 168 meseci
> u info polje cvora koji se brise upisuje info krajnjeg desno...

Ne. Nod koji se briše se može obrisati odmah, jedino što je neophodno je da se zapamti njegov roditelj i levi i desni naslednik.

Pošto koliko vidim, ovo nije klasično stablo gde je levi naslednik manji a desni veći, nema ni nekih uobičajenih pravila koje se moraju poštovati, pa je zato pretraga daleko sporija od uobičajene O(Log2(N)). Preporuka je da to pravilo uvedeš po nazivu, a time će i brisanje noda biti daleko jasnije i pravilnije. Za pronalaženje nodova po indeksu jednostavno napravi listu odnosno array sa pointerima.

Uzmimo kao primer da se briše root nod. U tom slučaju roditelj je nil, a naslednici neka budu TL i TR. Root node može da se izbriše odmah, a Root postaje TR. Prošetaš se po stablu od TR noda tražeći nod koji ima prazan link vodeći računa da ukoliko je veći bude sa desne, odnosno sa leve strane ukoliko je manji i tu linkuješ TL nod. To je sve.

Uzmimo sada da se briše prvi desni naslednik Root-a. U tom slučaju roditelj je Root, a naslednici neka budu TL i TR desnog naslednika Root-a - ostatak procedure je isti, s tim što se desni link Root-a povezuje za TR. Sledbeno toj logici slično se radi i kada se briše levi nod.

Problem koji se u oba slučaja javlja je da stablo postaje neizbalansirano i pretraga daleko sporija. Balansiranje stabla nije baš trivijalan posao, jer sa leve, odnosno desne strane mora biti približno isti broj nodova a svaki nod da ima oba naslednika do poslednje grane...

Odnosno, primeni pravilo ubacivanja po tvojoj strukturi stabla. Bitno je samo da zapamtiš roditelja i naslednike tog noda koji se briše.

[Ovu poruku je menjao sasaz2008 dana 15.05.2010. u 16:52 GMT+1]
 
Odgovor na temu

miniplazma

Član broj: 240037
Poruke: 68
*.crnagora.net.



Profil

icon Re: binarno drvo , pretrazivanje16.05.2010. u 12:57 - pre 168 meseci
zadatak je takav da se u drvo clanovi dodaju na osnovu broja,a pretrayuje se po imenu
Ovo meni nije jasno:
Ovo je zadatak u kome je binarno drvo def. ovako:
tree:^cvor;
cvor = RECORD
info:treeinfo; {treeinfo je tipa integer}
left,right:tree;
end;
Ako proceduru za brisanje napisem ovako, radi kako treba

Code:
procedure brisi(var t:tree;x:treeinfo);

var

   p,q,r:tree;

begin

    if t<> nil then

      if x<t^.info then brisi(t^.left,x)
 {trazi cvor sa sadrzajem x koji treba da se obrise}
         else

            if (x>t^.info ) then brisi(t^.right,x)

            else

               begin

                   p:=t;

                   if (p^.left=nil) then t:=p^.right

                   else

                        if p^.right=nil then t:=p^.left

                        else

                           begin

                               q:=t^.left;

                               r:=q;

                               while q^.right<>nil do

                                 begin

                                     r:=q;

                                     q:=q^.right;

                                 end;

                               p^.info:=q^.info;

                               r^.right:=q^.left;

                               p:=q;

                           end;

                   dispose(p);

               end;

end;


A ako umjesto prva tri reda koristim funkciju find_node koja vraca pokazivac na cvor koji treba da se obrise ,ne radi
Code:
procedure brisi(var t:tree;x:treeinfo);

var

   p,q,r:tree;

begin

    if t<> nil then
    p:=find_node(t,x);
    if p=nil then writeln('Nema takvog cvora u drvetu')
            else

               begin

                   t:=p;

                   if (p^.left=nil) then t:=p^.right

                   else

                        if p^.right=nil then t:=p^.left

                        else

                           begin

                               q:=t^.left;

                               r:=q;

                               while q^.right<>nil do

                                 begin

                                     r:=q;

                                     q:=q^.right;

                                 end;

                               p^.info:=q^.info;

                               r^.right:=q^.left;

                               p:=q;

                           end;

                   dispose(p);

               end;

end;
 
Odgovor na temu

sasaz2008

Član broj: 200415
Poruke: 204
*.adsl.eunet.rs.



+4 Profil

icon Re: binarno drvo , pretrazivanje16.05.2010. u 13:22 - pre 168 meseci
U potpunosti te razumem da radiš prečicu - umesto brisanja noda ubaciješ podatke iz noda koji je na poslednjoj grani i njega brišeš. To može u tvom slučaju, ali ne i u standardno formiranom stablu... Može malo drugačije da se izvrši optimizacija u standardnom stablu, ali bih ti preporučio da prvo uradiš "na teži način", kako bi u potpunosti razumeo šta se dešava.

Savet: ako nešto ne razumeš tačno kako radi - nacrtaj i simuliraj na papiru.
 
Odgovor na temu

sasaz2008

Član broj: 200415
Poruke: 204
*.adsl.eunet.rs.



+4 Profil

icon Re: binarno drvo , pretrazivanje17.05.2010. u 05:11 - pre 168 meseci
Uzgred, izbriši na taj način nod sa poslednje grane i odštampaj celo stablo ili pretraži celo stablo za vrednost koja ne postoji...
 
Odgovor na temu

[es] :: Pascal / Delphi / Kylix :: binarno drvo , pretrazivanje

[ Pregleda: 3390 | Odgovora: 10 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.