AVL - Bedingung ....Suchbaum-bedingung

[Jaroslaw]

Wie ist das eigentlich bei AVL - bäumen ....... hier gilt doch auch die allgemeine bedingung der suchbäume, dass alle größeren Schlüssel rechts der Wurzel und alle kleineren Schlüssel links der Wurzel stehen oder ............

jetzt kann es aber sein dass durch rotation diese suchbaumbedingung verletzt wird - was geschieht dann

............2
......1...........9
..............4.......6
....................11
rotation fall 2.1 laut skriptum bal(2)=2 und bal(9)=0,1:
...........9
.....2.........6
...1....4...11

der 6er ist ja kleiner als 9 .........
geht das oder nicht, was ist falsch
thx jaro

[Dimitrij]

bei deinem Beispiel ist die Suchbaumbedingung ja schon VOR der Rotation verletzt, (wenn ich das richtig interpretiere).
also durch die Rotation sollte das nicht verletzt werden.

[Jaroslaw]

also gilt die suchbaumbedingung bei avls net ????

die bedingung :rechts stehen nur größere als root und links nur kleinere =>
9,4,6,11 > 2
1 < 2
das müsste stimmen
nur durch das rotieren wirds eben verletzt
....
@ dimitrij .... von wo im 18. kommst du denn - ich wohn nämlich auch im 18. ??????

[yrucrem]

Die binaere Suchbaum eigenschaft besagt nicht, dass rechts der Wurzel nur groessere Elemente als die Wurzel und links davon nur kleinere sind. Es gilt fuer _jeden_ Knoten, das in seinem linken Unterbaum nur kleinere Elemente sind und im rechten nur groessere.

Bei deinem Beispiel ist die 11 das linke Kind der 6 und das darf nicht sein (auch wenn 11 groeszer ist als die Wurzel).

In einem AVL-Baum muss natuerlich auch die binaere Suchbaumeigenschaft gelten. Und durch das Rotieren wird diese sicher nicht verletzt.

[Jaroslaw]

Alles klar !!!!!! ist genau das was ich wissen wollte .....

thx

gruß jaro

[Dimitrij]

Original geschrieben von Jaroslaw
@ dimitrij .... von wo im 18. kommst du denn - ich wohn nämlich auch im 18. ??????
du wohnst auch in Wladiwostok? ;)
Czartoryskigasse

[Jaroslaw]

@ dimitrji
ach du meine güte - hmmmm..... naja, das sagt ma grad mal nix ..... kommt wahrscheinlich daher , da ich gar no net so lang(eh nur 1,5 jaaaaahre) in wladiwostok wohn ..... sag mal wo das genau is .... kennst doch sicher das starkfriedheim ..... geiler park - pool !!! neben dem boku-heim ???