Chapitre V : Les arbres
4. Arbres binaires de
recherche
Soit A un arbre binaire (nœuds
étiquetés par des éléments)
A est un arbre binaire ordonnée (de
recherche) :
ssi en tout nœud p de A Elt(G(p))
<= Elt(p) < Elt(D(p))
ssi
A = Arbre_vide ou
A = (r, G, D) avec G, D arbres
binaires de recherche et .
Elt(G) <= Elt (r) < Elt(D)
Chapitre V : Les arbres
fonction appartient(a:Arbre,
val:typeElement): booléen
début
if (a=nil) alors retourner ( faux)
Sinon si(a^.info = val)
alors retourner (vrai)
Sinon si (val < a^.info)
Alors retourner (appartient(a^.fg, val))
Sinon retourner(appartient(a^.fd, val))
Finsi
fin
Chapitre V : Les arbres
Version itérative
fonction appartient(a:Arbre, val:typeElement): booléen
var trouve:booléen
début
trouve←false;
Tant que (a<>nil et non(trouve)) faire
trouve ← (a^.info = val);
si (val < a^.info) alors
a ← a^.fg
Sinon a ← a^.fd;
Finsi
Fintant que
Retourner ( trouve)
Fin
Chapitre V : Les arbres
Exemple
Successeur de 7: 8
=minimum du Fils
droit s’il existe
7
Successeur de 8: 10
12
Successeur de 5: 7
4 Prédécesseur de 7: 5=
maximum du fils
7 gauche s’il existe
10 20
3 5 v Prédécesseur de 5: 4
8 17
Chapitre V : Les arbres
Successeur et prédécesseur:
Si B est non vide, son minimum est le successeur de k,
sinon le successeur de k est le premier ancêtre de k dont le
fils gauche est aussi ancêtre de k.
Chapitre V : Les arbres
b. Insertion d’un élément Version récursive
L’élément à ajouter est inséré là où on
l’aurait trouvé s’il avait été présent dans procedure ajout (var a:Arbre, val:integer);
l’arbre. L’algorithme d’insertion, Debut
recherche donc l’élément dans l’arbre
et, quand il aboutit à la conclusion que si (a =nil) alors allouer(a);
l’élément n’appartient pas à l’arbre a^.info ← val;
(l’algorithme aboutit sur NIL), il insère
l’élément comme fils du dernier nœud a^.fg ← nil;a^.fd ← nil;
visité.
Sinon si (val <= a^.info) alors
ajout (a^.fg, val)
sinon ajout (a^.fd, val);
Finsi
Fin
Chapitre V : Les arbres
Version itérative Fin tant que
procedure ajout (var a:ARbre, val:entier) allouer(p); p^.info ← val; p^.fg ← nil;
var p , pere:Arbre; p^.fd ← nil;
Début si (pere =nil) alors a ← p
p ← a; pere ← nil;
Sinon si (val <=pere^.info) alors
Tant que (p<>nil) faire
pere^.fg ← p
pere ← p;
si (val <= p^.info)
Sinon pere^.fd ← p;
alors p ← p^.fg Finsi
sinon p ← p^.fd; Fin;
Finsi
Chapitre V : Les arbres
c. Suppression d’un élément
La suppression commence par la recherche de l'élément. Une fois trouvé
ce dernier :
si c'est une feuille, on la vire sans problèmes
si c'est un sommet qui n'a qu'un fils, on le remplace par ce fils
si c'est un sommet qui a deux fils, on a deux solutions :
le remplacer par le sommet de plus grande valeur dans le sous arbre
gauche .
le remplacer par le sommet de plus petite valeur dans le sous arbre droit.
Pour simplifier le travail nous allons commencer par écrire deux fonctions
: PlusPetitSousArbreDroit et PlusGrandSousArbreGrand.
Chapitre V : Les arbres
Fonction Fonction
PlusPetitSousArbreDroit(B : PlusGrandSousArbreGauche(B :
Arbre) : arbre Arbre) :arbre
Début Début
Si B^.FilsG ≠ nil Alors Si B^.FilsD ≠ nil Alors
retourner ( Retourner
PlusPetitSousArbreDroit(B^.Fils (PlusGrandSousArbreGauche(B
G)) ^.FilsD)
Sinon Sinon
Retourner ( B ) retourner( B )
Fin Si Fin Si
Fin
Chapitre V : Les arbres
Procedure Supprimer(x : Entier ; var B : Sinon Si B^.FilsG ≠ nil ET B^.FilsD ≠ nil
Arbre) Alors P ←PlusPetitSousArbreDroit(B^.FilsD)
Var // Si le sommet admet deux fils
P, Q : Arbre // On cherche le plus petit du sous arbre droit
Debut // ou aussi on peut chercher le plus grand du sous
Si B = nil Alors arbre gauche
Ecrire ("Arbre vide ", x, " est introuvable") // P ← PlusGrandSousArbreGauche(B^.FilsG)
Sinon Q←P
Si B^.val = x Alors Q^.FilsG ← B^.FilsG
Si B^.FilsG = nil ET B^.FilsD = nil Alors Q^.FilsD ← B^.FilsD
// Si c’est une feuille Supprimer(P^.val, P) // appel récursif
Liberer(B) B←Q
Sinon Si B^.FilsG ≠ nil ET B^.FilsD = nil Fin Si
Alors B ← B^.FilsG Sinon Si B^.val > x Alors
// Si le sommet admet un sous arbre gauche Supprimer(x, B^.FilsG)
Sinon Si B^.FilsG = nil ET B^.FilsD ≠ nil Sinon
Alors B ←B^.FilsD Supprimer(x, B^.FilsD)
// Si le sommet admet un sous arbre gauche Fin Si
Fin Si
Fin
Chapitre V : Les arbres
d. Complexité
Si h est la hauteur de l’arbre, on peut aisément montrer que
tous les algorithmes précédents ont une complexité en O(h).
Malheureusement, un arbre binaire quelconque à n noeuds a
une hauteur comprise, en ordre de grandeur, entre log2 n et
n. Pour éviter les cas les plus pathologiques, on s’intéresse à
des arbres de recherches équilibrés..
