Baum - Versionsgeschichte

Kristin: /* Repräsentativer Aufbau */

2017-01-18T15:16:22Z

‎Repräsentativer Aufbau

Kristin: /* Repräsentierter Aufbau */

2016-11-30T15:52:28Z

‎Repräsentierter Aufbau

Kristin: /* Anwendung zum Sortieren */

2016-07-09T22:23:07Z

‎Anwendung zum Sortieren

Kristin: /* Verwendung */

2016-07-09T22:21:15Z

‎Verwendung

Kristin: /* Objektorientiert */

2016-07-09T22:16:33Z

‎Objektorientiert

Kristin: /* Als Array */

2016-07-09T22:15:45Z

‎Als Array

Kristin: /* Suchbaum */

2016-07-09T22:14:08Z

‎Suchbaum

Kristin: /* Suchbaum */

2016-07-09T22:13:49Z

‎Suchbaum

Kristin: /* Binärbaum */

2016-07-09T21:58:07Z

‎Binärbaum

Hauer am 8. Juli 2016 um 21:06 Uhr

2016-07-08T21:06:09Z

@@ Zeile 4: / Zeile 4: @@
 Ein Baum ist entweder leer oder besteht aus einem einzelnen '''Knoten''' mit '''Unterbäumen'''. Die Unterbäume selbst können wiederum leer oder ein weiterer Knoten mit Unterbäumen sein.
 Wenn ein Knoten keine Unterbäume hat, gilt er als '''Blatt'''.
-Ein Knoten ist immer '''Wurzel''' seines eigenen (Unter-)Baumes.
+Ein Knoten, der weder Blatt noch Wurzel ist, gilt einfach als '''innerer Knoten'''.
 = Eigenschaften und Begriffe =

@@ Zeile 1: / Zeile 1: @@
 Ein '''Baum''' ist eine der am häufigsten verwendeten [[Rekursion|rekursiven]] [[Datenstruktur|Datenstrukturen]]. Bäume gehören zu den [[Dynamische Datenstruktur|dynamischen Datenstrukturen]]. Die in dieser Veranstaltung behandelten Bäume sind hauptsächlich '''binäre Bäume'''. Bäume eignen sich vor allem zum strukturierten Abspeichern von Daten. Die interne Repräsentation hängt dabei von der Implementierung der Datenstruktur ab.
-= Repräsentierter Aufbau =
+= Repräsentativer Aufbau =
 Ein Baum ist entweder leer oder besteht aus einem einzelnen '''Knoten''' mit '''Unterbäumen'''. Die Unterbäume selbst können wiederum leer oder ein weiterer Knoten mit Unterbäumen sein.

@@ Zeile 58: / Zeile 58: @@
 == Anwendung zum Sortieren ==
-Ist eine gegebene Menge an zu sortierenden Zahlen gegeben, können diese mithilfe eines binären Suchbaumes sortiert werden. Zuerst werden die gegebenen Zahlen in einen neuen Binärbaum eingefügt. Anschließend gibt man den In-Order-Durchlauf des Baumes aus. Dieser gibt, Aufgrund der Struktur des Baumes, die Zahlen aufsteigend sortiert aus.
+Ist eine gegebene Menge an zu sortierenden Zahlen gegeben, können diese mithilfe eines '''binären Suchbaumes''' sortiert werden. Zuerst werden die gegebenen Zahlen in einen neuen Binärbaum eingefügt. Anschließend gibt man den '''In-Order-Durchlauf''' des Baumes aus. Dieser gibt, Aufgrund der Struktur des Baumes, die Zahlen aufsteigend sortiert aus.
-Alternativ kann man alle gegebenen Zahlen einem Heap hinzufügen und nacheinander die Wurzel des Heaps entfernen und ausgeben. Dadurch, dass durch die Operationen des Heaps das kleinste bzw. größte Element immer in der Wurzel zu finden ist, gibt man also alle gegebenen Zahlen in auf-, bzw. absteigende Reihenfolge aus. Der Heap ist nach diesem Verfahren jedoch leer, während der Binärbaum für weitere Berechnungen verwendet werden kann.
+Alternativ kann man alle gegebenen Zahlen einem '''Heap''' hinzufügen und nacheinander die Wurzel des Heaps entfernen und ausgeben. Dadurch, dass durch die Operationen des Heaps das kleinste bzw. größte Element immer in der Wurzel zu finden ist, gibt man also alle gegebenen Zahlen in auf-, bzw. absteigende Reihenfolge aus.
 == Beispielcode ==

@@ Zeile 58: / Zeile 58: @@
 == Anwendung zum Sortieren ==
-Ist eine gegebene Menge an zu sortierenden Zahlen gegeben, kann man mithilfe eines binären Suchbaumes die Zahlen sortieren: Man fügt jede gegebene Zahl in einen zunächst leeren Binärbaum ein und gibt anschließend den In-Order Durchlauf des Baumes aus. Dieser gibt, Aufgrund der Struktur des Baumes, die Zahlen aufsteigend sortiert aus.
+Ist eine gegebene Menge an zu sortierenden Zahlen gegeben, können diese mithilfe eines binären Suchbaumes sortiert werden. Zuerst werden die gegebenen Zahlen in einen neuen Binärbaum eingefügt. Anschließend gibt man den In-Order-Durchlauf des Baumes aus. Dieser gibt, Aufgrund der Struktur des Baumes, die Zahlen aufsteigend sortiert aus.
-Alternativ kann man alle gegebenen Zahlen einem Heap hinzufügen und nacheinander die Wurzel des Heaps entfernen und ausgeben. Dadurch, dass durch die Operationen des Heaps das kleinste bzw. größte Element immer in der Wurzel zu finden ist, gibt man also alle gegebenen Zahlen in auf, bzw. absteigende Reihenfolge aus. Der Heap ist nach diesem Verfahren jedoch leer, während der Binärbaum für weitere Berechnungen verwendet werden kann.
+Alternativ kann man alle gegebenen Zahlen einem Heap hinzufügen und nacheinander die Wurzel des Heaps entfernen und ausgeben. Dadurch, dass durch die Operationen des Heaps das kleinste bzw. größte Element immer in der Wurzel zu finden ist, gibt man also alle gegebenen Zahlen in auf-, bzw. absteigende Reihenfolge aus. Der Heap ist nach diesem Verfahren jedoch leer, während der Binärbaum für weitere Berechnungen verwendet werden kann.
-=== Beispielcode ===
+== Beispielcode ==
 <source lang="java">

@@ Zeile 45: / Zeile 45: @@
 Der Index 0 wird dabei ignoriert. Stattdessen ist der '''Index 1''' die Wurzel des Baumes.
-== Objektorientiert ==
+== Objektorientierte Implementierung ==
-Eine '''objektorientierte''' Implementierung repräsentiert einen Baum mithilfe von Knotenobjekten. Dabei kann entweder jeder Knoten selbst alle Operationen eines Baumes umsetzen oder die Verwaltung einer zweiten Baumklasse überlassen.
+Eine '''objektorientierte''' Implementierung repräsentiert einen Baum mithilfe von '''Knotenobjekten'''. Dabei kann entweder jeder Knoten selbst alle Operationen eines Baumes umsetzen oder die Verwaltung einer zweiten Baum[[klasse]] überlassen.
 Ein Knoten besitzt dabei Referenzen auf seine Kinder und ein [[Attribut]], um seinen Wert zu repräsentieren. Hinzufügen, entfernen, ändern, suchen etc. findet dabei meist [[Rekursion | rekursiv]] statt.

@@ Zeile 37: / Zeile 37: @@
 Ein Baum kann sowohl [[Objekt|objektorientiert]] als Datenstruktur aufgebaut werden, als auch durch ein [[Array]] repräsentiert werden.
-== Als Array ==
+== Implementierung als Array ==
-Die Repräsentation des Baumes als '''Array''' ist im Allgemeinen nur dann nützlich, wenn der Baum linksvollständig besetzt werden soll.
+Die Repräsentation des Baumes als '''Array''' ist im Allgemeinen nur dann nützlich, wenn der Baum '''linksvollständig''' besetzt werden soll.
-Dabei werden die einzelnen Zellen des Arrays als Knoten interpretiert und die Eltern-Kind-Beziehung durch die passende Position im Array. Dabei ist für einen Knoten an Position '''i''' der Knoten an Position '''2i''' und '''2i+1''' ein Kind. Entsprechend ist für den Knoten an Position '''i''' der Knoten an Position '''i/2'''<ref>Integerdivision: Division zweier Zahlen ohne Rest</ref> Vater/Mutter.
+Dabei werden die einzelnen Zellen des Arrays als Knoten interpretiert und die Eltern-Kind-Beziehung durch die passende Position im Array repräsentiert. Für einen Knoten an Position '''i''' ist der Knoten an Position '''2i''' und '''2i+1''' ein Kind. Entsprechend ist für den Knoten an Position '''i''' der Knoten an Position '''i/2'''<ref>Integerdivision: Division zweier Zahlen ohne Rest</ref> Vater/Mutter.
 Der Index 0 wird dabei ignoriert. Stattdessen ist der '''Index 1''' die Wurzel des Baumes.

@@ Zeile 31: / Zeile 31: @@
 Diese Ordnung gestattet eine zielgerechte Navigierung durch den Baum und reduziert somit die Suche nach einem gewünschten Wert auf '''logarithmische [[Laufzeit]]''' in Abhängigkeit von der Tiefe des Baumes. In [[Listen]] wird hierfür '''lineare Laufzeit''' benötigt.
-Ein '''In-Order-Durchlauf'' eines binären Suchbaums gibt zudem eine [[Sortieren|sortierte]] Liste aus.
+Ein '''In-Order-Durchlauf''' eines binären Suchbaums gibt zudem eine [[Sortieren|sortierte]] Liste aus.
 = Implementierung =

@@ Zeile 27: / Zeile 27: @@
 == Suchbaum ==
-Ein '''Suchbaum''' ist ein Baum mit einer besonderen Struktur. Die Position der Knoten zueinander wird dabei durch eine Ordnung bestimmt: Kleinere Werte werden zumeist links von einem Knoten einsortiert, während größere Werte rechts von einem Knoten landen. Dadurch kann man bei der Suche danach, ob ein gewünschter Wert bereits im Baum einsortiert wurde, zielgerecht durch den Baum navigieren und so die Suche von linearer Zeit bei Listen auf logarithmische Laufzeit (in Abhängigkeit zur Tiefe des Baumes) reduzieren. Ein In-Order Durchlauf eines binären Suchbaums gibt zudem eine [[Sortieren|sortierte]] [[Liste]] aus.
+Ein '''Suchbaum''' ist ein Baum mit einer besonderen Struktur. Die Position der Knoten zueinander wird dabei durch eine '''Ordnung''' bestimmt: Kleinere Werte werden meistens links und größere Werte rechts von einem Knoten einsortiert.
 = Implementierung =

@@ Zeile 13: / Zeile 13: @@
 == Binärbaum ==
-Ein '''Binärbaum''' ist ein Baum, dessen Knoten genau '''zwei Kinder''' haben. Die beiden Kinder eines Baumes werden dann meistens als '''linkes''' und '''rechtes''' Kind bezeichnet.
+Ein '''Binärbaum''' ist ein Baum, dessen Knoten genau '''zwei Kinder''' haben. Die beiden Kinder werden meistens als '''linkes''' und '''rechtes''' Kind bezeichnet.
-Die Verwaltung von Daten in Binärbäumen wird im speziellen in [[Heap | Heaps]] und in '''Binären Suchbäumen''' verwendet. Diese erlauben für bestimmte Verwendungszwecke sehr effiziente [[Algorithmus|Algorithmen]].
+'''[[Heap | Heaps]]''' und '''Binäre Suchbäume''' sind spezielle Binärbäume. Diese Strukturen ermöglichen für bestimmte Verwendungszwecke sehr effiziente [[Algorithmus|Algorithmen]] .
 == Ebene ==