Arbre Binaire de Recherche

Définition d'un Arbre Binaire de Recherche

Un Arbre Binaire de Recherche est un Arbre Binaire qui respecte une organisation ordonnéee particulière.

Les Clés des Noeuds doivent toutes pouvoir être comparées entre elles (c'est à dire disposer d'un opérateur < ou > ...).

La définition de l'Arbre Binaire de recherche impose que :

1. Toutes les clés du sous-arbre gauche sont plus petites* que la clé de la racine de l'Arbre étudié
2. Toutes les clés du sous-arbre de droite sont plus grandes* que la clé de la racine de l'Arbre étudié

La présence du * indique que l'égalité peut être traitée comme vous le voulez : à vous de choisir si vous voulez insérer un tel noeud à droite ou à gauche.

Dans un premier temps, nous nous limiterons au cas des arbres pour lequel les clés sont toutes différentes.

Exemples

Un Arbre Binaire de Recherche Complet :

Les mêmes noeuds avec les mêmes clés dans une configuration moins optimale pour la recherche :

L'intérêt ?

Comme pour la liste-tableau trié qui permet une recherche dichotomique à coût logarithmique plutôt que linéaire,
l'ABR permet une recherche à coût logarithmique (sur un Arbre proche d'un Arbre Complet) plutôt que linéaire.

Un algorithme d'insertion dans un arbre binaire de recherche (non vide)

VARIABLE
T : arbre
x : noeud
y : noeud
DEBUT
ARBRE-INSERTION(T,y) :
  x ← T.racine
  tant que T ≠ NIL :
    x ← T.racine
    si y.clé < x.clé :
      T ← x.gauche
    sinon :
      T ← x.droit
    fin si
  fin tant que
  si y.clé < x.clé :
    insérer y à gauche de x
  sinon :
    insérer y à droite de x
  fin si
FIN

Les fonctions liées aux Noeuds :

1. nvND(cle:Cle, data:Data) -> Noeud : on crée un nouveau noeud et son élément attaché. Ce n'est pas une fonction d'interface de l'arbre mais on a besoin au moins de pouvoir créer un Noeud.
2. cle(noeud:Noeud) -> Cle : renvoie la clé ou l'étiquette du noeud.
3. data(noeud:Noeud) -> Data : renvoie les données associées au noeud.

Les fonctions liées à l'Arbre Binaire de Recherche lui-même :

1. nvAV() -> Arbre : on le note ainsi pour dire nouvelArbreVide : on crée un nouvel ARBRE BINAIRE vide.
2. nvABR(r:Noeud, g:Arbre, d:Arbre) -> Arbre : on crée un nouvel ARBRE BINAIRE de RECHERCHE dont la racine est r et dont les sous-arbres sont g et d fournis.
3. estArbreVide(arbre:Arbre) -> bool : True si l'arbre est un arbre vide.
4. racine(arbre:Arbre) -> Noeud : renvoie le noeud jouant le rôle de la racine pour cet arbre.
5. gauche(arbre:Arbre) -> Arbre : renvoie le sous-arbre gauche de arbre. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine.
6. droite(arbre:Arbre) -> Arbre : renvoie le sous-arbre droit de arbre.

Les deux nouvelles fonctions liées à l'insertion :

7. inserer_gauche(arbre:Arbre, g:Arbre) -> None : on remplace le sous-arbre gauche de arbre par l'arbre g.
8. inserer_droite(arbre:Arbre, d:Arbre) -> None : on remplace le sous-arbre droite de arbre par l'arbre d.

Algorithme d'insertion d'un noeud dans un Arbre Binaire de Recherche NON VIDE

ENTREE 1 : l'ABR arbre (non vide) avec lequel on veut travailler

ENTREE 2 : le noeud nd (possèdant une clé c et des données annexes éventuelles) qu'on veut rajouter à notre arbre.

SORTIE : Vide, on modifie ici l'arbre sur place

inserer_noeud_dans_ABR(arbre:ABR, nd:Noeud) -> Vide

étape 1 : on crée arbre_parent, variable qui va contenur la référence de l'arbre où insérer le Noeud nd

arbre_parent ← Vide




étape 2 : on explore l'arbre jusqu'à trouver la bonne position

TANT QUE NON estArbreVide(arbre)

arbre_parent ← arbre

SI cle(nd) < cle(racine(arbre))

arbre ← gauche(arbre)

SINON

arbre ← droite(arbre)

Fin SI

Fin Tant Que




étape 3 : on insère l'arbre dont nd est la racine au bon endroit

SI cle(nd) < cle(racine(arbre_parent))

inserer_gauche(arbre_parent, nvABR(nd, nvAV(), nvAV()) )

SINON

inserer_droite(arbre_parent, nvABR(nd, nvAV(), nvAV()) )

Fin SI

Renvoyer VIDE

Coût de la recherche dans un Arbre Binaire de Recherche

Le coût est alors fonction de la hauteur h l'Arbre Binaire : θ(h). Du coup,

1. Si l'AB est complet, on obtient alors un coût logarithmique sur la taille de l'Arbre : θ(log2(n))
2. Si l'AB est filiforme, on retrouve juste un coût linéaire par rapport à la taille : θ(n)
3. Si l'AB est quelconque, on est entre les deux.

Un algorithme de recherche d'une clé dans un arbre binaire de recherche (ABR)

Nous allons maintenant étudier un algorithme permettant de rechercher une clé de valeur k dans un arbre binaire de recherche.
Si k est bien présent dans l'arbre binaire de recherche, l'algorithme renvoie vrai, dans le cas contraire, il renvoie faux.

VARIABLE
T : arbre
x : noeud
k : entier
DEBUT
ARBRE-RECHERCHE(T,k) :
  si T == NIL :
    renvoyer faux
  fin si
  x ← T.racine
  si k == x.clé :
    renvoyer vrai
  fin si
  si k < x.clé :
    renvoyer ARBRE-RECHERCHE(x.gauche,k)
  sinon :
    renvoyer ARBRE-RECHERCHE(x.droit,k)
  fin si
FIN

Cet algorithme de recherche d'une clé dans un arbre binaire de recherche ressemble beaucoup à la recherche dichotomique vue en première dans le cas où l'arbre binaire de recherche traité est équilibré.
La complexité en temps dans le pire des cas de l'algorithme de recherche d'une clé dans un arbre binaire de recherche équilibré est donc O(log₂(n)).
Dans le cas où l'arbre est filiforme, la complexité est O(n).
Rappelons qu'un algorithme en O(log₂(n)) est plus "efficace" qu'un algorithme en O(n).

À noter qu'il existe une version dite "itérative" (qui n'est pas récursive) de cet algorithme de recherche :

VARIABLE
T : arbre
x : noeud
k : entier
DEBUT
ARBRE-RECHERCHE_ITE(T,k) :
  x ← T.racine
  tant que T ≠ NIL et k ≠ x.clé :
    x ← T.racine
    si k < x.clé :
      T ← x.gauche
    sinon :
      T ← x.droit
    fin si
  fin tant que
  si k == x.clé :
    renvoyer vrai
  sinon :
    renvoyer faux
  fin si
FIN

Pour Information : ABR complet et ABR équilibré

Vous savez maintenant qu'un ABR est complet si le dernier étage est composé uniquement des feuilles de l'arbre.

Nous venons de voir que dans ce cas, le coût de l'insertion et de la recherche est θ(log2(n)).

Or, ce cas est assez rare cas il faut déjà au moins que le nombre de noeuds soit égal à une puissance de 2 moins 1 : n = 2^x - 1.

La notion d'arbre équilibré possède plusieurs variantes.
L'important est de comprendre qu'il s'agit d'un arbre pour lequel les recherches peuvent toutes se ramener à peu près au cas de l'arbre complet.
C'est le "à peu près" qui fera la différence entre les définitions.

En 1962 que deux Russes, Adel'son-Vel'skii et Landis, introduisent des critères définissant un équilibre.
Les arbres vérifiant ces critères sont connus sous le nom d'arbres AVL. Avec ce critère AVL, pour tout nœud de l'arbre, la différence entre les hauteurs de ses deux fils ne peut excéder 1..

Cet Arbre n'est pas un Arbre Binaire équilibré (je considère une hauteur de 0 pour une racine seule)

Par contre, cet Arbre est un Arbre Binaire équilibré :

Pour un Arbre Binaire équilibré, on considère que le coût d'une recherche ou d'une insertion est au pire logarithmique par rapport à la taille de l'arbre (θ(log2(n))).

Les fonctions liées aux Noeuds :

1. nvND(cle:Cle, data:Data) -> Noeud : on crée un nouveau noeud et son élément attaché. Ce n'est pas une fonction d'interface de l'arbre mais on a besoin au moins de pouvoir créer un Noeud.
2. cle(noeud:Noeud) -> Cle : renvoie la clé ou l'étiquette du noeud.
3. data(noeud:Noeud) -> Data : renvoie les données associées au noeud.

Les fonctions liées à l'ABR lui-même :

1. nvAV() -> Arbre : on le note ainsi pour dire nouvelArbreVide : on crée un nouvel ARBRE BINAIRE vide.
2. nvAB(r:Noeud, g:Arbre, d:Arbre) -> Arbre : on crée un nouvel ARBRE BINAIRE dont la racine est r et dont les sous-arbres sont g et d fournis.
3. estArbreVide(arbre:Arbre) -> bool : True si l'arbre est un arbre vide.
4. racine(arbre:Arbre) -> Noeud : renvoie le noeud jouant le rôle de la racine pour cet arbre.
5. gauche(arbre:Arbre) -> Arbre : renvoie le sous-arbre gauche de arbre. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine.
6. droite(arbre:Arbre) -> Arbre : renvoie le sous-arbre droit de arbre.
7. inserer_gauche(arbre:Arbre, g:Arbre) -> None : on remplace le sous-arbre gauche de arbre par l'arbre g.
8. inserer_droite(arbre:Arbre, d:Arbre) -> None : on remplace le sous-arbre droite de arbre par l'arbre d.
9. recherche(arbre:ABR, cr:Cle) -> Noeud
10. parent(arbre:Arbre) -> Arbre : renvoie le parent de arbre si il existe.