Naloga/Programiranje/Objektno programiranje/Razred AVLDrevo/Rešitev AVL-2 (Mathematica)

Iz MaFiRaWiki

Avl-2 drevo ima enake rotacije kot AVL drevo, le da dovolimo neuravnoteženost stopnje 2, tj., globina levega in desnega poddrevesa se lahko razlikujeta za 2.

Najprej definirajmo pomožne funkcije.

(*Funkcije, ki nam pomagajo pri osnovnih operacijah : sestavljanje drevesa, merjenju globine drevesa ipd.*)

emptyTree = {};
node[balance_, data_, left_, right_] := {balance, data, left, right};
leftTree[{}] := {};
rightTree[{}] := {};
leftTree[{_, _, left_, _}] := left;
rightTree[{_, _, _, right_}] := right;
nodeData[{_, data_, _, _}] := data;
balanceFactor[{balance_, _, _, _}] := balance;
balanceFactor[{}] := 0;
nodeData[{}] := Null;
setLeftTree[tree_, left_] := 
node[balanceFactor[tree], nodeData[tree], left, rightTree[tree]];
setRightTree[tree_, right_] := node[balanceFactor[tree], nodeData[tree],leftTree[tree], right];
setBalance[tree_, balance_] := node[balance, nodeData[tree], leftTree[tree],rightTree[tree]];
setData[tree_, 
        data_] := node[balanceFactor[tree], data, leftTree[tree],rightTree[tree]];
glob[emptyTree] := 0;
glob[tree_] /; tree =!= {} := Depth[tree] - 2;

Definirajmo rotacije, ki jih že poznamo iz AVL drevesa, to so: LL, DD, LD in DL.

(*Rotacije*)

LL[tree_] := Module[{noviata, novilevi, novidesni, porot},
      noviata = nodeData[leftTree[tree]];
      novilevi = leftTree[leftTree[tree]];
      novidesni = setBalance[{0, nodeData[tree], 
      rightTree[leftTree[tree]], 
        rightTree[tree]}, glob[
          rightTree[leftTree[tree]]] - glob[rightTree[tree]]];
      porot = {glob[novilevi] - glob[
            novidesni], noviata, novilevi, novidesni}
      ];
DD[tree_] := Module[{noviata, novilevi, novidesni, porot},
      noviata = nodeData[rightTree[tree]];
      novilevi = setBalance[{0, nodeData[tree], leftTree[tree], 
            leftTree[rightTree[tree]]}, glob[leftTree[rightTree[
          tree]]] - glob[leftTree[tree]]];
      novidesni = rightTree[rightTree[tree]];
      porot = {glob[novilevi] - glob[novidesni], noviata, novilevi,novidesni}
      ];
LD[tree_] := Module[{noviata, novilevi, novidesni, porot},
      noviata = nodeData[rightTree[leftTree[tree]]];
      novilevi = setBalance[setRightTree[leftTree[tree],leftTree[rightTree[leftTree[tree]]]], glob[leftTree[leftTree[tree]]] - 
            glob[leftTree[rightTree[leftTree[tree]]]]];
      novidesni = setBalance[{0, 
      nodeData[tree], rightTree[
        rightTree[leftTree[tree]]], rightTree[tree]}, glob[
            rightTree[rightTree[leftTree[tree]]]] - glob[rightTree[tree]]];
      porot = {glob[novilevi] - glob[novidesni], noviata, 
            novilevi, novidesni}
      ];
DL[tree_] := Module[{noviata, novilevi, novidesni, porot},
      noviata = nodeData[leftTree[rightTree[tree]]];
      novidesni = setBalance[setLeftTree[rightTree[tree],rightTree[leftTree[rightTree[tree]]]], glob[rightTree[
    leftTree[rightTree[tree]]]] - glob[rightTree[rightTree[tree]]]];
      novilevi = setBalance[{0, nodeData[
      tree], leftTree[tree],
         leftTree[leftTree[rightTree[tree]]]},glob[leftTree[leftTree[rightTree[tree]]]] - glob[leftTree[tree]]];
      porot = {
              glob[novilevi] - glob[novidesni], noviata, novilevi, novidesni}
      ];

Definirajmo funkcijo, ki uravnoteži drevo. Pripomnimo, da je funkcija sestavljena tako, da lahko v pogojih števki 2 in 3 zmanjšamo za 1, torej na 1 in 2, in s tem dobimo celo kodo uporabno za običajno AVL drevo.

(*Funkcija "popraviD" uravnoteži drevo.*)

popraviD[{_, {}, {}, {}}] := {};
popraviD[tree_] /; (Abs[glob[leftTree[
              tree]] - glob[rightTree[tree]]] ? 2) && (nodeData[
            tree] =!= {}) := tree;
popraviD[tree_] /; (glob[leftTree[tree]] - glob[rightTree[
              tree]] ? 
                3 && glob[leftTree[leftTree[tree]]] - glob[rightTree[leftTree[
              tree]]] > 0) := LL[tree];
popraviD[tree_] /; (glob[leftTree[tree]] - 
            glob[rightTree[tree]] ? 3 && glob[leftTree[leftTree[
        tree]]] - glob[rightTree[leftTree[tree]]] < 0) := LD[tree];
popraviD[tree_] /; (glob[leftTree[tree]] - glob[rightTree[tree]] <= -3 &&glob[leftTree[rightTree[tree]]] - glob[rightTree[rightTree[tree]]] >
                 0) := DL[tree];
popraviD[tree_] /; (glob[leftTree[tree]] - glob[rightTree[tree]] <= -3 && 
glob[leftTree[rightTree[tree]]] - glob[rightTree[
                rightTree[tree]]] < 0) := DD[tree];

Definirajmo funkciji za vstavljanje elementa v drevo in za sestavo popolnoma novega drevesa iz seznama elementov.

(*Vstavljanje elementa*)

vstaviEl[{}, el_] := {0, el, {}, {}};
vstaviEl[tree_, el_] /; (Order[el, nodeData[tree]] == 0) := tree;
vstaviEl[tree_, el_] /; (Order[el, nodeData[tree]] == 1) := popraviD[
      setLeftTree[tree, vstaviEl[leftTree[tree], el]]];
vstaviEl[tree_, el_] /; (Order[
    el, nodeData[tree]] == -1) := 
      popraviD[setRightTree[tree, vstaviEl[rightTree[tree], el]]];


(*Vstavljanje seznama elementov*)

vstaviSeznam[tree_, x_List] := Fold[vstaviEl, tree, x];

Najzahtevnejša funkcija pri AVL drevesih je funkcija brisanja elementa. Paziti moramo, da odstranimo pravi element in takoj na to uravnotežiti drevo, če je to potrebno. Pri AVL-2 drevesu dovolimo neravnotežje stopnje 2, zato je potrebno drevo manjkrat ponovno uravnotežiti kot AVL drevo. Ker je razlika med brisanjem korena, lista in notranjega elementa velika, funkcijo definiramo za vsak primer posebej.

(*Pomožne funkcije, ki nam bodo pomagale pri spreminjanu drevesa ob odstranjevanju elementa*)

minim[tree_] := Module[{},
      If[leftTree[tree] =!= {}, najmanjsi = minim[leftTree[tree]], najmanjsi= nodeData[tree]];
      najmanjsi
      ];
maxim[tree_] := Module[{},
      If[rightTree[tree] =!= {}, najvecji = maxim[rightTree[
          tree]], najvecji = nodeData[tree]];
      najvecji
      ];
newTreeD[tree_] := Module[{},
      novo = brisiEl[tree, minim[rightTree[tree]]];
      novo = setData[novo, minim[rightTree[tree]]];
      setRightTree[setLeftTree[popraviD[novo], popraviD[leftTree[popraviD[
            novo]]]], popraviD[rightTree[popraviD[novo]]]]
      ];
newTreeL[tree_] := Module[{},
      novo = brisiEl[tree, maxim[leftTree[tree]]];
      novo = setData[novo, maxim[leftTree[tree]]];
      setRightTree[setLeftTree[popraviD[novo], popraviD[leftTree[
      popraviD[novo]]]], popraviD[rightTree[popraviD[novo]]]]
      ];


(*brisanje lista, ki ni koren, torej pravega lista*)

brisiEl[tree_, el_] /; (nodeData[tree] =!= el)&& (Extract[tree, Delete[Position[tree, 
                el][[1]], -1]][[3]] == {}) && (Extract[tree,
                       Delete[Position[tree, el][[1]], -1]][[4]] == {}) :=
    setRightTree[
      setLeftTree[popraviD[
                ReplacePart[ReplacePart[ReplacePart[tree, {}, 
                      Position[tree, el]], {}, Position[tree, el]], {},
            {Delete[Position[tree, el][[1]], -1]}]], popraviD[leftTree[
          
  popraviD[ReplacePart[ReplacePart[ReplacePart[tree, {}, Position[
              tree, el]], {}, Position[tree, el]], {},
                {Delete[Position[tree, el][[1]], -1]}]]]]],
      popraviD[rightTree[setLeftTree[popraviD[ReplacePart[ReplacePart[
    ReplacePart[tree, {}, Position[tree, el]], {}, Position[tree, el]], {},
                {Delete[Position[tree, el][[1]], -1]}]], popraviD[leftTree[
             
                 popraviD[ReplacePart[
                ReplacePart[ReplacePart[
                  tree, {}, Position[tree, el]], {}, Position[tree, el]], {},
                    {Delete[Position[tree, el][[1]], -1]}]]]]]]]
      ];

(*brisanje lista, ki je hkrati koren, torej brisanje atomarnega drevesa*)

brisiEl[tree_, el_] /; (nodeData[tree] == el) && (rightTree[
      tree] == {} && leftTree[tree] == {}) := {};

(*brisanje notranjega elementa, če desno poddrevo ni prazno*)

brisiEl[tree_, el_] /; (nodeData[tree] =!= el && 
    Extract[tree, Delete[Position[tree, el][[1]], -1]][[4]] =!= {}) :=
    popraviD[
      ReplacePart[tree,
        newTreeD[Extract[tree, Drop[Position[tree, el][[1]], -1]]],
        Drop[Position[tree, el][[1]], -1]]
      ];

(*brisanje notranjega elementa, če je desno poddrevo prazno, levo pa ne*)

brisiEl[tree_, el_] /; (nodeData[tree] =!= el && Extract[tree, Delete[
    Position[tree, el][[1]], -1]][[
      3]] =!= {}) && (Extract[tree, Delete[Position[tree, el][[
        1]], -1]][[4]] == {}) :=
    popraviD[
      ReplacePart[tree,
        newTreeL[Extract[tree, Drop[Position[tree, el][[1]], -1]]],
        Drop[Position[tree, el][[1]], -1]]
      ];

(*brisanje korena, če desno poddrevo ni prazno*)

brisiEl[tree_, el_] /; (nodeData[tree] == el && rightTree[tree] =!= {}) :=
    popraviD[
      ReplacePart[tree, newTreeD[tree], 2]
      ];

(*brisanje korena, če je desno poddrevo prazno, levo pa ne*)
brisiEl[tree_, el_] /; (nodeData[tree] == el && rightTree[tree] == {} &&leftTree[tree] =!= {}) :=
    popraviD[
      ReplacePart[tree, newTreeL[tree], 2]
      ];


(*brisanje seznama elementov*)

brisiSeznam[tree_, l_List] := Fold[brisiEl, tree, l];

Element je enostavno poiskati. Če hočemo surove koordinate elementa, lahko uporabimo že vgrajeno funkcijo Positions[]. Mi bomo raje pot do elementa poiskali tako, da bomo na vsakem koraku vedeli kam moramo zaviti.

(*funkcija "Kjeje" nam da napotke, kako priti od korena do iskanega elementa*)
    
Kjeje[tree_, el_] /; (Position[tree, el] == {}) := "Ni tega v drevesu."
Kjeje[tree_, 
          el_] := ReplaceAll[ReplaceAll[Drop[Position[tree, el][[1]], -1], 3 \
-> levo], 4 -> desno];

Za lepšo predstavitev rabimo še funkcijo, ki nam drevo izriše.

(*funkcija "plotTree" nam izriše drevo*)

diskr = 0.45;
maxnode = 7;
margin = 0.5;
diskbg = {0.05, 0.9, 0.56};
ys = 1;
plot0[emptyTree, stufe_, nextx_] := {nextx, nextx + 1, {}};
plot0[tree_, stufe_, nextx_] :=
    Module[{wx, nextl, nextr, wl, wr, gl, gr, g = {}},
      If[leftTree[
tree] =!= emptyTree, {wl, nextl, gl} = 
    plot0[leftTree[tree], stufe - 1, nextx];
         wx = nextl;
        AppendTo[g, Line[{{wl, ys (stufe - 1)}, {wx, ys stufe}}]];
        AppendTo[g, gl],(*else*) wx = nextx ];
      If[rightTree[tree] =!= emptyTree, {wr, nextr, gr} =
         plot0[rightTree[tree], stufe - 1, wx + 1];
         AppendTo[g, Line[{{wr, ys (stufe - 1)}, {wx, ys stufe}}]];
        AppendTo[g, gr],(*else*) nextr = wx + 1 ];
       g = Join[g, {{RGBColor[
          1, 1, 0], Disk[{wx, ys stufe}, diskr]}, Circle[{wx, ys stufe},
               diskr], Text[nodeData[tree], {wx, ys stufe}] }];
      {wx, nextr, g}
      ];
plotTree[tree_, opts___] :=
Module[{wx, nextx, g, x0, x1},
      {wx, nextx, g} = plot0[tree, 0, 0];
      g = Prepend[g, Line[{{wx, 0}, {wx, ys}}]];
      If[nextx > maxnode, {x0, x1} = {0, nextx - 
        1}, {x0, x1} = {0 - (maxnode - (nextx - 1))/2, nextx - 1 + (
              maxnode - (nextx - 1))/2}
        ];
      Show[Graphics[g],
             opts, AspectRatio -> Automatic, PlotRange -> {{x0 - margin, 
            x1 + margin}, All}]];

Primeri:

Želimo sestaviti AVL-2 drevo iz elementov : Mojca, Manca, Andreja, Jernej, Aleks, Špela, Nina, Jure, Aleš, Pepca, Robi, Andrej.

plotTree[vstaviSeznam[{}, {Mojca, Manca, Andreja, Jernej, Aleks, Špela, Nina, Jure, Aleš, Pepca, Robi, Andrej}]]

image:Graf_avl2_1.jpg


Primer brisanja elementov 32,50,52 in 61 iz drevesa, ki smo ga sestavili iz elementov : 43, 29, 61, 16, 32, 50, 83, 26, 52, 65, 95 in 87.

drevo = vstaviSeznam[{}, {43, 29, 61, 16, 32, 50, 83, 26, 52, 65, 95, 87}];
plotTree[drevo]
plotTree[brisiSeznam[drevo, {32, 50, 52, 61}]]

image:Graf_avl2_2.jpg image:Graf_avl2_3.jpg


Kako najdemo oz. pridemo od korena do elementa 52 v prejšnjem drevesu "drevo":

Kjeje[drevo, 52]
{desno, levo, desno}
Osebna orodja