Rebalance AVL
-
Hallo miteinander!
Ich habe 'nen AVL-tree zusammen. Nun fehlt mir aber noch 'ne wichtige Funktion, nämlich das rebalancing.
Hat evtl. gerade jemand einen möglichen Code bereit?int height;
bool is_balanced();
avl_tree* _tree;
int value;
avl_tree_node* _parent, _left, _righthab ich schon alles bereit
Ich wäre sehr dankbar, wenn mir jemand helfen könnte.
Liebe Grüsse,
Max
-
Schau mal im Magazin (einer der Links im Linkhaufen ganz oben rechts der Seite), da müsste ein Artikel samt Code dazu sein.
-
Ah, vielen Dank, habs gefunden
Dazu hätte ich nur noch eine Frage: rotate_left bzw. *_right - wie würde das mit meinen Funktionen und Objekten aussehen?
-
Wie die Rotationen funktionieren, steht auch im Magazin-Artikel (im ersten Teil der Binärbäume-Serie).
-
Dankeschön!
Hab's gefunden. Allerdings funktioniert's bei mir noch nicht ganz (hab ja au unterschiedliche Bezeichnungen).
-
lern erstmal c++
ich hab den eindruck du hast absolut keinen peil was du machst...ausser halt copy&paste...
-
MaxC++ schrieb:
Dankeschön!
Hab's gefunden. Allerdings funktioniert's bei mir noch nicht ganz (hab ja au unterschiedliche Bezeichnungen).Mach die Rotationen an einem Baum von Hand bis du exakt begreifst was geschieht und dann programmierst du das und kannst es nötigenfalls anhand des Testbaumes, den du von Hand gemacht hast debuggen. Es empfiehlt sich da gleich einige solche Testbäume zu machen, um möglichst alle Fälle abdecken zu können.