Arbre Binaire De Recherche

Arbre binaire de recherche

Exemple représentant un arbre binaire de recherche

En informatique, un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque nœud possède une clé, telle que chaque nœud du sous-arbre gauche ait une clé inférieure ou égale à celle du nœud considéré, et que chaque nœud du sous-arbre droit possède une clé supérieure ou égale à celle-ci — selon la mise en œuvre de l'ABR, on pourra interdire ou non des clés de valeur égale. Les nœuds que l'on ajoute deviennent des feuilles de l'arbre.

Sommaire

Opérations

Recherche

La recherche dans un arbre binaire d'un nœud ayant une clé particulière est un procédé récursif. On commence par examiner la racine. Si sa clé est la clé recherchée, l'algorithme termine et renvoie la racine. Si elle est strictement inférieure, alors elle est dans le sous-arbre droit, sur lequel on effectue alors récursivement la recherche. De même si la clé de la racine est strictement supérieure à la clé recherchée la recherche continue sur le sous-arbre gauche. Si on atteint une feuille dont la clé n'est pas celle recherchée, on sait alors que la clé recherchée n'appartient à aucun nœud. On peut la comparer avec la recherche par dichotomie qui procède à peu près de la même manière sauf qu'elle accède directement à chaque élément d'un tableau au lieu de suivre des liens.

Cette opération requiert un temps en O(log(n)) dans le cas moyen, mais O(n) dans le cas critique où l'arbre est complètement déséquilibré et ressemble à une liste chaînée.

Insertion

L'insertion d'un nœud commence par une recherche : on cherche la clé du nœud à insérer ; lorsqu'on arrive à une feuille, on ajoute le nœud comme fils de la feuille en comparant sa clé à celle de la feuille : si elle est inférieure, le nouveau nœud sera à gauche ; sinon il sera à droite.

La complexité est évidemment la même que pour la recherche : O(ln n) dans le cas moyen et O(n) dans le cas critique.

Suppression

Plusieurs cas sont à considérer, une fois que le nœud à supprimer a été trouvé à partir de sa clé :

  • Suppression d'une feuille : Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils.
  • Suppression d'un nœud avec un enfant : Il faut l'enlever de l'arbre en le remplaçant par son fils.
  • Suppression d'un nœud avec deux enfants : Supposons que le nœud à supprimer soit appelé N (le nœud de valeur 7 dans le graphique ci-dessous). On le remplace alors par son successeur le plus proche (le nœud le plus à gauche du sous-arbre droit - ci-dessous, le nœud de valeur 9) ou son plus proche prédécesseur (le nœud le plus à droite du sous-arbre gauche - ci-dessous, le nœud de valeur 6). Cela permet de garder une structure d'arbre binaire de recherche. Puis on applique à nouveau la procédure de suppression à N, qui est maintenant une feuille ou un nœud avec un seul fils.

Suppression d'un nœud interne avec deux enfants dans un arbre binaire de recherche

Pour une implémentation efficace, il est déconseillé d'utiliser uniquement le successeur ou le prédécesseur car cela contribue à déséquilibrer l'arbre.

Dans tous les cas cette opération requiert de parcourir l'arbre de la racine jusqu'à une feuille : le temps d'exécution est donc proportionnel à la profondeur de l'arbre qui vaut n dans le pire des cas, d'où une complexité maximale en O(n).

Parcours ordonné

On peut facilement récupérer les éléments d'un arbre binaire de recherche dans l'ordre de leurs clés en parcourant récursivement le sous-arbre gauche, puis en ajoutant la racine, puis en parcourant récursivement le sous-arbre droit. On peut évidemment le faire dans l'ordre inverse en commençant par le sous-arbre droit.

Le parcours de l'arbre se fait en O(n), puisqu'il doit passer par chaque nœud.

Tri

On peut dès lors implémenter un algorithme de tri simple mais peu efficace, en insérant toutes les clés que l'on veut trier dans un nouvel arbre binaire de recherche, puis en parcourant de manière ordonnée cet arbre comme ci-dessus.

Le pire temps d'exécution est en O(n²), obtenu lorsque les clés sont déjà ordonnées : on obtient alors une liste chaînée. Par exemple, si on donne dans cet ordre les clés 1, 2, 3, 4, 5, on obtient l'arbre (Vide, 1, (Vide, 2, (Vide, 3, (Vide, 4, (Vide, 5))))). Il y a de nombreuses façons d'éviter ce problème, la plus commune étant l'arbre équilibré. On peut alors arriver à un pire cas en O(n ln n).

Types d'arbres binaires de recherche

Il existe de nombreux types d'arbres binaires de recherche. Les arbres AVL et les arbres rouge-noir sont deux types d'arbres équilibrés. Un arbre splay est un arbre binaire de recherche qui rapproche automatiquement de la racine les éléments utilisés fréquemment. Dans un treap, chaque nœud possède aussi une priorité supérieure à chacun de ses fils.

Liens externes

Ce document provient de « Arbre binaire de recherche ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arbre Binaire De Recherche de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Arbre binaire de recherche — Pour les articles homonymes, voir Arbre (homonymie). Exemple représentant un arbre binaire de recherche En informatique, un arbre binaire de recherche (ABR) est un …   Wikipédia en Français

  • Rotation d'un arbre binaire de recherche — La rotation d un arbre binaire de recherche permet de changer la structure d un arbre binaire de recherche ou ABR sans invalider l ordre des éléments. Une telle rotation consiste en fait à faire remonter un nœud dans l arbre et à en faire… …   Wikipédia en Français

  • Arbre ternaire de recherche — En informatique, un arbre ternaire de recherche (ATR ou TST pour Ternary Search Tree en anglais) est une structure de données adaptée pour la recherche et combinant les avantages d un arbre binaire de recherche et d un arbre préfixe. Sommaire 1… …   Wikipédia en Français

  • Arbre Binaire — En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus… …   Wikipédia en Français

  • Arbre binaire — Pour les articles homonymes, voir Arbre (homonymie). En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine.… …   Wikipédia en Français

  • Arbre Andelson-Velskii et Landis — Arbre AVL Pour les articles homonymes, voir AVL. Un exemple d arbre non AVL. En informatique, les arbres AVL ont été his …   Wikipédia en Français

  • Arbre avl — Pour les articles homonymes, voir AVL. Un exemple d arbre non AVL. En informatique, les arbres AVL ont été his …   Wikipédia en Français

  • Arbre Bicolore — Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomma… …   Wikipédia en Français

  • Arbre rouge-noir — Arbre bicolore Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui… …   Wikipédia en Français

  • Arbre rouge et noir — Arbre bicolore Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”