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 istRotation vornehmen
aktueller Knoten > 1Linksrotation
aktueller Knoten <-1Rechtsrotation

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>();