IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

AVL : calcul du déséquilibre après rotation


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Inscrit en
    Novembre 2003
    Messages
    245
    Détails du profil
    Informations forums :
    Inscription : Novembre 2003
    Messages : 245
    Points : 106
    Points
    106
    Par défaut AVL : calcul du déséquilibre après rotation
    Bonjour,

    Pour l'école j'ai fait l'implémentation des AVL, en Java. Chaque noeud contient une donnée "desequilibre" (= hauteur (filsGauche) - hauteur (filsDroit)).

    Après une rotation droite, le déséquilibre de 2 noeuds (sommet et filsGauche qui deviennent respectivement filsDroit et sommet) est modifié. Je sais qu'il est possible de trouver grâce à une formule es nouvelles valeurs des déséquilibres. J'en ai trouvé une sur un site internet :



    Celle-ci ne fonctionne pas chez moi, notamment car leur déséquilibre est égal à "filsDroit - filsGauche". J'ai essayé de la comprendre, de l'inverser mais le résultat reste faux.

    Cela fait plusieurs heures que je manipule mes données dans tous les sens pour retrouver une formule cohérente avec mon implémentation... mais impossible d'y arriver. Si quelqu'un pouvait m'indiquer cette formule (dans un premier temps pour une rotation droite), et mieux, me l'expliquer... je lui en serai très reconnaissant.

    Merci d'avance.

  2. #2
    Membre régulier
    Inscrit en
    Novembre 2003
    Messages
    245
    Détails du profil
    Informations forums :
    Inscription : Novembre 2003
    Messages : 245
    Points : 106
    Points
    106
    Par défaut
    Sans forcément passer par une formule, si quelqu'un connait la méthode efficace (pas de calcul de hauteur) pour recalculer les déséquilibres après une rotation, en analysant toutes les situations... je suis aussi preneur, car je n'y arrive vraiment pas.

    Merci.

  3. #3
    Membre régulier
    Inscrit en
    Novembre 2003
    Messages
    245
    Détails du profil
    Informations forums :
    Inscription : Novembre 2003
    Messages : 245
    Points : 106
    Points
    106
    Par défaut
    Je pense avoir trouvé...

    ROTATION GAUCHE :

    (A) Sommet ==RG==> (A') FilsGauche
    (B) FilsDroit ==RG==> (B') Sommet

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    A' = A + 1 - min(0, B)
    B' = B + 1 + max(0, A')
    ROTATION DROITE :

    (A) Sommet ==RD==> (A') FilsDroit
    (B) FilsGauche ==RD==> (B') Sommet

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    A' = A - 1 - max(0, B)
    B' = B - 1 + min(0, A')
    Je teste, ça a l'air de marcher...

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [2D SFML] deplacement apres rotation
    Par Sniper-Omega dans le forum SFML
    Réponses: 7
    Dernier message: 11/05/2009, 18h51
  2. limitation calcul à 2 chiffres après virgule
    Par jgrazzi dans le forum Requêtes et SQL.
    Réponses: 2
    Dernier message: 18/09/2008, 10h01
  3. calcul de prix apres addition de TVA
    Par ismailsrt4400 dans le forum Excel
    Réponses: 4
    Dernier message: 11/03/2008, 19h07
  4. Réponses: 0
    Dernier message: 11/03/2008, 16h02
  5. Dimension d'une image après rotation
    Par Tyler Durden dans le forum AWT/Swing
    Réponses: 1
    Dernier message: 03/02/2007, 20h08

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo