Binární vyhledávací strom J e d n á s e o o d r ů d u o b e c n ě j š í d a t o v é s t r u k t u r y z v a n é „ st r o m“. P o j e m p o c h á z í z t e o ri e g r a f ů , k d e j e s t r o m e m n a z ý v á n s o u v i s l ý g r a f b e z c y k l ů. S k l á d á s e z u z l ů a h r a n . V p r o g r a m o v é r e p r e z e n t a c i j s o u u z l y z á z n a m y a n e s o u j e d n a k i n f o r m a c i, j e d n a k o d k a z y n a d a l š í u z l y. H r a n y j s o u r e p r e z e n t o v á n y u k a z a t e li a u r č u j í v a z b y m e z i j e d n o t li v ý m i u z l y.
S t r o m y č a s t o b ý v a j í z o b r a z o v á n y g r a f i c k y:
P o j í s e s n i m i c e l á ř a d a t e r m í n ů . P o k u s í m s e j e v e s t r u č n o s t i s h r n o u t. U z e l z c e l a n a h o ř e, k t e r ý m s e v s t u p u j e d o c e l é h o s t r o m u , s e n a z ý v á k o ř e n. U z l y, k e k t e r ý m v e d o u h r a n y z n ě k t e r é h o u z l u, j s o u o z n a č o v á n y z a s y n y t o h o t o u z l u. K a ž d ý s y n m ůž e m í t s v é s y n y a ti z a s e s v é a t d. S y n s e v š í m s v ý m p o t o m s t v e m t v o ř í j e d e n z p o d s t r o m ů o t c o v s k é h o u z l u. L i s t y j s o u p a k u z l y b e z s y n ů ; ji m i s t r o m k o n č í. Č et n o s t s t r o m u j e m a x i m á l n í p o č e t s y n ů , k t e r é m á n ě k t e r ý z j e h o u z l ů . C e s t a o d k o ř e n e k n ě k t e r é m u z u z l ů s e n a z ý v á v ě t e v. V z h l e d e m k t o m u , ž e s t r o m y n e o b s a h u j í c y k l y, j e v ě t e v v ž d y j e d n o z n a č n ě u r č e n a . A k o n e č n ě h l o u b k a s t r o m u j e d é l k a (po č e t h r a n) m a x i m á l n í v ě t v e. U d á v á , j a k á j e n e j v ě t š í v z d á l e n o s t m e z i k o ř e n e m a n ě k t e r ý m z li s t ů .
Proč binární? B i n á r n í: Č et n o s t s t r o m u j e d v ě . K a ž d ý j e h o u z e l s m í m í t n a n e j v ý š d v a s y n y. P o u ž í v a j í s e p r o ně u k a z a t e l e L e v ý a P r a v ý.
Vyhledávání T e n t o d r u h s t r o m u j e o r g a n i z o v á n p r o s n a d n é v y h l e d á v á n í j e d n o tli v ý c h p r v k ů . Č á s t n e s e n é i n f o r m a c e t v o ř í k l í č . K l í č e v l e v é m p o d s t r o m u k a ž d é h o u z l u j s o u v ž d y m e n š í n e ž k l í č u z l u, k l í č e v p r a v é m p o d s t r o m u j s o u n a o p a k v ě t š í. D í k y t o m u j e v y h l e d á v á n í u r č it é h o d n o t y k l í č e s n a d n é . J e-li m e n š í, n e ž k l í č z k o u m a n é h o u z l u, m u s í s e p o k r o č it k l e v é m u s y n o v i. J e-li v ě t š í, b u d e h l e d á n í p o k r a č o v a t v p r a v o .
P r a v i d l o „ m e n š í v l e v o , v ě t š í v p r a v o“ j e p o m ě r n ě v o l n é a u z l y l z e v e s t r o m u u s p o ř á d a t m n o h a z p ů s o b y, a n i ž b y d o š l o k j e h o p o r u š e n í. O v š e m p r a v i d l ů m t a k é v y h o v í z c e l a d e g e n e r o v a n ý s t r o m , j e h o ž k o ř e n p o n e s e k l í č 2, v š e c h n y u z l y b u d o u m í t p r á z d n ý l e v ý p o d s t r o m a j e ji c h p r a v ý m s y n e m b u d e n e j b l i ž š í h o d n o t a. T a k o v ý s t r o m v p o d s t a t ě p ř e š e l d o li n e á r n í h o s e z n a m u , n i c m é n ě s p l ň uj e v e š k e r é n á r o k y n a b i n á r n í v y h l e d á v a c í s t r o m .
Praxe: Ze všeho nejdříve se podíváme na deklarace, jejichž pomocí budeme strom realizovat: type strom=array [1..100] of Integer; var st:strom; počet, cis:integer;
^tato část kódu nám říká, že strom budeme vytvářet pomocí pole, a zadeklamovali jsme si základní proměnné, které budeme později používat nyní rekurzivní procedura pro vytvoření samotného binárního vyhledávacího stromu: procedure VytvorBVS(i,x:integer; var s:strom); begin if s[1]=0 then begin s[1]:=x; pocet:=1; s[2]:=0; s[3]:=0; end else if x<s[i] then if s[2*i]=0 then s[2*i]:=x else VytvorBVS((2*i),x,s); if x>s[i] then if s[((2*i)+1)]=0 then s[((2*i)+1)]:=x else VytvorBVS(((2*i)+1),x,s); end; procedura pro vytvoření hlady: procedure halda; var i:integer; begin for i:=1 to 100 do st[i]:=0; end; halda se musí vytvořit ihned se startem programu, to uděláme tak že jí vložíme do procedury samotného Formuláře: procedure TForm1.FormCreate(Sender: TObject); begin halda; end; procedura pro vytvoření stromu ze souboru s čísly:
procedure TForm1.Button2Click(Sender: TObject); var f: TextFile; a: Integer; begin AssignFile(f, 'File1.txt'); reset(f); while not EOF(f) do begin readln(f, a); VytvorBVS(1,a, St); end; CloseFile(f); end; procedura pro výpis do mema: procedure tisk (i,h:integer); var s1:string; j:integer; begin if st[i]<>0 then begin tisk(2*i+1,h+1); s1:=''; for j:=1 to h do s1:=s1+' s1:=s1+inttostr(st[i]); memo1.lines.add(s1); tisk(2*i,h+1); end; end; begin memo1.Lines.Clear; tisk(1,1); end;
';
přehlednější než výpis je však grafické vykreslení do komponenty image, to uděláme následovně: procedure TForm1.Button3Click(Sender: TObject); procedure vykresli(i, x, y, sirka: Integer); begin sirka:=sirka div 2; if st[2*i]<>0 then begin image1.canvas.MoveTo(x,y); image1.canvas.LineTo(x-sirka,y+30); vykresli(2*i,x-sirka,y+30, sirka) end; if St[2*i+1]<>0 then begin image1.canvas.MoveTo(x,y); image1.canvas.LineTo(x+sirka,y+30); vykresli(2*i+1,x+sirka,y+30,sirka)
end; Image1.Canvas.TextOut(x-5, y-8, IntToStr(St[i])); end; begin image1.canvas.Brush.Color:=clwhite; image1.canvas.Brush.Style:=bssolid; image1.canvas.Rectangle(0,0,image1.width,image1.height); vykresli(1, image1.width div 2, 10, image1.width div 2,); end;
^zde by bylo možná lepší proceduru lépe popsat, jelikož je dosti dlouhá: Procedura pro vykreslení je součásti procedury buttonu3, na který když klikneme tak se nám strom vykreslí, zadali jsme si několik proměnných i pro číslo, x, y a šířku výpočet pro souřadnic. Nejprve zjistíme, zdali strom není prázdný, pokud ne tak začneme vykreslovat jeho levou stranu. Příkaz MoveTo je pro přesouvání „kreslícího pera“ na pozici x a y, a LineTo nám kreslí spojnici (větev). Totéž uděláme pro pravou stranu. Nakonec příkazem TextOut vypíšeme ke každé větvi její číslo, nebo chcete-li její hodnotu. To je celá procedura na vykreslení. V proceduře samotného buttonku pak pouze smažeme plátno, nastavíme vlastnosti kreslicího pera a zavoláme proceduru“ vykresli“.
Čtvrtou a poslední částí programu je vyhledávání námi zadaného čísla: samotná vyhledávací procedura: procedure vyhledej (x,i:integer; s:strom;var a:integer); begin if x=s[i]then begin a:=i; end else if (x>s[i]) and (s[(2*i)+1]<>0) then vyhledej (x,((2*i)+1),s,a) else if (x<s[i]) and (s[(2*i)]<>0) then vyhledej (x,(2*i),s,a) else a:=0; end; button pro button: procedure TForm1.Button4Click(Sender: TObject); var cis: integer; begin vyhledej(strtoint(edit1.text),1,st,cis); if cis<>0 then begin memo1.lines.Add(' '); memo1.lines.Add('Číslo nalezeno na řádku:'+(inttostr(cis))); end else memo1.lines.Add('Číslo nebylo nalezeno'); end;
