mittelding
2011-02-12, 16:24:16
Hallo!
Versuche gerade, Rotationen zur Herstellung eines bilanzierten Baumes zu verstehen. Die Rotationen für sich betrachtet sind nicht das Problem (Links/Rechtsrotation und rechtslinks/linksrechts), das Einfügen in einen Baum auch nicht, nur das Zusammenspiel zwischen Einfügen und Rotieren - wobei man ja sicherlich einem bestimmten Pfad entlang muss - erschließt sich mir nicht.
Aber mal langsam.
Zuerst wird also in den Baum eingefügt. Dass passiert ja ganz normal, entsprechende Position suchen und dann dranhängen - auch wenn dadurch der Baum temporär nicht mehr bilanziert ist.
Und jetzt sollen die Rotationen folgen, die nach dem Einfügen die Balance wiederherstellen. Die richtige Rotationsart bestimmt sich ja durch den Balancewert der einzelnen Knoten. Soweit, so gut.
Doch wo fängt man überhaupt mit dem Rotieren an? Beim Parent des gerade eingefügten Elements (und dann bottom up zur Wurzel) oder aber von der Wurzel und dann nach unten Richtung Blätter?
Ich beziehe mich übrigens auf folgende Rotationsregeln:
Linksrotation, falls Balance des aktuellen Knotens > 1, Rechtsrotation falls Balance des aktuellen Knotens < -1, LinksRechts falls Balance <- 1 und Nachfolgerbalance +1, RechtsLinks falls Balance > 1 und Nachfolgerbalance -1.
Wäre cool, wenn jemand den Ablauf in Worten beschreiben könnte. Also praktisch was passieren muss, nachdem das Einfügen stattgefunden hat. Ich habe noch eine Palette an weiteren Unklarheiten, aber wenn sich obiges Problem löst, so lösen sich vermutlich auch die meisten anderen.
Soweit erstmal, Danke!
Edit: Kann es sein, dass die obigen genannten Regeln wirklich nur für AVL-Bäume brauchbar sind und gewöhnliche, allerdings völlig entartete Binärbaume damit nicht so einfach höhenbilanziert werden können? Denn bei letzteren kann ja z.B. eine Balance von 15 auftreten, da wäre ein einmaliges Rotieren und anschließendes Weiterlaufen zum nächsten Knoten nur einen Tropfen auf den heißen Stein.
Versuche gerade, Rotationen zur Herstellung eines bilanzierten Baumes zu verstehen. Die Rotationen für sich betrachtet sind nicht das Problem (Links/Rechtsrotation und rechtslinks/linksrechts), das Einfügen in einen Baum auch nicht, nur das Zusammenspiel zwischen Einfügen und Rotieren - wobei man ja sicherlich einem bestimmten Pfad entlang muss - erschließt sich mir nicht.
Aber mal langsam.
Zuerst wird also in den Baum eingefügt. Dass passiert ja ganz normal, entsprechende Position suchen und dann dranhängen - auch wenn dadurch der Baum temporär nicht mehr bilanziert ist.
Und jetzt sollen die Rotationen folgen, die nach dem Einfügen die Balance wiederherstellen. Die richtige Rotationsart bestimmt sich ja durch den Balancewert der einzelnen Knoten. Soweit, so gut.
Doch wo fängt man überhaupt mit dem Rotieren an? Beim Parent des gerade eingefügten Elements (und dann bottom up zur Wurzel) oder aber von der Wurzel und dann nach unten Richtung Blätter?
Ich beziehe mich übrigens auf folgende Rotationsregeln:
Linksrotation, falls Balance des aktuellen Knotens > 1, Rechtsrotation falls Balance des aktuellen Knotens < -1, LinksRechts falls Balance <- 1 und Nachfolgerbalance +1, RechtsLinks falls Balance > 1 und Nachfolgerbalance -1.
Wäre cool, wenn jemand den Ablauf in Worten beschreiben könnte. Also praktisch was passieren muss, nachdem das Einfügen stattgefunden hat. Ich habe noch eine Palette an weiteren Unklarheiten, aber wenn sich obiges Problem löst, so lösen sich vermutlich auch die meisten anderen.
Soweit erstmal, Danke!
Edit: Kann es sein, dass die obigen genannten Regeln wirklich nur für AVL-Bäume brauchbar sind und gewöhnliche, allerdings völlig entartete Binärbaume damit nicht so einfach höhenbilanziert werden können? Denn bei letzteren kann ja z.B. eine Balance von 15 auftreten, da wäre ein einmaliges Rotieren und anschließendes Weiterlaufen zum nächsten Knoten nur einen Tropfen auf den heißen Stein.