Ausgeglichene Bäume

Kurzzusammenfassung

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 Eintre

Fachbereich:	Informatik
Sprache:	Deutsch
Wörter:	1100
Note:	n.v.

Ausgeglichene Bäume

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.
Originaldokument enthält an dieser Stelle eine Grafik!Original document contains a graphic at this position!

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.Originaldokument enthält an dieser Stelle eine Grafik!Original document contains a graphic at this position!
Suche nach G:
mittlere Verzweigung, da G zw. E und R
links, da G nicht vorhanden und Suche von links beginnt.

Originaldokument enthält an dieser Stelle eine Grafik!Original document contains a graphic at this position!
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.Originaldokument enthält an dieser Stelle eine Grafik!Original document contains a graphic at this position!

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.

Originaldokument enthält an dieser Stelle eine Grafik!Original document contains a graphic at this position!

Auspalten von Wurzelknoten:

I als mittlerer Wert bleibt als Wurzel in einem 2-Knoten bestehen.
E & R werden eine Ebene tiefer als zwei seperate 2-Knoten
eingefügt.
Einfügen von D:

Suche von Pos. Erg. rechts von C.
Da C in 4-Knoten aufspaltung von EIR.
Erneute Suche von Pos. zw. CE
Einfügen des neuen 2-Knoten.
Der oben skizzierte Algorithmus wie Suchvorgänge und Einfügungen
in 2-3-4-Bäumen ausgeführt werden können. Da die 4-Knoten auf dem
Weg von oben nach [...]

Du musst angemeldet sein, um das komplette Referate anschauen zu können.

Oder nutze Facebook Share, um das Referat herunterladen zu können.

share

Nach dem Du die Facebook Share Funktion ausgeführt hast aktualisiert sich die Seite automatisch und Du bekommst das komplette Referat zum Download bereit gestellt.