Implémentation d'un séquence impérative sous forme de arbre AVL
créer-sommet(données, sous-abre-gauche, sous-arbre-droite)
gauche(sommet)
droite(sommet)
données(sommets)
hauteur(sommet)
taille(sommet)
entier
hauteur-abre(arbre a)
renvoyer si a == nil
alors 0
sinon hauteur(a)
entier
taille-arbre(arbre a)
renvoyer si arbre = nil
alors 0
sinon taille(a)
arbre
rotation-droite(arbre a)
g = gauche(a)
gauche(a) <- droite(g)
droite(g) <- a
taille(droite(g)) <-
taille-arbre(gauche(droite(g))) +
taille-arbre(droite(droite(g))) + 1
taille(g) <-
taille-arbre(gauche(g)) +
taille-arbre(droite(g)) + 1
renvoyer g
arbre
rotation-gauche(arbre a)
d <- droite(a)
droite(a) <- gauche(d)
gauche(d) <- a
taille(gauche(g)) <-
taille-arbre(gauche(gauche(g))) +
taille-arbre(droite(gauche(g))) + 1
taille(g) <-
taille-arbre(gauche(g)) +
taille-arbre(droite(g)) + 1
renvoyer d
parcourir(arbre a, fonction f)
si a = nil
alors // ne rien faire
sinon
parcourir(gauche(a))
f(donées(a))
parcourir(droite(a))
arbre
insérer-arbre(objet obj, arbre a, entier position)
si a = nil
alors renvoyer créer-sommet(obj, nil, nil)
sinon si position <= taille-arbre(gauche(a))
alors
gauche(a) <- insérer-arbre(obj, gauche(a), position)
si hauteur-abre(gauche(a)) > hauteur-arbre(droite(a)) + 1
alors
si hauteur-arbre(droite(gauche(a))) > hauteur-arbre(gauche(gauche(a)))
alors gauche(a) <- rotation-gauche(gauche(a))
renvoyer rotation-droite(a)
sinon
taille(a) <- taille(a) + 1
renvoyer a
sinon
droite(a) <-
insérer-arbre(obj, droite(a), position - taille-arbre(gauche(a) - 1))
si hauteur-arbre(droite(a)) > hauteur-arbre(gauche(a)) + 1
alors
si hauteur-arbre(gauche(droite(a))) > hauteur-arbre(droite(droite(a)))
alors droite(a) <- rotation-droite(droite(a))
renvoyer rotation-gauche(a)
sinon
taille(a) <- taille(a) + 1
renvoyer a
void
insérer(objet obj, séquence s, entier position)
assert(position <= taille(s))
éléments(s) <- insérer-arbre(obj, éléments(s), position)
taille(s) <- taille(s) + 1