Bäume

Schlagwörter:
Referat, Hausaufgabe, Bäume
Themengleiche Dokumente anzeigen

Beschreibung / Inhalt
Das Dokument behandelt verschiedene Arten von Suchbäumen und Problemen, die bei der Suche, dem Löschen und Einfügen von Elementen in diesen Bäumen auftreten können. Zunächst wird erklärt, dass die Suche in einem binären Suchbaum durch einen binären Baum dargestellt werden kann. Es werden zwei verschiedene Arten von Suchbäumen beschrieben: balancierte und unbalancierte (degenerierte) Bäume. Balancierte Bäume haben gleichlange Äste und sind für die Suche günstiger als für das Löschen oder Einfügen von Elementen. Unbalancierte Bäume hingegen benötigen bei der Suche viele Vergleiche und sind daher schlecht geeignet.

Es wird auch ein spezieller balancierter Baum namens AVL-Baum beschrieben, bei dem die Tiefendifferenz der Knoten nicht mehr als 1 betragen darf. Diese Methode ist jedoch komplex und erfordert viel Aufwand, um einen balancierten Baum zu erhalten.

Ein weiterer Baum, der beschrieben wird, ist der 2-3-4-Baum, der im Gegensatz zu herkömmlichen binären Suchbäumen mehr Flexibilität durch 3 und 4 Knoten bietet. Hier ist das Suchen einfacher, während das Löschen oder Einfügen von Elementen komplizierter sein kann.

Schließlich wird eine Lösung für das Problem der Löschung von Knoten beschrieben, die viele Nachfolger haben. Die Methode nennt sich „Lazy Deletion“. Dabei wird der Knoten nicht wirklich gelöscht, sondern es wird lediglich ein Löschbit gesetzt.

Die letzte Methode, die beschrieben wird, ist die indirekte Suche (Indirect Search), bei der für oftgesuchte Attribute ein Hilfsbaum oder -index verwendet wird.

Insgesamt behandelt das Dokument verschiedene Ansätze und Probleme beim Suchen, Löschen und Einfügen von Elementen in Suchbäumen, um deren Effizienz zu erhöhen.
Direkt das Referat aufrufen

Auszug aus Referat
12 Bäume Die Folge der Vergleiche ist beim binären Suchen vorbestimmt und kann in einem binären Baum dargestellt werden. 12.1 balancierte Bäume Bei einem balancierten Baum sind die äste gleichlang (symmetrisch). Für die Suche ist diese Baumart günstig, für das Löschen bzw. Einfügen nicht. 12.2 unbalancierter (degenerierter) Baum Bei einem degenerierten Baum hat jeder Knoten nur rechte oder linke Nachfolger. Hier kann die Suche N Vergleiche benötigen (d.h. Suche bei einem deg. Baum ist schlecht). 12.3 AVL - Baum Bei einem AVL-Baum gilt, dass die Tiefendifferenz der Knoten nicht mehr als 1 betragen darf. AVL steht für die Anfangsbuchstaben der Nachnamen der drei russischen Mathematiker. Diese Methode ist kompliziert, da man viel herumranchieren muss, um einen balancierten Baum zu erhalten. 12.4 2-3-4 Baum Dieser Baum bietet gegenüber herkömmlichen binären Suchbäumen mehr Flexibilität (durch 3 und 4 Knoten). Im Gegensatz zum Löschen und Einfügen eines Elementes ist das Suchen eine einfache Sache. 12.5 Lazy Deletion (faule Löschung) Beim Löschen eines Elementes kommt es darauf an, wo sich der Knoten befindet bzw. wieviele Nachfolger er hat. Hat ein Knoten keinen oder nur einen Nachfolger oder einer seiner zwei Nachfolger hat keinen Nachfolger, so ist das Löschen einfach. Das Problem tritt dann auf, wenn die Nachfolger dieses Knotens weitere Nachfolger haben. Hier muss entweder das am weitesten rechts befindliche Element von der linken Verzweigung oder das am weitesten links ...
Direkt das Referat aufrufen

Autor:
Kategorie:
Sonstiges
Anzahl Wörter:
312
Art:
Fachbereichsarbeit
Sprache:
Deutsch
Bewertung dieser Hausaufgabe
Diese Hausaufgabe wurde bisher 2 mal bewertet. Durchschnittlich wurde die Schulnote 1 vergeben.
Zurück