AuK/Sortierte Folgen SS12
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
=Bäume= ==Termminologie== ==Binäre Bäume== =Binäre Suchbäume= ==Einfügen eines Elementes== ==Einfügen eines Duplikates== ==Finden eines Elementes== ==Finden des Minimums== ==Finden des Maximums== ==Finden des Nachfolgers== ==Sortierte Ausgabe des Baumes== ==Löschen eines Elementes== ===Mit einem Sohn=== ===Mit zwei Söhnen=== =Rot-Schwarz-Bäume= ==Komponenten der Knoten== * Farbe * Schlüssel * Adresse des Eleternknotens * Adresse des linken Kindknotens * Adresse des rechten Kindknotens ==Eigenschaften== # Jeder Konten ist entweder rot oder schwarz # Die Wurzel ist schwarz # Jedes Blatt( null/ nil ) ist schwarz # Die Kind-Knoten eines Roten Knotens sind jeweils schwarz # Alle Pfade die von einem bestimmten Knoten ausgehen und in einem Blatt dieses Teilbaums enden, haben die gleiche Anzahl an schwarzen Knoten ==Rotationen== Durch die Einfüge- und Löschoperationen kann es dazu kommen, das eine oder mehrere Eigenschaften des Rot-Schwarzbaumes verletzt werden. Um die Zeigerstruktur des Baumes zu "reparieren" bedient man sich der Rotation. ===Linksrotation=== ===Rechtsrotation=== ==Einfügen== ===Fall 1=== ===Fall 2=== ===Fall 3=== ===Fall 4=== ===Fall 5=== ==Löschen== ===Fall 1=== ===Fall 2=== ===Fall 3=== ===Fall 4=== ===Fall 5===