Rešitev: Uravnoteženo dvojiško drevo (Mathematica)

Iz MaFiRaWiki

Naloga: Uravnoteženo dvojiško drevo

Najprej implementiramo podatkovno strukturo dvojiško drevo:

 Clear[Pripravi,DDrevo,Sestavi,Koren,LeviSin,DesniSin,JePrazno]
 Pripravi[]:=DDrevo[]
 Sestavi[p_,ls_,ds_]:=DDrevo[ls,p,ds]
 Koren[DDrevo[_,k_,_]]:=k
 LeviSin[DDrevo[l_,_,_]]:=l
 DesniSin[DDrevo[_,_,d_]]:=d
 JePrazno[d_DDrevo] := Length[d]==0

Rešitev naloge, pri kateri uporabimo pomožno funkcijo globina[DDrevo], ki vrne globino drevesa:

 Clear[globina] 
 globina[Sestavi[_,Pripravi[],Pripravi[]]]:=0
 globina[Sestavi[_,Pripravi[],d_DDrevo]]:=globina[d]+1
 globina[Sestavi[_,d_DDrevo,Pripravi[]]]:=globina[d]+1
 globina[d_DDrevo]:=Max[globina[DesniSin[d]], globina[LeviSin[d]]] + 1
 globina::usage="Funkcija globina[DDrevo] vrne globino drevesa (t.j. največja globina oz. raven kakšnega lista).";

 Clear[uravnotezeno]
 uravnotezeno[Pripravi[]]:=True
 uravnotezeno[Sestavi[_,Pripravi[],Pripravi[]]]:=True
 uravnotezeno[Sestavi[_,Pripravi[],d_DDrevo]]:=If[globina[d]>1, False, True]
 uravnotezeno[Sestavi[_,d_DDrevo,Pripravi[]]]:=If[globina[d]>1, False, True]
 uravnotezeno[d_DDrevo]:=If[Abs[globina[LeviSin[d]]-globina[DesniSin[d]]] > 1, False, 
  True && uravnotezeno[LeviSin[d]] && uravnotezeno[DesniSin[d]]]
 uravnotezeno::usage="Funkcija uravnotezeno[DDrevo] vrne True, če je dvojiško drevo uravnoteženo (t.j. za vsako poddrevo velja, da 
  je globina levega poddrevesa za največ ena različna od globine desnega poddrevesa), in False sicer. Pri tem se dogovorimo, da je 
  prazno drevo uravnoteženo.";

Preizkusimo na primerih:

1. primer:

 Clear[drevo1]
 drevo1 = Sestavi[1,
  Sestavi[2,
   Sestavi[4,
    Pripravi[], Pripravi[]],
   Pripravi[]],
  Sestavi[3,
   Sestavi[5, Pripravi[],
    Sestavi[7, Pripravi[], Pripravi[]]],
   Sestavi[6, Pripravi[], Pripravi[]]]]

drevo1 izgleda takole:

 In[23]:= uravnotezeno[drevo1]
 Out[23]:= True

2. primer:

 Clear[drevo2]
 drevo2 = Sestavi[1,
  Sestavi[2,
   Sestavi[4, Pripravi[], Pripravi[]],
   Sestavi[5,
     Sestavi[7, Pripravi[], Pripravi[]],
     Pripravi[]]],
  Sestavi[3, Pripravi[], Pripravi[]]]

drevo2 izgleda takole:

 In[26]:= uravnotezeno[drevo2]
 Out[26]:= False

Če pa pred primeroma potrdimo še naslednjo funkcijo Risi, nam Mathematica drevo tudi nariše.

 Clear[RisiDrevo,Risi]
 RisiDrevo[d_]:=If[!JePrazno[d], Show[Graphics[Risi[d,0,{0,0}]]]]
 Risi[d_,n_,{x_,y_}]:=
   If[JePrazno[d],{},Join[{Point[{x,y}],Text[Koren[d],{x+0.1,y}]},
       If[JePrazno[LeviSin[d]], {}, {Line[{{x,y},{x-2^(-n),y-1}}]}], If[JePrazno[DesniSin[d]], {}, {Line[{{x,y},{x+2^(-n),y-1}}]}],
       Risi[LeviSin[d],n+1,{x-2^(-n),y-1}], Risi[DesniSin[d],n+1,{x+2^(-n),y-1}]
      ]
   ]

 (* Poskrbimo, da vedno dobimo izrisano drevo. *)
 Format[d_DDrevo]:=RisiDrevo[d]

Glej tudi

Osebna orodja