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

Iz MaFiRaWiki

Osnovne funkcije

Drevo oz. vozlišče je definirano kot seznam štirih spremenljivk: ravnotežnostni faktor, padatek, levo drevo in desno drevo. Prazno drevo je definirano kot prazen seznam. Osnovne funkcije definirajo kreiranje novega vozlišča ter branje in vstavljanje posameznih spremenjljivk v določeno vozlišče drevesa

  1. emptyTree = {};
  2.  
  3. node[balance_, data_, left_, right_] := {balance, data, left, right}
  4. leftTree[{_, _, left_, _}] := left
  5. rightTree[{_, _, _, right_}] := right
  6. nodeData[{_, data_, _, _}] := data
  7. balanceFactor[{balance_, _, _, _}] := balance
  8. setLeftTree[tree_, left_] :=
  9. node[balanceFactor[tree], nodeData[tree], left, rightTree[tree]]
  10. setRightTree[tree_, right_] :=
  11. node[balanceFactor[tree], nodeData[tree], leftTree[tree], right]
  12. setBalance[tree_, balance_] :=
  13. node[balance, nodeData[tree], leftTree[tree], rightTree[tree]]
  14. setData[tree_, data_] :=
  15. node[balanceFactor[tree], data, leftTree[tree], rightTree[tree]]
  16.  
  17. (* spremenljivke, potrebne pri vstavljenju in brisanju *)
  18. balanceChanged = False;
  19. deleteInProgress = False;
  20. deletedData = Null;

Funkcije za vstavljanje

Sledeče funkcije omogočajo vstavljanje novih elementov v drevo. Novi element se najprej vstavi kot list na pravo mesto, nato pa se ob "plezanju" nazaj po drevesu z rotacijami drevo poravlja (če je seveda potrebno).

Funkcija insert[tree_,data_] vstavi en element v drevo. Funkcija insertList[tree_,data_] pa vstavi v drevo seznam elementov.

  1. insertList[tree_, data_] := Fold[insert, tree, data]
  2. insert[tree_, data_] :=
  3. Module[{}, balanceChanged = False; deleteInProgress = False;
  4. insertNode[tree, data]]
  5.  
  6. (* vstavi element kot list *)
  7. insertNode[emptyTree, data_, Key_: Identity] :=
  8. Module[{}, balanceChanged = True;
  9. node[0, data, emptyTree, emptyTree] ]
  10.  
  11. (* .e je element .e v drevesum, ne naredi ni. *)
  12. insertNode[tree_, data_, Key_: Identity] /;
  13. Order[Key[data], Key[nodeData[tree]]] == 0 := tree
  14.  
  15. (* .e je novi element monj.i, vstavi v levo poddrevo *)
  16. insertNode[tree_, data_, Key_: Identity] /;
  17. Order[Key[data], Key[nodeData[tree]]] > 0 :=
  18. fix[ setLeftTree[tree, insertNode[leftTree[tree], data, Key]], 1]
  19.  
  20. (* sicer je ve.i, vstavi v desno poddrevo *)
  21. insertNode[tree_, data_, Key_: Identity] :=
  22. fix[ setRightTree[tree, insertNode[rightTree[tree], data, Key]], -1]

Funkcije za brisanje

Sledeče funkcije omogočajo brisanje elementov iz drevesa. Najprej se poišče element element, ki ga želimo zbrisati, nato pa je postopek sledeči:

  - če je element list, se ga odstrani
  - če ima element samo enega sina, se ga zamenja s sinom
  - če ima element dva sinova, se ga zamenja z največjim elementom levega poddrevesa

V vseh primerih je treba preveriti, če je prišlo do spremembe ranotežja in drevo poraviti, če je potrebno.

Funkcija remove[tree_, data_] odstrani en element iz drevesa. Funkcija insertList[tree_, data_] pa odstrani iz drevesa seznam elementov.

  1. removeList[tree_, data_] := Fold[remove, tree, data]
  2. remove[tree_, data_] :=
  3. Module[{}, balanceChanged = False; deleteInProgress = True;
  4. deleteNode[tree, data]]
  5.  
  6. (* .e iskanega elementa ni v drevesu, ne naredi ni. *)
  7. deleteNode[emptyTree, data_, Key_: Identity] := emptyTree
  8. (* .e je manj.i, bri.i iz levega poddrevesa *)
  9. deleteNode[tree_, data_, Key_: Identity] /;
  10. Order[Key[data], Key[nodeData[tree]]] > 0 :=
  11. fix[ setLeftTree[tree, deleteNode[leftTree[tree], data, Key]], -1]
  12. (* .e je ve.ji, bri.i iz desnega poddrevesa *)
  13. deleteNode[tree_, data_, Key_: Identity] /;
  14. Order[Key[data], Key[nodeData[tree]]] < 0 :=
  15. fix[ setRightTree[tree, deleteNode[rightTree[tree], data, Key]], 1]
  16. (* na.li smo iskani element, zbri.i *)
  17. deleteNode[tree_, data_, Key_: Identity] :=
  18. Module[{}, balanceChanged = True; delete[tree]]
  19.  
  20. (* .e ima element nima sina ali ima enega sina, ga zamenjaj s tem
  21. sinom *)
  22. delete[tree_] /; rightTree[tree] == emptyTree := leftTree[tree]
  23. delete[tree_] /; leftTree[tree] == emptyTree := rightTree[tree]
  24. (* sicer ima dva sina, zamenjaj ga z najve.jim v levem poddrevesu *)
  25. delete[tree_] :=
  26. Module[{tree1}, tree1 = setLeftTree[tree, del[leftTree[tree]]];
  27. tree1 = setData[tree1, deletedData]; fix[tree1, -1]]
  28.  
  29. del[r_] /; rightTree[r] =!= emptyTree :=
  30. fix[setRightTree[r, del[rightTree[r]]], 1]
  31. del[r_] :=
  32. Module[{}, balanceChanged = True; deletedData = nodeData[r] ;
  33. leftTree[r]]

Funkcije za popravljenje drevesa

Te funkcije popravijo ranotežnostni faktor in ugotovijo, če je potreno drevo popraviti (rotirati).

  1. fix[tree_, mod_] /; balanceChanged && balanceFactor[tree] == 1*mod :=
  2. Module[{}, balanceChanged = If[deleteInProgress, True, False];
  3. setBalance[tree, 0]]
  4. fix[tree_, mod_] /; balanceChanged && balanceFactor[tree] == 0 :=
  5. Module[{}, balanceChanged = If[deleteInProgress, False, True];
  6. setBalance[tree, -1*mod]]
  7. fix[tree_, mod_] /; balanceChanged && balanceFactor[tree] == -1*mod :=
  8. Module[{}, balanceChanged = If[deleteInProgress, True, False];
  9. rotate[tree]]
  10. fix[tree_, mod_] := tree

Funkcije za obračanje drevesa

Te funkcije izvajajo dejanske rotacije drevasa (in poddreves), potrebne za uravnoteženje. Imamo enojne in dvojne rotacije.

  1. rotate[tree_] /;
  2. balanceFactor[tree] == 1 && balanceFactor[rightTree[tree]] >= 0 :=
  3. rotateL[tree]
  4. rotate[tree_] /;
  5. balanceFactor[tree] == 1 && balanceFactor[rightTree[tree]] < 0 :=
  6. rotateDL[tree]
  7.  
  8. rotate[tree_] /;
  9. balanceFactor[tree] == -1 && balanceFactor[leftTree[tree]] <= 0 :=
  10. rotateR[tree]
  11. rotate[tree_] /;
  12. balanceFactor[tree] == -1 && balanceFactor[leftTree[tree]] > 0 :=
  13. rotateDR[tree]
  14. rotate[tree_] := tree
  15.  
  16. rotateL[tree_] := Module[{newRoot, tree1},
  17. newRoot = rightTree[tree];
  18. tree1 = setRightTree[tree, leftTree[newRoot]];
  19. If[deleteInProgress && balanceFactor[newRoot] == 0,
  20. balanceChanged = False;];
  21. tree1 =
  22. setBalance[tree1,
  23. If[deleteInProgress && balanceFactor[newRoot] == 0, 1, 0]];
  24. newRoot = setLeftTree[rightTree[tree], tree1];
  25. newRoot =
  26. setBalance[newRoot,
  27. If[deleteInProgress && balanceFactor[newRoot] == 0, -1, 0]];
  28. newRoot
  29. ]
  30.  
  31. rotateR[tree_] := Module[{newRoot, tree1},
  32. newRoot = leftTree[tree];
  33. tree1 = setLeftTree[tree, rightTree[newRoot]];
  34. If[deleteInProgress && balanceFactor[newRoot] == 0,
  35. balanceChanged = False;];
  36. tree1 =
  37. setBalance[tree1,
  38. If[deleteInProgress && balanceFactor[newRoot] == 0, -1, 0]];
  39. newRoot = setRightTree[leftTree[tree], tree1];
  40. newRoot =
  41. setBalance[newRoot,
  42. If[deleteInProgress && balanceFactor[newRoot] == 0, 1, 0]];
  43. newRoot
  44. ]
  45.  
  46. rotateDL[tree_] := Module[{newRoot, tree1, rightT},
  47. rightT = rightTree[tree];
  48. newRoot = leftTree[rightT];
  49. rightT = setLeftTree[rightT, rightTree[newRoot]];
  50. tree1 = setRightTree[tree, leftTree[newRoot]];
  51. tree1 = setBalance[tree1, If[balanceFactor[newRoot] == 1, -1, 0]];
  52. rightT =
  53. setBalance[rightT, If[balanceFactor[newRoot] == -1, 1, 0]];
  54. newRoot = node[0, nodeData[newRoot], tree1, rightT];
  55. newRoot
  56. ]
  57.  
  58. rotateDR[tree_] := Module[{newRoot, tree1, leftT},
  59. leftT = leftTree[tree];
  60. newRoot = rightTree[leftT];
  61. leftT = setRightTree[leftT, leftTree[newRoot]];
  62. tree1 = setLeftTree[tree, rightTree[newRoot]];
  63. tree1 = setBalance[tree1, If[balanceFactor[newRoot] == -1, 1, 0]];
  64. leftT = setBalance[leftT, If[balanceFactor[newRoot] == 1, -1, 0]];
  65. newRoot = node[0, nodeData[newRoot], leftT, tree1];
  66. newRoot
  67. ]

Funkcija za merjenje globine drevesa

Ta funkcija vrne globino drevesa

  1. depth[emptyTree] := 0
  2. depth[tree_] :=
  3. 1 + Max[ depth[leftTree[tree]], depth[rightTree[tree]] ]
  4. depth[tree_] :=
  5. 1 + Max[ depth[leftTree[tree]], depth[rightTree[tree]] ] 1 + Max[ depth[leftTree[tree]], depth[rightTree[tree]] ]

Funkcija za iskanje po drevesu

Ta funkcija najde vozlišče z iskanim podatkom in vrne poddrevo s tem pozliščem kot korenom. Če podatka ne najde, vrne Null

  1. searchTree[ emptyTree, key_, Key_: Identity ] := Null
  2.  
  3. searchTree[ tree_, key_, Key_: Identity ] /;
  4. Order[ Key[nodeData[tree]], Key[key] ] == 0 := tree
  5.  
  6. searchTree[ tree_, key_, Key_: Identity ] /;
  7. Order[ Key[nodeData[tree]], Key[key] ] < 0 :=
  8. searchTree[ leftTree[tree], key, Key ]
  9.  
  10. searchTree[ tree_, key_, Key_: Identity ] :=
  11. searchTree[ rightTree[tree], key, Key ]

Funkcija za izris drevesa

Funkcija izriše podano drevo

  1. diskr = 0.45;
  2. maxnode = 7;
  3. margin = 0.5;
  4. diskbg = {0.05, 0.9, 0.56};
  5. ys = 1;
  6.  
  7. plot0[ emptyTree, stufe_, nextx_ ] := {nextx, nextx + 1, {}}
  8. plot0[ tree_, stufe_, nextx_ ] :=
  9. Module[{wx, nextl, nextr, wl, wr, gl, gr, g = {}},
  10. If[ leftTree[tree] =!= emptyTree,
  11. {wl, nextl, gl} = plot0[leftTree[tree], stufe - 1, nextx];
  12. wx = nextl;
  13. AppendTo[g, Line[{ {wl, ys (stufe - 1)}, {wx, ys stufe} }]];
  14. AppendTo[g, gl],
  15. (* else *) wx = nextx
  16. ];
  17. If[ rightTree[tree] =!= emptyTree,
  18. {wr, nextr, gr} = plot0[rightTree[tree], stufe - 1, wx + 1];
  19. AppendTo[g, Line[{ {wr, ys (stufe - 1)}, {wx, ys stufe} }]];
  20. AppendTo[g, gr],
  21. (* else *) nextr = wx + 1
  22. ];
  23. g = Join[g,
  24. { {RGBColor[diskbg], Disk[ {wx, ys stufe}, diskr ]},
  25. Circle[{wx, ys stufe}, diskr ],
  26. Text[ Style[nodeData[tree], Larger], {wx, ys stufe} ]
  27. } ];
  28. {wx, nextr, g}
  29. ]
  30.  
  31. plotTree[ tree_, opts___ ] :=
  32. Module[{wx, nextx, g, x0, x1},
  33. {wx, nextx, g} = plot0[tree, 0, 0];
  34. g = Prepend[ g, Line[{{wx, 0}, {wx, ys}}] ];
  35. If[ nextx > maxnode,
  36. {x0, x1} = {0, nextx - 1},
  37. {x0, x1} = {0 - (maxnode - (nextx - 1))/2,
  38. nextx - 1 + (maxnode - (nextx - 1))/2}];
  39. Show[ Graphics[g], opts, AspectRatio -> Automatic,
  40. PlotRange -> {{x0 - margin, x1 + margin}, All} ]
  41. ]
Osebna orodja