| home | suche | kontakt/johner | institut studierende | tech-docs | mindmailer |
 |
Binäre höhenbilanzierte Suchbäume
Ist ein binärer Suchbaum nicht höhenbilanziert, kann er durch Links- oder Rechtsrotation umstrukturiert werden.
| Balance ist | Rotation vornehmen |
|---|---|
| aktueller Knoten > 1 | Linksrotation |
| aktueller Knoten <-1 | Rechtsrotation |
aktueller Knoten = 2 vom Nachfolgerknoten = -1 | Rechtslinksrotation |
aktueller Knoten = -2 vom Nachfolgerknoten = +1 | Linksrechtsrotation |
Das folgende UML-Diagramm und die Instanzsicht zeigen, wie ein binärer Suchbaum implementiert werden kann. Diese Diagramme zeigen nur eine Möglichkeit der Implementierung, es gibt noch weitere Ansätze.
Um ein Element aus einem Binärbaum zu löschen müssen, abhängig von der Anzahl der Nachfolger, folgende Regeln beachtet werden.
Das zu löschende Element ist/hat
- ein Blatt --> einfach aus dem Baum herausnehemen (Knoten auf null setzen)
- einen Nachfolger --> der Nachfolger ersetzt das zu löschende Element
- zwei Nachfolger --> das zu löschende Element durch das kleinste/größte Element des rechten/linken Teilbaums ersetzen
Vielwegbäume
Bei Vielwegbäumen ist der Grad des Baumes > 2, d.h. es können mehr als 2 Kindelemente vorkommen. Folgendes UML-Diagramm und Instanzsicht sollen zeigen, wie so ein Baum implementiert werden kann. Dabei kann die Liste, die hier als Array dargestellt ist, einfach als Java Collection umgesetzt werden.
Collection<VielwegNode> subNodes = new Vector<VielwegNode>();
