Tema
Registracija

binarno drvo , pretrazivanje

Odgovori Nova tema
Štampanje RSS teme Kopiraj vezu do teme Podeli na Facebook-u Podeli na X-u (Twitter) Idi na poslednju poruku
  • 10 odgovora
  • 4.892 pregleda
binarno drvo , pretrazivanje 13.05.2010. u 23:27 · pre 200 meseci #1
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;
Re: binarno drvo , pretrazivanje 14.05.2010. u 00:37 · pre 200 meseci #2
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;
Potpis
Do not be a help vampire (http://slash7.com/pages/vampires), use the google.

How to ask questions the smart way:
http://www.catb.org/~esr/faqs/smart-questions.html
http://solair.eunet.rs/~fangor...stions/smart-questions.sr.html
Re: binarno drvo , pretrazivanje 14.05.2010. u 12:29 · pre 200 meseci #3
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)
Re: binarno drvo , pretrazivanje 14.05.2010. u 13:25 · pre 200 meseci #4
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;
Re: binarno drvo , pretrazivanje 14.05.2010. u 18:01 · pre 200 meseci #5
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?

Re: binarno drvo , pretrazivanje 14.05.2010. u 22:15 · pre 200 meseci #7
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
Re: binarno drvo , pretrazivanje 15.05.2010. u 15:04 · pre 200 meseci #8
> 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]
Re: binarno drvo , pretrazivanje 16.05.2010. u 12:57 · pre 200 meseci #9
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;
Re: binarno drvo , pretrazivanje 16.05.2010. u 13:22 · pre 200 meseci #10
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.
Re: binarno drvo , pretrazivanje 17.05.2010. u 05:11 · pre 200 meseci #11
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...
Odgovori
Prijavite se da biste odgovorili u ovoj temi.PrijavaRegistracija

Premeštanje teme