Baum: Unterschied zwischen den Versionen
Hauer (Diskussion | Beiträge) |
|||
| Zeile 1: | Zeile 1: | ||
| − | Ein Baum ist eine der am häufigsten verwendeten | + | Ein '''Baum''' ist eine der am häufigsten verwendeten rekursiven [[Datenstruktur|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äsentierter Aufbau = | ||
| − | Ein Baum ist entweder leer oder besteht aus einem einzelnen Knoten mit Unterbäumen. Die Unterbäume | + | 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 ist immer '''Wurzel''' seines eigenen (Unter-)Baumes. |
= Eigenschaften und Begriffe = | = Eigenschaften und Begriffe = | ||
| Zeile 15: | Zeile 15: | ||
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 eines Baumes werden dann 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 Algorithmen. | + | 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]]. |
== Ebene == | == Ebene == | ||
| − | Zwei Knoten, die den gleichen Abstand zur Wurzel des Baumes haben, befinden sich | + | Zwei Knoten, die den gleichen Abstand zur Wurzel des Baumes haben, befinden sich auf der gleichen '''Ebene'''. |
Eine Ebene wird als '''vollständig''' bezeichnet, wenn alle möglichen Knoten in einer Ebene auch existieren. | Eine Ebene wird als '''vollständig''' bezeichnet, wenn alle möglichen Knoten in einer Ebene auch existieren. | ||
| − | Eine Ebene ist '''linksvollständig''', wenn | + | Eine Ebene ist '''linksvollständig''', wenn von links an eine Ebene lückenlos gefüllt ist, aber nicht unbedingt vollständig ist. |
== Suchbaum == | == Suchbaum == | ||
| − | Ein Suchbaum ist ein Baum mit einer besonderen Struktur. Die | + | 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 sortierte Liste aus. |
= Implementierung = | = Implementierung = | ||
| − | Ein Baum kann sowohl objektorientiert als Datenstruktur aufgebaut werden, als auch durch ein [[Array]] repräsentiert werden. | + | Ein Baum kann sowohl [[Objekt|objektorientiert]] als Datenstruktur aufgebaut werden, als auch durch ein [[Array]] repräsentiert werden. |
== Als Array == | == Als Array == | ||
| − | Die Repräsentation des Baumes als Array ist im | + | 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</ref> Vater/Mutter. | ||
| + | |||
| + | Der Index 0 wird dabei ignoriert. Stattdessen ist der '''Index 1''' die Wurzel des Baumes. | ||
== Objektorientiert == | == Objektorientiert == | ||
| − | Eine objektorientierte Implementierung repräsentiert einen Baum mithilfe von Knotenobjekten. Dabei kann entweder jeder Knoten selbst alle Operationen eines Baumes umsetzen oder die Verwaltung | + | 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. |
| − | Ein Knoten besitzt dabei Referenzen auf seine Kinder und ein Attribut um seinen Wert zu repräsentieren. | + | 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. |
= Verwendung = | = Verwendung = | ||
| − | [[Heap | Heaps]] werden meistens zur Implementierung von Prioritätswarteschlangen verwendet, oder als Trägerstruktur für | + | [[Heap | '''Heaps''']] werden meistens zur Implementierung von Prioritätswarteschlangen verwendet, oder als Trägerstruktur für [[Sortieren|Sortieralgorithmen]]. |
| − | '''Binäre Suchbäume''' werden meistens zur Implementierung von Mengen verwendet, da das | + | '''Binäre Suchbäume''' werden meistens zur Implementierung von Mengen verwendet, da das Hinzufügen und Suchen hier relativ schnell möglich ist. Die verschiedenen Arten der '''Baumdurchläufe''' haben in dieser Datenstruktur zudem Eigenschaften, die verschiedenen Problemstellungen zu relativ effizienten Algorithmen führen. |
= Fußnoten = | = Fußnoten = | ||
<references /> | <references /> | ||
Version vom 23. März 2016, 23:02 Uhr
Ein Baum ist eine der am häufigsten verwendeten rekursiven 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.
Inhaltsverzeichnis
Repräsentierter 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.
Wenn ein Knoten keine Unterbäume hat, gilt er als Blatt.
Ein Knoten ist immer Wurzel seines eigenen (Unter-)Baumes.
Eigenschaften und Begriffe
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.
Die Verwaltung von Daten in Binärbäumen wird im speziellen in Heaps und in Binären Suchbäumen verwendet. Diese erlauben für bestimmte Verwendungszwecke sehr effiziente Algorithmen.
Ebene
Zwei Knoten, die den gleichen Abstand zur Wurzel des Baumes haben, befinden sich auf der gleichen Ebene.
Eine Ebene wird als vollständig bezeichnet, wenn alle möglichen Knoten in einer Ebene auch existieren.
Eine Ebene ist linksvollständig, wenn von links an eine Ebene lückenlos gefüllt ist, aber nicht unbedingt vollständig ist.
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 sortierte Liste aus.
Implementierung
Ein Baum kann sowohl objektorientiert als Datenstruktur aufgebaut werden, als auch durch ein Array repräsentiert werden.
Als Array
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[1] Vater/Mutter.
Der Index 0 wird dabei ignoriert. Stattdessen ist der Index 1 die Wurzel des Baumes.
Objektorientiert
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. 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 rekursiv statt.
Verwendung
Heaps werden meistens zur Implementierung von Prioritätswarteschlangen verwendet, oder als Trägerstruktur für Sortieralgorithmen.
Binäre Suchbäume werden meistens zur Implementierung von Mengen verwendet, da das Hinzufügen und Suchen hier relativ schnell möglich ist. Die verschiedenen Arten der Baumdurchläufe haben in dieser Datenstruktur zudem Eigenschaften, die verschiedenen Problemstellungen zu relativ effizienten Algorithmen führen.
Fußnoten
- ↑ Integerdivision
