Ausgeglichene Bäume

Beschreibung / Inhalt
Das Dokument beschäftigt sich mit dem Thema der ausgeglichenen Bäume und Algorithmen zur Verwaltung und Suche in diesen Bäumen. Es werden 2-3-4-Bäume und Rot-Schwarz-Bäume vorgestellt, die auf der Grundlage von ausgeglichenen Bäumen aufgebaut sind. Die Autoren beschreiben, wie diese Bäume aufgebaut und manipuliert werden können, um eine effektive Datenstruktur für die Suche und Verwaltung von Datenbeständen zu bieten.

Der Text beschreibt auch die Unterschiede zwischen AVL-Bäumen und 2-3-Bäumen und wie diese als Grundlage für den Aufbau von Rot-Schwarz-Bäumen genutzt werden können. Es wird betont, dass die Effektivität dieser Strukturen im ungünstigsten Fall besonders wichtig ist und dass sie mit vergleichsweise geringem Aufwand erreicht werden kann.

Insgesamt beschäftigt sich das Dokument mit den Grundlagen der Datenspeicherung und -suche und zeigt auf, wie ausgeglichene Bäume und verwandte Datenstrukturen dazu beitragen können, die Effektivität und Effizienz von Datenbanken und anderen Datenbeständen zu erhöhen.
Direkt das Referat aufrufen

Auszug aus Referat
Ausgeglichene Bäume bei binären Bäumen tritt ungünstigster Fall relativ häufig ein. (geordnete Dateien, umgekehrter Reihenfolge, abwecheselnd großer, kleiner Schlüssel, usw.) Ausgleichen verhindert das Eintreten des ungünstigsten Falls. Ausgleichen dient als Grundlage für ausgeglichene Bäume. Top-Down 2-3-4-Bäume mehr Flexibilität gegenüber herkömmlichen binären Suchbäumen durch 3-Knoten und 4-Knoten. 2-Knoten enthalten 1 Schlüssel 3-Knoten enthalten 2 Schlüssel 4-Knoten enthalten 3 Schlüssel Suchen, Einfügen und Aufspaleten. Suche nach G: mittlere Verzweigung, da G zw. E und R links, da G nicht vorhanden und Suche von links beginnt. Einfügen von G: Zuerst erfolglose Suche durchführen, dann G anhängen. drei Möglichkeiten: 2-Knoten: G wird angehängt. aus 2 wird 3. 3-Knoten: G wird ebenfalls angehängt. aus 3 wird 4. 4-Knoten: G wird mit dem ihm am nächsten Elemten zusammengezogen und bildet mit diesem einen 3-Knoten, ein Elemtent wird nach oben geschoben, wobei die hier angeführeten Regel zu berücksichtigen sind. Aus dem vierten Element wird ein 2-Knoten gebildet. Aufspaltung eines 4-Knotens, wenn Vorgänger ebenfalls 4-Knoten: Es besteht die Möglichkeit beim Einfügen eines neuen Knotens, den ganzen Baum (wenn notwendig) nach oben hin aufzuspalten. Nur wenn in der Wurzel ein 4-Knoten steht und dieser aufgespalten werden muß, wird der Baum um eine Stufe tiefer. Auspalten von Wurzelknoten: I als mittlerer Wert bleibt als Wurzel in einem 2-Knoten bestehen. E & R werden eine Ebene ...
Direkt das Referat aufrufen