Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- %% coding: latin-1
- %Quellen:
- %http://erlang.org/documentation/doc-5.3/doc/getting_started/getting_started.html
- %2.
- %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
- %3.
- %VL vom 03.11.2020
- %4.
- %util.erl
- -module(btree).
- -export([initBT/0,isEmptyBT/1,isBT/1,isEqualBT/2, insertBT/2, findBT/2, inOrderBT/1, deleteBTree/2]).
- %initBT() erzeugt einen leeren Baum.
- %Doku: 2.2 Abbildung 1
- %Stelligkeit: 0, Sichtbarkeit: public, Rueckgabewert: Tupel
- initBT() ->
- {}.
- %isEmptyBT() ueberpuerft ob ein Baum ein leerer Baum ist.
- %Doku: 2.2 Abbildung 2
- %Stelligkeit: 1, Sichtbarkeit: public, Rückgabewert: bool
- isEmptyBT(BTree) ->
- BTree == {}.
- %isBT() überprüft einen Baum auf seine Korrekt nach Definition
- %Die einzelnen Constraints für einen korrekten Baum werden im folgenden noch detaillierter beschrieben
- %Entwurf: 2.2 Abbildung 3
- %Stelligkeit: 1, Sichtbarkeit: public, Rückgabewert: bool
- %BTree wird um ein Minimum und Maximum erweitert.
- isBT(BTree) ->
- isBT(BTree, 0, inf).
- %Sollte der betrachtete Baum leer sein, spielt das MInimum und Maximum keine weitere Rolle - der Baum ist korrekt.
- isBT(_BTree = {}, _Minimum, _Maximum) ->
- true;
- %Sortierung:
- %Minimum und Maximum bilden nun ein Intervall in dem das Element des übergebenen Baumes liegen darf.
- %Die Syntaktische Korrektheit wird überprüft:
- %Ist das Tupel als die richtige Datenstruktur verwendet?
- %Ist das Element eines jeden Teilbaumes vom Typ Ganzzahl (Integer)?
- %Ist die Höhe im Baum richtig angegeben?
- %Die richtige Höhe nach Definition (siehe findHeight) wird errechnet und mit der übergebenen Höhe verglichen.
- %Rekursiver Aufruf der Teilbäume:
- % Sind die Bedingungen für einen korrekten BST in allen Teilbäumen erfüllt?
- isBT(_BTree = {ElementAtom,Height,Leftsub,Rightsub}, Minimum, Maximum) when ElementAtom>Minimum, ElementAtom<Maximum ->
- (util:is_integer(ElementAtom)) and
- (findHeight(Leftsub,Rightsub) == Height) and
- isBT(Leftsub, Minimum, ElementAtom) and
- isBT(Rightsub, ElementAtom, Maximum);
- %Sollte Unsinn als Baum übergeben werden, der nicht der richtigen Datenstruktur folgt, wird false returned.
- isBT(_BTree, _Minimum, _Maximum) ->
- false.
- %Private Hilfsfunktion zum Errechnen der Höhe eines Teilbaumes für die folgende Funktion
- %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)]
- findHeight(_Leftsub = {_ElementLeft,HeightLeft,_Leftsubsub,_Rightsubsub},
- _Rightsub = {_ElementRight,HeightRight,_Leftsubsub,_Rightsubsub}) ->
- max(HeightLeft, HeightRight) + 1;
- %Wenn beide Unterbäume leer sind, sind beide leeren Bäume mit Höhe 0 zu interpretieren und 1 wird returned.
- findHeight(_Leftsub = {}, _Rightsub = {}) ->
- 0 + 1;
- %Sollte nur einer der beiden Unterbäume leer sein, muss dies als Höhe 0 interpretiert werden.
- %Der jeweils andere Baum ist also auch ohne Vergleich der "höhere".
- findHeight(_Leftsub = {}, _Rightsub = {_ElementRight,_HeightRight,_Leftsubsub,_Rightsubsub}) ->
- _HeightRight + 1;
- findHeight(_Leftsub = {_ElementLeft,_HeightLeft,_Leftsubsub,_Rightsubsub}, _Rightsub = {}) ->
- _HeightLeft + 1.
- %isEqual überprüft die semantische Gleicheit zweier Bäume.
- %Sollte keiner der beiden Bäume leer sein, wird inOrderBT benutzt um die beiden Bäume als sortierte Liste umzuformen
- %und im Folgenden auf syntaktische Gleichheit zu überprüfen.
- %Doku: 2.2 Abbildung 4
- %Stelligkeit: 2, Sichtbarkeit: public, Rückgabewert: bool
- isEqualBT({},{}) ->
- true;
- isEqualBT(_BaumEins, {}) ->
- false;
- isEqualBT({}, _BaumZwei) ->
- false;
- isEqualBT(_BaumEins,_BaumZwei) ->
- inOrderBT(_BaumEins)==inOrderBT(_BaumZwei).
- %Hilfsmethode für Hoehe
- getHoehe({_Zahl, Hoehe, _Liniks, _Rechts}) -> Hoehe;
- getHoehe ({}) -> 0.
- %insertBT fügt einen neuen Node dem BTree hinzu und positioniert es an der richtigen stelle
- %Stelligkeit: 2, Sichtbarkeit: Public, Rückgabewert: Tupel
- %Doku: TODO
- insertBT({},Element) ->
- {Element, 1, {}, {}};
- insertBT(BTree= {Zahl, Hoehe, Links, Rechts}, Element) ->
- BTree = {Zahl, Hoehe, Links, Rechts},
- if Element < Zahl ->
- NeuerLinks = insertBT(Links, Element),
- case getHoehe(NeuerLinks) >= getHoehe(Rechts) orelse (Hoehe-getHoehe(NeuerLinks) >0) of true ->
- {Zahl, Hoehe, NeuerLinks, Rechts};
- false ->
- {Zahl, Hoehe+1, NeuerLinks, Rechts}
- end;
- Element > Zahl ->
- NeuerRechts = insertBT(Rechts,Element),
- case getHoehe(Links) >= getHoehe(NeuerRechts) orelse (Hoehe-getHoehe(NeuerRechts) >0) of
- true ->
- {Zahl, Hoehe, Links, NeuerRechts};
- false ->
- {Zahl, Hoehe+1, Links, NeuerRechts}
- end;
- true ->
- BTree
- end.
- %findBT() wird ein Baum und ein Element übergeben.
- %Daraufhin wird das Element im Baum gesucht.
- %Falls es im Baum existiert wird die Höhe returned, falls nicht ein Error.
- %Entwurf: 2.2 Abbildung 7
- %Stelligkeit: 2, Sichtbarkeit: public, Rückgabewert: int
- %Wenn der Baum leer ist, kann das Element nicht darin vorkommen und Error (-1) wird returned.
- %Das leere Element wird hier ignoriert.
- findBT({}, _Element) ->
- -1;
- %BTree Tupel wird zur weiteren Bearbeitung in mehreren Atomen definiert. (ElementAtom = <ELEMENT>, Height = <HÖHE>)
- %Das Übergebene Element wird mit dem Element des aktuellen Nodes verglichen
- %Sollten die ELement übereinstimmen, wurde das gesuchte Element gefunden und seine Höhe wird returned.
- %Falls nicht, werden die beiden Elemente verglichen:
- %Ist das gesuchte Element größer als das Element unseres aktuellen Nodes,
- %müssen wir im Folgen den im rechten Unterbaum unseres aktuellen Nodes weitersuchen.
- %Wenn das gesuchte Element kleiner ist, suchen wir im linken Unterbaum weiter.
- %Die Funktion wird erneut mit dem jeweiligen Unterbaum aufgerufen, bis das gesuchte Element gefunden ist oder wir an einem Blatt angekommen sind.
- findBT(BTree, Element) ->
- {ElementAtom, Height, Leftsub, Rightsub} = BTree,
- if Element == ElementAtom ->
- Height;
- Element > ElementAtom ->
- findBT(Rightsub, Element);
- Element < ElementAtom ->
- findBT(Leftsub,Element)
- end.
- %inOrderBT() gibt den Baum in einer aufsteigend sortierten Liste zurück.
- %Entwurf: 2.2 Abbildung 8
- %Stelligkeit: 1, Sichtbarkeit: public, Rückgabewert: list
- %Ist der Baum leer wird eine leere Liste returned.
- inOrderBT({}) ->
- [];
- %Ist das aktuelle Node ein Blatt wird das Element des aktuellen Elements in die Liste eingefügt und die Liste wird zurückgegeben.
- inOrderBT({ElementAtom,_Height,{},{}}) ->
- [ElementAtom];
- %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.
- %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.
- inOrderBT({ElementAtom,_Height,{},Rightsub}) ->
- [ElementAtom] ++ inOrderBT(Rightsub);
- %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,
- %da sich mit Sicherheit noch ein kleineres Element im Baum befindet.
- %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.
- inOrderBT({ElementAtom,_Height,Leftsub,{}}) ->
- inOrderBT(Leftsub) ++ [ElementAtom];
- %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.
- %Dann können wir das Element des aktuellen Nodes in die Liste einfügen, da es keine kleineren Element mehr im Baum gibt.
- %Um sicherzustellen, dass alle Elementen ihren Platz in der sortierten Liste finden, müssen wir anschließend noch den rechten Unterbaum überprüfen.
- %Wir rufen nun also noch inOrderBt mit dem rechten Unterbaum auf.
- inOrderBT({ElementAtom,_Height,Leftsub,Rightsub}) ->
- inOrderBT(Leftsub) ++ [ElementAtom] ++ inOrderBT({Rightsub}).
- %%Wenn wir einen Leerenbaum als Parameter erhalten, gibt es das gewünschte Element nicht im BTree
- deleteBTree({}, _Element) -> {};
- deleteBTree(BTree = {ElementAtom,Height,Links,Rechts}, Element) ->
- if %%Wir haben 3 Cases hier:
- %a) Element ist Größer als das ElementAtom vom root, b) es ist kleiner und c) es ist gleich groß
- %a) Hier wird "tiefer" im Baum nach dem Element gesucht, anschließend wird die Höhe korrigiert und es wird ein ErsatzKnoten zurückgegeben
- Element > ElementAtom ->
- NeuRechts = deleteBTree(Rechts, Element),
- Hanoi = findHeight(NeuRechts, Links),
- {ElementAtom,Hanoi,Links,NeuRechts};
- %b) Hier geschieht das Equivalente für den Linkenbaumteil
- Element < ElementAtom ->
- NeuLinks = deleteBTree(Links, Element),
- Hanoi = findHeight(NeuLinks, Rechts),
- {ElementAtom,Hanoi,NeuLinks,Rechts};
- %c) Hier haben wir unser Element gefunden.
- %Nun wird abgefragt ob das Node nur leere Linke und Rechte Teilbäume hat oder ob es beide hat.
- Element == ElementAtom ->
- if %Beim Fall dass es nur einen Teilbaum gibt, wird einfach der Linke, bzw. Rechte Teilbaum zurückgegeben.
- BTree == {ElementAtom, Height, Links,{}} ->
- Links;
- BTree == {ElementAtom, Height, {},Rechts} ->
- Rechts;
- BTree == {ElementAtom, Height, {},{}} ->
- {} end;
- %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.
- BTree == {ElementAtom, Height, Links,Rechts} ->
- Kleinster = kLZahl(Rechts), %Findet uns die Kleinste Zahl vom übergebenen Baum
- RechtsNeu = deleteBTree(Rechts, Kleinster), %Der Node von dem wir den Ersatzwert nehmen, wird gelöscht
- Hanoi = findHeight(RechtsNeu, Links),
- {Kleinster, Hanoi, Links, RechtsNeu}
- end.
- %max(X,Y)->
- % if X>Y ->
- % X;
- % Y>X ->
- % Y;
- % X==Y ->
- % X
- % end.
- kLZahl(_BTree = {ElementAtom, _Height, {}, _Rechts}) ->
- ElementAtom;
- kLZahl(_BTree = {_ElementAtom, _Height, Links, _Rechts}) ->
- kLZahl(Links).
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement