PC 6
Arbres binaires de recherche
Comparaison des algorithmes de recherche
* : en moyenne.
Les arbres binaires de recherche fournissent une structure de données dynamique de relativement basse complexité.
Arbres de recherche
Arbres binaires satisfaisant la propriété suivante: Si v est l'étiquette d'un noeud, on a w<v pour tout noeud du sous-arbre gauche et v<w pour tout noeud du sous-arbre droit. arbrerech58mm49mm700
Propriété caractéristique: la suite des étiquettes des noeuds dans l'ordre interne est croissante.
Opérations de base: recherche,insertion, suppression.
La recherche est une généralisation de la recherche dichotomique.
Représentation
On représente les arbres avec des pointeurs.
Déclaration de type en Pascal:
type
Arbre = ^Noeud;
Noeud = record
contenu: Element;
filsg: Arbre;
filsd: Arbre;
end;
Ou en C:
typedef struct Noeud{
Element contenu;
struct Noeud *filsG;
struct Noeud *filsD;
} *Arbre;
Recherche d'un élément
La recherche est une généralisation de la recherche dichotomique. En Pascal:
function Recherche (v: Element; a: Arbre):Arbre;
var r: Arbre;
begin
if a = nil then r := nil
else if v = a^.contenu then
r := a
else if v < a^.contenu then
r := Recherche (v, a^.filsg)
else
r := Recherche (v, a^.filsd);
Recherche := r;
end;
En C:
Arbre Recherche (Element v, Arbre a)
{
if (a == NULL || v == a -> contenu)
return a;
else
if (v < a -> contenu)
return Recherche (v, a -> filsG);
else
return Recherche (v, a -> filsD);
}
Insertion
procedure Ajouter (v : Element; var a : Arbre);
begin if a = nil then
a := NouvelArbre(v, nil, nil)
else if v <= a^.contenu then
Ajouter (v, a^.filsG)
else Ajouter (v, a^.filsD);
end;
ou en C:
void Ajouter(Element v, Arbre *ap)
{
Arbre a=*ap;
if (a==NULL)
a = NouvlArbre(v,NULL,NULL);
else if (v <= a -> contenu)
Ajouter (v, &a -> filsG);
else
Ajouter (v, &a -> filsD);
*ap = a;
}
Suppression
La suppression d'un élément nécessite une précaution : il ne faut pas créer un ``trou''. On choisit de remplacer le noeud à supprimer par le plus grand des descendants de son fils gauche (ou par son fils droit s'il n'a pas de fils gauche).
La première fonction supprime le plus grand élément d'un arbre de recherche et rend sa valeur:
function max(var a: Arbre): Element; begin if a^.filsd = nil then begin max := a^.contenu; a := a^.filsg end else max := max(a^.filsd) end;
procedure Supprimer(v: Element, var a: Arbre); begin if a <> nil then if v < a^.contenu then Supprimer(v, a^.filsg) else if v > a^.contenu then Supprimer(v, a^.filsd) else if (a^. filsg = nil) then a := a^.filsd else a^.contenu := max(a^.filsg) end;
Complexité Toutes les opérations sur les arbres binaires de recherche se réalisent le long d'un chemin de l'arbre.
Leur complexité est donc O(h) où h est la hauteur de l'arbre.
La complexité moyenne est la hauteur moyenne h(n) d'un noeud. Pour montrer que , on procède en deux étapes.
Relation de récurrence
Supposons que l'arbre est obtenu par n insertions successives de n éléments arrivant dans un ordre aléatoire. On a en raisonnant sur le premier arrivé i
avec, en raisonnant sur chaque noeud
d'où
Résolution On va montrer que
où est le n-ième nombre harmonique. Comme , la conclusion suit.
On écrit
Et on soustrait . On obtient
ou encore
Comme l'expression ci-dessus satisfait cette relation de récurrence et que h(1)=1, le résultat suit.
Autres arbres
On peut obtenir une complexité logarithmique non pas en moyenne mais dans le pire des cas en utilisant des structures plus compliquées comme :
Arbres AVL Un arbre AVL ou arbre équilibré est un arbre binaire tel que pour tout noeud n, les hauteurs des sous-arbres gauche et droit en n diffèrent d'au plus 1.
On peut vérifier que la hauteur h d'un arbre AVL ayant N noeuds vérifie
où est la suite de Fibonacci définie par et . Ainsi
Insertion dans un arbre AVL L'insertion dans un arbre AVL se fait en suivant le même principe que dans les arbres binaires de recherche mais en ajoutant une fonction de réequilibrage. Celle-ci est définie en utilisant des opérations de rotation sur les arbres binaires.
La rotation droite est définie par
La rotation gauche est l'opération inverse. Toutes deux s'effectuent en temps constant.