Advertisement
exnon

sami1245

Nov 18th, 2020
2,890
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Erlang 10.97 KB | None | 0 0
  1. %% coding: latin-1
  2. %Quellen:
  3. %http://erlang.org/documentation/doc-5.3/doc/getting_started/getting_started.html
  4. %2.
  5. %https://erlang.org/doc/reference_manual/expressions.html#:~:text=Erlang%20uses%20single%20assignment,%20that,its%20value%20can%20be%20ignored.&text=Variables%20starting%20with%20underscore%20(_),are%20normal%20variables,%20not%20anonymous
  6. %3.
  7. %VL vom 03.11.2020
  8. %4.
  9. %util.erl
  10. -module(btree).
  11. -export([initBT/0,isEmptyBT/1,isBT/1,isEqualBT/2, insertBT/2, findBT/2, inOrderBT/1, deleteBTree/2]).
  12.  
  13. %initBT() erzeugt einen leeren Baum.
  14. %Doku: 2.2 Abbildung 1
  15. %Stelligkeit: 0, Sichtbarkeit: public, Rueckgabewert: Tupel
  16.  
  17. initBT() ->
  18.         {}.
  19.  
  20. %isEmptyBT() ueberpuerft ob ein Baum ein leerer Baum ist.
  21. %Doku: 2.2 Abbildung 2
  22. %Stelligkeit: 1, Sichtbarkeit: public, Rückgabewert: bool
  23.  
  24. isEmptyBT(BTree) ->
  25.         BTree == {}.
  26.  
  27. %isBT() überprüft einen Baum auf seine Korrekt nach Definition
  28. %Die einzelnen Constraints für einen korrekten Baum werden im folgenden noch detaillierter beschrieben
  29. %Entwurf: 2.2 Abbildung 3
  30. %Stelligkeit: 1, Sichtbarkeit: public, Rückgabewert: bool
  31.  
  32. %BTree wird um ein Minimum und Maximum erweitert.
  33. isBT(BTree) ->
  34.         isBT(BTree, 0, inf).
  35.  
  36. %Sollte der betrachtete Baum leer sein, spielt das MInimum und Maximum keine weitere Rolle - der Baum ist korrekt.
  37. isBT(_BTree = {}, _Minimum, _Maximum) ->
  38.         true;
  39.  
  40. %Sortierung:
  41.     %Minimum und Maximum bilden nun ein Intervall in dem das Element des übergebenen Baumes liegen darf.
  42. %Die Syntaktische Korrektheit wird überprüft:
  43.     %Ist das Tupel als die richtige Datenstruktur verwendet?
  44.         %Ist das Element eines jeden Teilbaumes vom Typ Ganzzahl (Integer)?
  45. %Ist die Höhe im Baum richtig angegeben?
  46.     %Die richtige Höhe nach Definition (siehe findHeight) wird errechnet und mit der übergebenen Höhe verglichen.
  47. %Rekursiver Aufruf der Teilbäume:
  48. %   Sind die Bedingungen für einen korrekten BST in allen Teilbäumen erfüllt?
  49. isBT(_BTree = {ElementAtom,Height,Leftsub,Rightsub}, Minimum, Maximum) when ElementAtom>Minimum, ElementAtom<Maximum ->
  50.         (util:is_integer(ElementAtom)) and
  51.         (findHeight(Leftsub,Rightsub) == Height) and
  52.         isBT(Leftsub, Minimum, ElementAtom) and
  53.         isBT(Rightsub, ElementAtom, Maximum);
  54.  
  55. %Sollte Unsinn als Baum übergeben werden, der nicht der richtigen Datenstruktur folgt, wird false returned.
  56. isBT(_BTree, _Minimum, _Maximum) ->
  57.         false.
  58.  
  59.  
  60. %Private Hilfsfunktion zum Errechnen der Höhe eines Teilbaumes für die folgende Funktion
  61. %Wenn die Höhe zweier, nicht leerer Unterbäume gefunden werden soll, wird die Höhe der beiden Unterbäume verglichen und der "höhere" wird mit 1 addiert. [nach Definition Höhe (siehe VL)]
  62. findHeight(_Leftsub = {_ElementLeft,HeightLeft,_Leftsubsub,_Rightsubsub},
  63.         _Rightsub = {_ElementRight,HeightRight,_Leftsubsub,_Rightsubsub}) ->
  64.             max(HeightLeft, HeightRight) + 1;
  65.  
  66. %Wenn beide Unterbäume leer sind, sind beide leeren Bäume mit Höhe 0 zu interpretieren und 1 wird returned.
  67. findHeight(_Leftsub = {}, _Rightsub = {}) ->
  68.             0 + 1;
  69.  
  70. %Sollte nur einer der beiden Unterbäume leer sein, muss dies als Höhe 0 interpretiert werden.
  71. %Der jeweils andere Baum ist also auch ohne Vergleich der "höhere".
  72. findHeight(_Leftsub = {}, _Rightsub = {_ElementRight,_HeightRight,_Leftsubsub,_Rightsubsub}) ->
  73.             _HeightRight + 1;
  74.  
  75. findHeight(_Leftsub = {_ElementLeft,_HeightLeft,_Leftsubsub,_Rightsubsub}, _Rightsub = {}) ->
  76.             _HeightLeft + 1.
  77.            
  78. %isEqual überprüft die semantische Gleicheit zweier Bäume.
  79. %Sollte keiner der beiden Bäume leer sein, wird inOrderBT benutzt um die beiden Bäume als sortierte Liste umzuformen
  80. %und im Folgenden auf syntaktische Gleichheit zu überprüfen.
  81. %Doku: 2.2 Abbildung 4
  82. %Stelligkeit: 2, Sichtbarkeit: public, Rückgabewert: bool
  83.  
  84. isEqualBT({},{}) ->
  85.         true;
  86.  
  87. isEqualBT(_BaumEins, {}) ->
  88.         false;
  89.  
  90. isEqualBT({}, _BaumZwei) ->
  91.         false;
  92.  
  93. isEqualBT(_BaumEins,_BaumZwei) ->
  94.         inOrderBT(_BaumEins)==inOrderBT(_BaumZwei).
  95.  
  96. %Hilfsmethode für Hoehe
  97. getHoehe({_Zahl, Hoehe, _Liniks, _Rechts}) -> Hoehe;
  98. getHoehe ({}) -> 0.
  99.  
  100.  
  101. %insertBT fügt einen neuen Node dem BTree hinzu und positioniert es an der richtigen stelle
  102. %Stelligkeit: 2, Sichtbarkeit: Public, Rückgabewert: Tupel
  103. %Doku: TODO
  104. insertBT({},Element) ->
  105.     {Element, 1, {}, {}};
  106.  
  107. insertBT(BTree= {Zahl, Hoehe, Links, Rechts}, Element) ->
  108.     BTree = {Zahl, Hoehe, Links, Rechts},
  109.     if Element < Zahl ->
  110.         NeuerLinks = insertBT(Links, Element),
  111.         case getHoehe(NeuerLinks) >= getHoehe(Rechts) orelse (Hoehe-getHoehe(NeuerLinks) >0) of true ->
  112.             {Zahl, Hoehe, NeuerLinks, Rechts};
  113.         false ->
  114.             {Zahl, Hoehe+1, NeuerLinks, Rechts}
  115.         end;
  116.     Element > Zahl ->
  117.         NeuerRechts = insertBT(Rechts,Element),
  118.         case getHoehe(Links) >= getHoehe(NeuerRechts) orelse (Hoehe-getHoehe(NeuerRechts) >0) of
  119.         true ->
  120.             {Zahl, Hoehe, Links, NeuerRechts};
  121.         false ->
  122.             {Zahl, Hoehe+1, Links, NeuerRechts}
  123.         end;
  124.     true ->
  125.         BTree
  126.     end.
  127.    
  128.  
  129.  
  130. %findBT() wird ein Baum und ein Element übergeben.
  131. %Daraufhin wird das Element im Baum gesucht.
  132. %Falls es im Baum existiert wird die Höhe returned, falls nicht ein Error.
  133. %Entwurf: 2.2 Abbildung 7
  134. %Stelligkeit: 2, Sichtbarkeit: public, Rückgabewert: int
  135. %Wenn der Baum leer ist, kann das Element nicht darin vorkommen und Error (-1) wird returned.
  136. %Das leere Element wird hier ignoriert.
  137.  
  138. findBT({}, _Element) ->
  139.         -1;
  140.  
  141. %BTree Tupel wird zur weiteren Bearbeitung in mehreren Atomen definiert. (ElementAtom = <ELEMENT>, Height = <HÖHE>)
  142. %Das Übergebene Element wird mit dem Element des aktuellen Nodes verglichen
  143. %Sollten die ELement übereinstimmen, wurde das gesuchte Element gefunden und seine Höhe wird returned.
  144. %Falls nicht, werden die beiden Elemente verglichen:
  145. %Ist das gesuchte Element größer als das Element unseres aktuellen Nodes,
  146. %müssen wir im Folgen den im rechten Unterbaum unseres aktuellen Nodes weitersuchen.
  147. %Wenn das gesuchte Element kleiner ist, suchen wir im linken Unterbaum weiter.
  148. %Die Funktion wird erneut mit dem jeweiligen Unterbaum aufgerufen, bis das gesuchte Element gefunden ist oder wir an einem Blatt angekommen sind.
  149. findBT(BTree, Element) ->
  150.         {ElementAtom, Height, Leftsub, Rightsub} = BTree,
  151.             if Element == ElementAtom ->
  152.                 Height;
  153.             Element > ElementAtom ->
  154.                 findBT(Rightsub, Element);
  155.             Element < ElementAtom ->
  156.                 findBT(Leftsub,Element)
  157.             end.
  158.  
  159. %inOrderBT() gibt den Baum in einer aufsteigend sortierten Liste zurück.
  160. %Entwurf: 2.2 Abbildung 8
  161. %Stelligkeit: 1, Sichtbarkeit: public, Rückgabewert: list
  162.  
  163. %Ist der Baum leer wird eine leere Liste returned.
  164. inOrderBT({}) ->
  165.         [];
  166.  
  167. %Ist das aktuelle Node ein Blatt wird das Element des aktuellen Elements in die Liste eingefügt und die Liste wird zurückgegeben.
  168. inOrderBT({ElementAtom,_Height,{},{}}) ->
  169.         [ElementAtom];
  170.  
  171. %Wenn das aktuelle Node nur einen rechten Unterbaum hat, können wir davon ausgehen, dass kein kleineres Element mehr gefunden wir dals das Element in dem aktuellen Node.
  172. %Also wird es in die Liste eingefügt und die Funktion wird nachfolgend mit dem rechten Unterbaum, der auschließlich größere ELemente enthalten wird, aufgerufen.
  173. inOrderBT({ElementAtom,_Height,{},Rightsub}) ->
  174.         [ElementAtom] ++ inOrderBT(Rightsub);
  175. %Falls das aktuelle Node keinen rechten Unterbaum, dafür aber einen linken besitzt, können wir das Element des aktuellen noch nicht in die liste einfügen,
  176. %da sich mit Sicherheit noch ein kleineres Element im Baum befindet.
  177. %Wir müssen also zunächst den linken Unterbaum an inOrderBT übergeben und können danach das Element des aktuellen Nodes in die Liste einfügen.
  178. inOrderBT({ElementAtom,_Height,Leftsub,{}}) ->
  179.         inOrderBT(Leftsub) ++ [ElementAtom];
  180.  
  181. %Im Falle, dass das aktuelle Node sowohl einen linken als auch einen rechten Unterbaum besitzt, müssen wir zunächst den linken Unterbaum an inOrderBT übergeben um die kleineren ELement zu finden.
  182. %Dann können wir das Element des aktuellen Nodes in die Liste einfügen, da es keine kleineren Element mehr im Baum gibt.
  183. %Um sicherzustellen, dass alle Elementen ihren Platz in der sortierten Liste finden, müssen wir anschließend noch den rechten Unterbaum überprüfen.
  184. %Wir rufen nun also noch inOrderBt mit dem rechten Unterbaum auf.
  185. inOrderBT({ElementAtom,_Height,Leftsub,Rightsub}) ->
  186.         inOrderBT(Leftsub) ++ [ElementAtom] ++ inOrderBT({Rightsub}).
  187.  
  188. %%Wenn wir einen Leerenbaum als Parameter erhalten, gibt es das gewünschte Element nicht im BTree
  189. deleteBTree({}, _Element) -> {};
  190.  
  191. deleteBTree(BTree = {ElementAtom,Height,Links,Rechts}, Element) ->
  192.     if %%Wir haben 3 Cases hier:
  193.         %a) Element ist Größer als das ElementAtom vom root, b) es ist kleiner und c) es ist gleich groß
  194.        
  195.         %a) Hier wird "tiefer" im Baum nach dem Element gesucht, anschließend wird die Höhe korrigiert und es wird ein ErsatzKnoten zurückgegeben
  196.         Element > ElementAtom ->
  197.             NeuRechts = deleteBTree(Rechts, Element),
  198.             Hanoi = findHeight(NeuRechts, Links),
  199.             {ElementAtom,Hanoi,Links,NeuRechts};
  200.         %b) Hier geschieht das Equivalente für den Linkenbaumteil
  201.         Element < ElementAtom ->    
  202.             NeuLinks = deleteBTree(Links, Element),
  203.             Hanoi = findHeight(NeuLinks, Rechts),
  204.             {ElementAtom,Hanoi,NeuLinks,Rechts};
  205.         %c) Hier haben wir unser Element gefunden.
  206.         %Nun wird abgefragt ob das Node nur leere Linke und Rechte Teilbäume hat oder ob es beide hat.
  207.         Element == ElementAtom ->
  208.             if  %Beim Fall dass es nur einen Teilbaum gibt, wird einfach der Linke, bzw. Rechte Teilbaum zurückgegeben.
  209.                 BTree == {ElementAtom, Height, Links,{}} ->
  210.                     Links;
  211.                 BTree == {ElementAtom, Height, {},Rechts} ->
  212.                     Rechts;
  213.                 BTree == {ElementAtom, Height, {},{}} ->
  214.                 {} end;
  215.                 %Hier wird der richtige Ersatz des rechten Teilbaumes gesucht, die Ursprüngliche Node mit dem Ersatz gelöscht und ein korrekter Ersatzbaum wir zurückgegeben.
  216.                 BTree == {ElementAtom, Height, Links,Rechts} ->
  217.                     Kleinster = kLZahl(Rechts), %Findet uns die Kleinste Zahl vom übergebenen Baum
  218.                     RechtsNeu = deleteBTree(Rechts, Kleinster), %Der Node von dem wir den Ersatzwert nehmen, wird gelöscht
  219.                     Hanoi = findHeight(RechtsNeu, Links),
  220.                     {Kleinster, Hanoi, Links, RechtsNeu}
  221.             end.
  222. %max(X,Y)->
  223. %    if X>Y ->
  224. %        X;
  225. %       Y>X ->
  226. %        Y;
  227. %        X==Y ->
  228. %        X
  229. %    end.
  230. kLZahl(_BTree = {ElementAtom, _Height, {}, _Rechts}) ->
  231.     ElementAtom;
  232. kLZahl(_BTree = {_ElementAtom, _Height, Links, _Rechts}) ->
  233.     kLZahl(Links).
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement