Hab mich in meinem LK jetzt mal für ein Referat mit dem Thema AVL-Bäume gemeldet und im Prinzip auch ne recht verständliche Sache...

Nur weiß ich nicht ganz, wie der Baum die Höhe jedes Knotens überprüft. Ist das als INT in den Attributen gespeichert oder überprüft der das jedes mal neu mit einer Backtracking-function
Also links zu dem Thema werd ich kaum brauchen können, außer es sind mal richtig gute. Wikipedia steht nix sonderlich interessantes drin und auch mit google bin ich nicht so fündig geworden.

Also eine kurze Zusammenfassung dazu wäre echt ziemlich Hilfreich.

MFG.: Baalisto

Die Höhe ist irrelevant; der "Balancewert" (Überhang rechter/linker Teilbaum) wird als Attribut eines Knotens gespeichert. Beim Einfügen werden alle Balancewerte auf dem Einfügepfad aktualisiert (und ggf. rotiert).

Aber is nicht der "Ballancewert" die Differenz der höhen der beiden Teilbäume? Also Speichert jeder Knoten die die Maximale Höhe jeder seiner Teilbäume. Dass er das als ein Attribut zusammenfasst klingt logisch.

Ich denke mal, dass ich für die ganze Sache wohl Backtracking brauche, klingt für mich zumindest so. Hat wohl jemand einen Ansatz wie ich das Ballancing zu beginn überprüfe??
Das aktualisieren müsste dann doch einach immer rekursiv nach den wurzeln greifen und wenn das aktuelle Element dem linken Baum entspricht, dann das ballancing etwas nach links verschieben und wenn es rechts ist, dann etwas nach rechts.
Kann mich natürlich auch völlig auf dem Holzweg befinden und wenn es so ist, dann hoffe ich hier auch einen schnellen Protest.

MfG.: Baalisto

"Am Anfang" gibt es auch keinen Baum. Beim Einfügen eines Wertes mußt du den Einfügepfad aktualisieren - da würde ich aufsteigend vom eingefügten Knoten aus rückwärts laufen (doppelt verkettet).

"Balancewert" ist die Differenz der Höhe der Teilbäume - die ist völlig ausreichend. Du speicherst also wirklich nur die Differenz, nicht die maximale Höhe.