AVL - Bedingung ....Suchbaum-bedingung

  • 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

  • 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. ??????

  • 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.

    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  • @ 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 ???