Nicht Lineare Abstrakte Datentypen
Die vorliegenden Materialien wurden von André Tempel erstellt und von Daniel Hoherz geprüft. Sollten andere Editoren die Materialien erstellt haben, werden diese explizit genannt.
Abstrakte Datentypen (ADT) sind, ähnlich wie primitive Datentypen (int, double, float, boolean, char,...), Konstruktionen für Objekte, die auf eine bestimmte Art und Weise funktionieren sollen. Ein ADT hat immer eine konkrete Implementation, die Datenstruktur, und eine Schnittstelle, mit welcher ein User arbeiten kann, das Interface. Dem User muss die konkrete Implementation nicht bekannt sein. Nur die vorhanden Operationen, die der ADT können soll, müssen namentlich und in ihrer Funktionsweise über das Interface bekannt sein. Die tatsächliche Umsetzung kann dann unbekannt bleiben.
Ein phylogenetischer Baum ist ein Diagramm, das die evolutionären Beziehungen zwischen Organismen oder Gruppen von Organismen darstellt. Anhand der gemeinsamen Merkmale und geneischer Informationen wird abgeleitet, wie nahe oder enEernt die Arten im evolutionären Sinne miteinander verwandt sind. Solche Bäume helfen, die Geschichte der Entstehung und Diversifizierung von Lebensformen zu rekonstruieren. Vereinfacht betrachten wir den folgenden phylogenetischen Baum.
-
In dieser Aufgabe beschäftigen Sie sich mit der Verwaltung von Tierbezeichnungen, die in einem Binärbaum gespeichert sind. Das Ziel ist es, diese Bezeichnungen nacheinander auszugeben.
Hierzu können Sie sich für einen der beiden Schwierigkeitsgrade entscheiden: die Basisvariante oder die Challengevariante.
Basisvariante
Challengevariante
Implementieren Sie mit Hilfe der notwendigen BinTree-Operationen einen Algorithmus, um den Inhalt des Binärbaums mit dem Namen baum auszugeben.
Vergleichen Sie Ihre Lösung mit der Lösung unten. Beschreiben Sie, in welcher Regelmäßigkeit die Inhalte der Knoten von baum ausgegeben werden.
Lösung anzeigen
println(baum1.getItem());
println(baum2.getItem());
println(baum2.getLeft().getItem());
println(baum2.getRight().getItem());
println(baum3.getItem());
println(baum3.getLeft().getItem());
println(baum3.getLeft().getLeft().getItem());
println(baum3.getLeft().getRight().getItem());
println(baum3.getRight().getItem());
println(baum3.getRight().getLeft().getItem());
println(baum3.getRight().getRight().getItem());
Untersuchen Sie, wie Ihr Lösungsvorschlag bei einem beliebigen Binärbaum funktioniert, dessen konkreter Aufbau nicht bekannt ist.
Die Operation preorderAusgabe() soll die in einem Binärbaum gespeicherten Inhalte ausgeben.
Analysieren Sie das (unvollständige) Struktogramm der Operation preorderAusgabe() mit dem phylogenetischen Baum als Übergabe.
Hierfür müssen Sie zunächst die Abfragen der letzten beiden bedingten Anweisungen ergänzen und entscheiden, was in den fehlenden Fällen mit „...“ geschehen soll.
Hinweis: Es muss nicht zwingend etwas passieren!
Erläutern Sie die Notwendigkeit der Abfragen und der Anweisungen.
Unvollständiges Struktogramm
Implementieren Sie im Programm Binärbaumtest die Operation preorderAusgabe() und überprüfen Sie deren Funktionalität.
Betrachten Sie zunächst einen Binärbaum, der nur aus einer Wurzel besteht (Baum 1). Implementieren Sie mit Hilfe der notwendigen Operationen einen Algorithmus, um den Inhalt von baum1 auszugeben.
Betrachten Sie nun Baum 2. Implementieren Sie einen weiteren Algorithmus, um den Inhalt des Binärbaums mit dem Namen baum2 auszugeben.
Betrachten Sie nun Baum 3. Implementieren Sie einen weiteren Algorithmus, um den Inhalt des Binärbaums mit dem Namen baum3 auszugeben.
Vergleichen Sie Ihre Lösungen mit der Lösung unten. Beschreiben Sie, in welcher Regelmäßigkeit die Inhalte der Knoten von baum3 ausgegeben werden.
Lösung anzeigen
//Lösungsvorschlag zu a:
println(baum1.getItem());
//Lösungsvorschlag zu b:
println(baum2.getItem());
println(baum2.getLeft().getItem());
println(baum2.getRight().getItem());
//Lösungsvorschlag zu c:
println(baum3.getItem());
println(baum3.getLeft().getItem());
println(baum3.getLeft().getLeft().getItem());
println(baum3.getLeft().getRight().getItem());
println(baum3.getRight().getItem());
println(baum3.getRight().getLeft().getItem());
println(baum3.getRight().getRight().getItem());
Untersuchen Sie, wie Ihre Lösung bei einem beliebigen Binärbaum funktioniert, dessen konkreter Aufbau nicht bekannt ist.
Die Operation preorderAusgabe() soll die in einem Binärbaum gespeicherten Inhalte ausgeben.
Analysieren Sie das (unvollständige) Struktogramm der Operation preorderAusgabe() mit dem phylogenetischen Baum als Übergabe.
Erläutern Sie die Notwendigkeit der Abfragen und die Anweisungen in den letzten beiden bedingten Anweisungen.
Unvollständiges Struktogramm
Implementieren Sie im Programm Binärbaumtest die Operation preorderAusgabe() und überprüfen Sie deren Funktionalität.
-
Die Operation
preorderAusgaberuft sich während der Ausführung wieder selbst auf. So eine Operation bezeichnet man als eine rekursive Operation.
Entscheiden Sie, ob die unten dargestellte Reihenfolge der Operationsaufrufe korrekt ist und korrigieren Sie diese gegebenenfalls. Der Vereinfachung wegen wird der entsprechende Binärbaum durch seinen Wurzelinhalt benannt.
Geben Sie außerdem an, welche Namen in welcher Reihenfolge ausgegeben werden.
preorderAusgabe(Theria)
preorderAusgabe(Beuteltiere)
preorderAusgabe(Amerikanisches Beuteltier)
preorderAusgabe(Australisches Beuteltier)
preorderAusgabe(Plazentatiere)
preorderAusgabe(Laurasiatheria)
preorderAusgabe(Euachontoglires)
Informieren Sie sich zur Inorder- und Postordertraversierung im Internet.
Entwickeln Sie zunächst beide Operationen in Wortform, analog zur Preordertraversierung.
Implementieren Sie die beiden fehlenden Operationen in BinTreeTest und führen Sie je einen Test auf den phylogenetischen Baum aus.
Implementieren Sie eine Operation int zaehleKnoten(BinTree b) in BinTreeTest, welche die Anzahl der Knoten eines übergebenen Binärbaumes zählt und zurückgibt.
Testen Sie die Operation.
-
Geben Sie zum nachfolgenden Binärbaum die Ausgaben der drei Traversierungen an.
-
Gegeben ist der folgenden Binärbaum.
Bestimmen Sie jeweils die entsprechende Ausgabe, wenn eine Preorder-, Inorder- und Postordertraversierung auf diesen Baum angewendet wird.
Von einem unbekannten Binärbaum sind die Preorder- und die Inordertraversierungen bekannt:
Preorder: 1, 2, 4, 3, 5, 6, 7
Inorder: 4, 2, 1, 6, 5, 7, 3
Rekonstruieren Sie den Binärbaum mit Hilfe der bekannten Traversierungen.
Untersuchen Sie, welche Traversierungen eines unbekannten Baumes vorliegen müssen, um diesen eindeutig rekonstruieren zu können.
- (Partnerarbeit) Um mathematische Ausdrücke durch Programme auszuwerten, muss der Ausdruck in eine geeignete Repräsentation gebracht werden. Eine mögliche Repräsentation ist der abstrakte Syntaxbaum, wie er für einen gegebenen Ausdruck in der Abbildung rechts dargestellt ist.
Untersuchen Sie am vorliegenden Baum, welche Traversierung aus einem Syntaxbaum einen korrekten mathematischen Term ausgibt.
Erstellen Sie einen Syntaxbaum für den Term (18+23)*(34-5)+(-2)*(1-15)*(25+2)
Bei einem Informatiksystem, wie einem sozialen Netzwerk, müssen sehr häufig riesige Mengen an Nutzerprofilen angelegt und verwaltet werden.
Bei einer Anmeldung muss das dahinterliegende System den entsprechenden Nutzernamen finden und mit dem eingegebenen Passwort vergleichen. Dies soll möglichst schnell ablaufen, da niemand minutenlang auf einen Login warten möchte.
Würde man die Anmeldedaten der Profile in einer linearen Datenstruktur, wie einer dynamischen Reihung, speichern, würde bei einer so hohen Profilanzahl jeder Login recht lange dauern.
In einem konkreten Beispiel sollen die folgenden Profile verwaltet werden.
Untersuchen wir die Anordnung der Profile im folgenden Vorschlag.
Aufgabe
Analysieren Sie den Aufbau des abgebildeten Binärbaums. Achten Sie insbesondere darauf, wie die Inhalte der Knoten angeordnet sind.
Dieser Binärbaum ist nach einer Sortierung aufgebaut. Für jeden Knoten gilt, dass die Inhalte aller Knoten in seinem linken Teilbaum, falls dieser nicht leer ist, lexikografisch (alphabetisch) kleiner sind, als der Inhalt des betrachteten Knotens, und die Inhalte aller Knoten im rechten Teilbaum, sollte dieser nicht leer sein, lexikografisch größer sind.
Schauen wir uns zum Beispiel die Wurzel mit dem Inhalt "jele16" an. "jele16" ist lexikografisch größer, als alle Inhalte des linken Teilbaums und lexikografisch kleiner, als alle Inhalte des rechten Teilbaums.
Selbiges gilt zum Beispiel auch für den Knoten mit dem Inhalt "susi19". "peha01" im linken Teilbaum ist lexikografisch kleiner als "susi19" und "taro16" und "tim93" sind lexikografisch größer.
Ein Binärbaum, in dem eine solche Ordnung (oder auch eine andere: Bei Zahlen zum Beispiel dürfen im linken Teilbaum eines Knotens nur kleinere und im rechten nur größere Zahlen gespeichert werden) gilt, heißt binärer Suchbaum.
Definition Binärer Suchbaum
Ein Binärbaum, in dem die Inhalte nach einer Ordnungsrelation so angeordnet sind,d ass für jeden Knoten gilt:
- Die Inhalte aller Knoten im linken Teilbaum sind bzgl. der Ordnungsrelation kleiner, als der Inhalkt des betrachteten Knotesn,
- Die Inhalte aller Knoten im rechten Teilbaum sind bzgl. der Ordnungsrelation größer, als der Inhalt des betrachteten Knotens,
heißt binärer Suchbaum.
-
Begründen Sie, ob es sich bei den abgebildeten Bäumen um binäre Suchbäume handelt.
- Erstellen Sie Biepsielgraphen der folgenden Objekte.
Einen Baum, der kein Binärbaum ist.
Einen Binärbaum, der kein binärer Suchbaum ist.
Einen binären Suchbaum.
Eine Struktur mit Knoten und Kanten, die kein Baum ist.
Der Nutzer "marco34" möchte sich in unserem Modell mit dem binären Suchbaum anmelden. Also muss das System nach dem Namen "marco34" im binären Suchbaum suchen.
Aufgabe
Entwickeln Sie eine Vorgehensweise, um das Profil von "marco34" zu suchen. Starten Sie oben und nutzen Sie die Ordnung im binären Suchbaum.
Wir nutzen also die Ordnung in unserem Baum:
Der Baum und alle Teilbäume sind binäre Suchbäume. Vergleichen wir also den Inhalt der Wurzel des Hauptbaumes mit "marco34", haben wir den Namen entweder gefunden oder der Inhalt ist größer oder kleiner, bzgl. der Ordnungsrelation (hier lexikografisch), als "marco34". In einem der beiden letzten Fälle wissen wir, dass sich der gesuchte Name im linken oder rechten Teilbaum befinden muss, sollte er überhaupt vorhanden sein. Also können wir den Algorithmus zum Suchen in einem binären Suchbaum in die folgenden Schritte einteilen:
- Ist der aktuelle Teilbaum leer, beende die Suche erfolglos.
- Wenn der Inhalt der Wurzel gleich dem gesuchten Namen ist, gib den Namen zurück. Sonst:
- Wenn der Inhalt der Wurzel kleiner als der gesuchte Name ist, führe die Operation "suche" auf den rechten Teilbaum aus. Sonst:
- Wenn der Inhalt der Wurzel größer als der gesuchte Name ist, führe die Operation "suche" auf den linken Teilbaum aus.
In unserem Beispiel sind vier Vergleiche notwendig, bei 14 gespeicherten Profilen. Dies ist sehr effektiv und entspricht der binären Suche aus dem Einstiegsbeispiel zum Thema Bäume mit den Länderkarten. Man beachte, dass maximal Tiefe des Baumes+1 Schritte notwendig sind, um den gesuchten Inhalt in einem binären Suchbaum zu finden oder festzustellen, dass er nicht enthalten ist. In unserem Beispiel hat der binäre Suchbaum eine Tiefe von 4 und um "tim93" zu finden, sind 5 Vergleiche notwendig.
-
Eine Operation
void suche(BinTree baum, String wert), welche ausgibt, ob das gesuchte Objekt gefunden wurde oder nicht, für die der folgende Pseudocode vorliegt, soll implementiert werden.suche (BinTree baum, String wert) falls baum ist nicht leer ist und wert ist nicht null setze aktuellesElement auf Element der Wurzel von baum falls wert gleich aktuellesElement Gib aus: "Der gesuchte Inhalt wurde gefunden." sonst falls wert kleiner aktuellesElement falls linker Teilbaum von baum nicht leer ist führe suche auf linker Teilbaum von baum und wert aus sonst Gib aus: "Der gesuchte Inhalt wurde nicht gefunden." sonst falls rechter Teilbaum von baum nicht leer ist führe suche auf rechter Teilbaum von baum und wert aus sonst Gib aus: "Der gesuchte Inhalt wurde nicht gefunden."Implementieren Sie die Operation
suchein einem ProgrammSuchbaumtest, das freigegeben ist und erstellen Sie dort einen kleinen binären Suchbaum. Testen Sie Ihr Ergebnis.
Die Klasse hat eine OperationbaumDrucken(BinTree b), welche Sie nutzen können.
-
Der folgende binäre Suchbaum ist gegeben:
Ermitteln Sie die Anzahl der rekursiven Aufrufe, wenn im gegebenen binären Suchbaum nach dem Inhalt 88 gesucht wird.
Ermitteln Sie für alle Elemente des Baumes die Anzahl der Schritte, wie oft die Operation suche jeweils aufgerufen werden muss.
Ein vollständiger Binärbaum ist ein Binärbaum, in dem alle Knoten, außer den Blättern, genau zwei nichtleere Teilbäume besitzen. Der oben abgebildete Binärbaum ist vollständig und hat die Tiefe 3.
Ermitteln Sie für vollständige Binärbäume der Tiefen 4, 5, 6, ..., bis hin zu Tiefe 10 die jeweils resultierende Knotenanzahl.
In einer linearen Datenstruktur, wie einer Reihung oder einer dynamischen Reihung, welche nicht sortiert aufgebaut wurde, kann man ebenfalls Inhalte suchen.
In der folgenden Tabelle sollen die maximale und die mittlere Anzahl der Schritte in einem binären Suchbaum und einer nicht sortierten linearen Datenstruktur miteinander verglichen werden.
| Anzahl der Elemente | mittlere Schrittanzahl in der linearen Struktur | maximale Schrittanzahl im vollständigen binären Suchbaum |
|---|---|---|
| 15 | 7,5 | 4 (Tiefe 3) |
| 31 | ... | ... |
| 63 | ... | ... |
| ... | ... | ... |
Vervollständigen Sie diese Tabelle bis zur Tiefe 10 des binären Suchbaumes. Interpretieren Sie anschließend Ihr Ergebnis und beurteilen Sie den Einsatz von linearen Datenstrukturen und binären Suchbäumen im vorgegebenen Sachkontext.
Die Fluktuation von Nutzern ist meist recht hoch. Deshalb ist es notwendig, dass es eine Möglichkeit gibt, neue Elemente in einen binären Suchbaum einzufügen, wobei die Ordnung des dadurch neu entstandenen Baumes erhalten bleiben muss.
In unserem Beispielbaum wollen wir den Nutzer "manuel55" einfügen.
Aufgabe
Entwickeln Sie eine Vorgehensweise, um das Profil von "manuel55" in den Suchbaum einzufügen. Starten Sie oben und nutzen Sie die Ordnung und die Suche.
Die Strategie der vorher entwickelten Suche ist hierbei sehr nützlich. Zunächst suchen wir "manuel55". Wenn wir an der Stelle sind, wo er sein sollte, dies wird eine leere Stelle sein, erstellen wir einfach einen neuen binären Suchbaum mit Wurzelinhalt "manuel55" und hängen ihn an das entsprechende Blatt.
Aber Vorsicht! Man muss erst vergleichen, dann schauen, ob der Teilbaum, in den man gehen möchte leer ist oder nicht. Nur wenn dieser nicht leer ist, kann man weiter schauen. Wenn wir im obigen Beispiel auf dem Knoten mit "marco34" stehen, schauen wir zunächst, ob der linke Teilbaum leer ist. Da dies der Fall ist, dürfen wir nicht weitergehen, weil wir dann keinen Zugriff auf den Verweis auf den linken Teilbaum vom Knoten mit "marco34" mehr haben.
Aufgaben
-
Eine Operation
void einfuegen(BinTree baum, String wert), welche das übergebene Objekt an die korrekte Stelle in einen binären Suchbaum einfügt, für die der folgende Pseudocode vorliegt, soll implementiert werden.einfuegen (BinTree baum, String wert) falls wert nicht null ist falls baum leer ist setze baum auf neuen Binärbaum mit Inhalt wert sonst setze aktuellesElement auf Element der Wurzel von baum falls wert kleiner als aktuellesElement ist falls linker Teilbaum von baum leer ist setze neuerKnoten auf neuen Binärbaum mit Inhalt wert setze neuerKnoten als linken Teilbaum von baum sonst führe einfuegen auf linken Teilbaum von baum und wert ausfallen sonst falls wert größer als aktuellesElement ist falls rechter Teilbaum von baum leer ist setze neuerKnoten auf neuen Binärbaum mit Inhalt wert setze neuerKnoten als rechten Teilbaum von baum sonst führe einfuegen auf rechten Teilbaum von baum und wert ausfallen sonst Gib aus: "Der Inhalt ist bereits vorhanden."Implementieren Sie die Operation
einfuegenin ProgrammSuchbaumtest, und testen Sie Ihr Ergebnis.
- Bearbeiten Sie die folgenden Aufgaben in Einzelarbeit.
-
Konstruieren Sie den binären Suchbaum, der durch die Eingabe der folgenden Zahlen entsteht.
Konstruieren Sie den binären Suchbaum, der sich durch nacheinander Einfügen der Zahlen 17, 23, 42, 19, 10, 11, 5, 21, 20, 22, 18, 4, 3 ergibt.
Konstruieren Sie den binären Suchbaum, der sich durch nacheinander Einfügen der Zahlen aus Aufgabenteil a) in umgekehrter Reihenfolge ergibt.
Die Preorderausgabe eines binären Suchbaumes ist: 12, 3, 0, 2, 7, 14, 13, 18, 15, 21.
Rekonstruieren Sie mit der Ausgabe den binären Suchbaum.
2, 1, 3, 4
1, 2, 3, 4
3, 4, 1, 2
Erläutern Sie Probleme, die durch eine ungeschickte Reihenfolge beim Einfügen in einen binären Suchbaum entstehen können. Informieren Sie sich hierzu im Internet über entartete binäre Suchbäume.