exnon

1428

Nov 18th, 2020
244
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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, Rückgabewert: Tupel
  16.  
  17. initBT() ->
  18.         {}.
  19.  
  20. %isEmptyBT() überpürft 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:type_is(ElementAtom) == integer) 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.             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.         Hanoi = 1+max(getHoehe(NeuerLinks),getHoehe(Rechts)),
  112.         {Zahl, Hanoi, NeuerLinks, Rechts};
  113.     Element > Zahl ->
  114.         NeuerRechts = insertBT(Rechts,Element),
  115.         Hanoi = 1+max(getHoehe(NeuerRechts),getHoehe(Links)),      
  116.         {Zahl, Hanoi, Links, NeuerRechts};
  117.     true ->
  118.         BTree
  119.     end.
  120.    
  121.  
  122.  
  123. %findBT() wird ein Baum und ein Element übergeben.
  124. %Daraufhin wird das Element im Baum gesucht.
  125. %Falls es im Baum existiert wird die Höhe returned, falls nicht ein Error.
  126. %Entwurf: 2.2 Abbildung 7
  127. %Stelligkeit: 2, Sichtbarkeit: public, Rückgabewert: int
  128. %Wenn der Baum leer ist, kann das Element nicht darin vorkommen und Error (-1) wird returned.
  129. %Das leere Element wird hier ignoriert.
  130.  
  131. findBT({}, _Element) ->
  132.         -1;
  133.  
  134. %BTree Tupel wird zur weiteren Bearbeitung in mehreren Atomen definiert. (ElementAtom = <ELEMENT>, Height = <HÖHE>)
  135. %Das Übergebene Element wird mit dem Element des aktuellen Nodes verglichen
  136. %Sollten die ELement übereinstimmen, wurde das gesuchte Element gefunden und seine Höhe wird returned.
  137. %Falls nicht, werden die beiden Elemente verglichen:
  138. %Ist das gesuchte Element größer als das Element unseres aktuellen Nodes,
  139. %müssen wir im Folgen den im rechten Unterbaum unseres aktuellen Nodes weitersuchen.
  140. %Wenn das gesuchte Element kleiner ist, suchen wir im linken Unterbaum weiter.
  141. %Die Funktion wird erneut mit dem jeweiligen Unterbaum aufgerufen, bis das gesuchte Element gefunden ist oder wir an einem Blatt angekommen sind.
  142. findBT(BTree, Element) ->
  143.         {ElementAtom, Height, Leftsub, Rightsub} = BTree,
  144.             if Element == ElementAtom ->
  145.                 Height;
  146.             Element > ElementAtom ->
  147.                 findBT(Rightsub, Element);
  148.             Element < ElementAtom ->
  149.                 findBT(Leftsub,Element)
  150.             end.
  151.  
  152. %inOrderBT() gibt den Baum in einer aufsteigend sortierten Liste zurück.
  153. %Entwurf: 2.2 Abbildung 8
  154. %Stelligkeit: 1, Sichtbarkeit: public, Rückgabewert: list
  155.  
  156. %Ist der Baum leer wird eine leere Liste returned.
  157. inOrderBT({}) ->
  158.         [];
  159.  
  160. %Ist das aktuelle Node ein Blatt wird das Element des aktuellen Elements in die Liste eingefügt und die Liste wird zurückgegeben.
  161. inOrderBT({ElementAtom,_Height,{},{}}) ->
  162.         [ElementAtom];
  163.  
  164. %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.
  165. %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.
  166. inOrderBT({ElementAtom,_Height,{},Rightsub}) ->
  167.         [ElementAtom] ++ inOrderBT(Rightsub);
  168. %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,
  169. %da sich mit Sicherheit noch ein kleineres Element im Baum befindet.
  170. %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.
  171. inOrderBT({ElementAtom,_Height,Leftsub,{}}) ->
  172.         inOrderBT(Leftsub) ++ [ElementAtom];
  173.  
  174. %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.
  175. %Dann können wir das Element des aktuellen Nodes in die Liste einfügen, da es keine kleineren Element mehr im Baum gibt.
  176. %Um sicherzustellen, dass alle Elementen ihren Platz in der sortierten Liste finden, müssen wir anschließend noch den rechten Unterbaum überprüfen.
  177. %Wir rufen nun also noch inOrderBt mit dem rechten Unterbaum auf.
  178. inOrderBT({ElementAtom,_Height,Leftsub,Rightsub}) ->
  179.         inOrderBT(Leftsub) ++ [ElementAtom] ++ inOrderBT({Rightsub}).
  180.  
  181. %%Wenn wir einen Leerenbaum als Parameter erhalten, gibt es das gewünschte Element nicht im BTree
  182. deleteBTree({}, _Element) -> {};
  183.  
  184. deleteBTree(BTree = {ElementAtom,Height,Links,Rechts}, Element) ->
  185.     if %%Wir haben 3 Cases hier:
  186.         %a) Element ist Größer als das ElementAtom vom root, b) es ist kleiner und c) es ist gleich groß
  187.        
  188.         %a) Hier wird "tiefer" im Baum nach dem Element gesucht, anschließend wird die Höhe korrigiert und es wird ein ErsatzKnoten zurückgegeben
  189.         Element > ElementAtom ->
  190.             NeuRechts = deleteBTree(Rechts, Element),
  191.             Hanoi = findHeight(NeuRechts, Links),
  192.             {ElementAtom,Hanoi,Links,NeuRechts};
  193.         %b) Hier geschieht das Equivalente für den Linkenbaumteil
  194.         Element < ElementAtom ->    
  195.             NeuLinks = deleteBTree(Links, Element),
  196.             Hanoi = findHeight(NeuLinks, Rechts),
  197.             {ElementAtom,Hanoi,NeuLinks,Rechts};
  198.         %c) Hier haben wir unser Element gefunden.
  199.         %Nun wird abgefragt ob das Node nur leere Linke und Rechte Teilbäume hat oder ob es beide hat.
  200.         Element == ElementAtom ->
  201.             if  %Beim Fall dass es nur einen Teilbaum gibt, wird einfach der Linke, bzw. Rechte Teilbaum zurückgegeben.
  202.                 BTree == {ElementAtom, Height, Links,{}} ->
  203.                     Links;
  204.                 BTree == {ElementAtom, Height, {},Rechts} ->
  205.                     Rechts;
  206.                 BTree == {ElementAtom, Height, {},{}} ->
  207.                 {} end;
  208.                 %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.
  209.                 BTree == {ElementAtom, Height, Links,Rechts} ->
  210.                     Kleinster = kLZahl(Rechts), %Findet uns die Kleinste Zahl vom übergebenen Baum
  211.                     RechtsNeu = deleteBTree(Rechts, Kleinster), %Der Node von dem wir den Ersatzwert nehmen, wird gelöscht
  212.                     Hanoi = findHeight(RechtsNeu, Links),
  213.                     {Kleinster, Hanoi, Links, RechtsNeu}
  214.             end.
  215.  
  216. kLZahl({ElementAtom, _Height, {}, _Rechts}) ->
  217.     ElementAtom;
  218. kLZahl({_ElementAtom, _Height, Links, _Rechts}) ->
  219.     kLZahl(Links).
  220.  
  221.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×