[FRAGE] - AVL - Bedingung ....Suchbaum-bedingung
Results 1 to 7 of 7
  1. #1

    Title
    Principal
    Join Date
    May 2002
    Location
    wien 12
    Posts
    86
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Unhappy 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

  2. #2

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    534
    Thanks
    3
    Thanked 124 Times in 78 Posts

    Re: AVL - Bedingung ....Suchbaum-bedingung

    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.

  3. #3

    Title
    Principal
    Join Date
    May 2002
    Location
    wien 12
    Posts
    86
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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. ??????
    Last edited by Jaroslaw; 20-05-2002 at 01:43.

  4. #4

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    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.

  5. #5

    Title
    Principal
    Join Date
    May 2002
    Location
    wien 12
    Posts
    86
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Alles klar !!!!!! ist genau das was ich wissen wollte .....

    thx

    gruß jaro

  6. #6

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    534
    Thanks
    3
    Thanked 124 Times in 78 Posts
    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

  7. #7

    Title
    Principal
    Join Date
    May 2002
    Location
    wien 12
    Posts
    86
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @ 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 ???

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •