Les AVL
x1 |
recherche
On commence à partir de la racine:
|Si(val(racine)>val(recherchée))
| | On parcourt le sous-arbre gauche
|Si(val(recherchée)>val(racine))
| | On parcourt le sous-arbre droit
| sinon si(val(racine)=val(recherchée))
| on s'arrete
insertion
_ si racine = nil
_ | insérer à la racine
_ sinon
_ | _ noeud = racine;
_ | _ si val > val(noeud)
_ | _ | _ insérer au fils droit
_ | _ sinon si val < val(noeud)
_ | _ | _ insérer au fils gauche
_ | _ sinon
_ | _ | _ afficher("element existant");
_ | _ fsi
_ fsi
_ on verifie s'il y'a déséquillibre
_ et on effectue les rotations adequates
suppression
On recherche la valeur qu’on souhaite supprimer en utilisant le module de recherche :
Si on ne la trouve pas on s’arrête.
Si la valeur existe plusieurs cas de figures se présentent:
| Si la valeur se trouve dans une feuille on la supprime
| Si la valeur se trouve dans un nœud interne dont les 2 fils sont différents de nil :
| | On le remplace par son suivant inordre
| | On supprime le suivant inordre.
| Si seulement 1 seul fils du nœud est différent de nil :
| | On remplace la valeur du nœud à supprimer par celle du fils qui n’est pas nil
| | On met le champ fils correspondant à nil.
on mis à jours les champs balances.
s'il y a déséquillibre on applique les rotations correspandantes.
equillibrer
_ si balance < -2
_ | _ si fg.balance > 0
_ | _ | double rotation gauche
_ | _ sinon
_ | _ | rotation gauche
_ | _ fsi
_ sinon
_ | _ si fg.balance < 0
_ | _ | double rotation droite
_ | _ sinon
_ | _ | rotation droite
_ | _ fsi
_ fsi
