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