Arbres binaires de recherche

La recherche dichotomique dans une liste triée s'avère très efficace dans la mesure où sa complexité est logarithmique. Néanmoins, le défaut de cet algorithme appliqué aux listes triées se situe au niveau de l'insertion de nouveaux éléments dans la liste. En effet, cette insertion est malheureusement linéaire puisqu'il faut placer l'élément au bon endroit dans la liste de telle sorte qu'elle demeure triée après l'insertion.

Pour pouvoir néanmoins utiliser une recherche efficace dans les situations qui impliquent de nombreuses insertions, il est nécessaire de développer une structure de données plus dynamique que les listes qui permette une recherche et une insertion logarithmique. Les arbres binaires de recherche (ABR) remplissent cette tâche.

Arbres

La plupart des structures de données étudiées jusqu'ici (listes, tuples, files, piles,...) étaient linéaires, c'est-à-dire des structures dont les données sont ordonnées selon l'ordre dans lequel les ajouts et les suppressions d'éléments ont lieu. La structure d'arbre ne répond pas aux caractéristiques des structures linéaires. Composée d'une racine, de branches et de feuilles, cette structure est utilisée dans divers domaines de l'informatique, allant des systèmes de fichiers aux bases de données en passant par les réseaux.

Un arbre est un graphe sans cycle, où des noeuds sont reliés par des arêtes. Il existe trois types de noeuds:

• les noeuds internes qui ont des fils;
• les feuilles qui n'ont pas de fils;
• la racine de l'arbre, qui est l'unique noeud ne possédant pas de père.

Traditionnellement, un arbre est dessiné toujours verticalement avec la racine en haut et les feuilles en bas comme l'illustrent les images suivantes:

La profondeur d'un noeud est la distance, c'est-à-dire le nombre d'arêtes, le séparant de la racine. La hauteur d'un arbre est la plus grande profondeur d'une feuille de l'arbre. La taille d'un arbre est son nombre de noeuds.

Les arbres peuvent être étiquetés. Dans ce cas, chaque noeud possède une étiquette qui est en quelque sorte l'"identifiant" du noeud. Les étiquettes sont généralement très simples (un nombre entier par exemple) et possèdent une relation d'ordre.

Arbres binaires de recherche

Un arbre binaire est un arbre dans lequel chaque noeud possède au plus deux fils, appelés habituellement gauche et droit. Du point de vue des fils, l'élément dont ils sont issus au niveau supérieur est logiquement appelé père ou parent.

Un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque noeud possède une étiquette telle que chaque noeud du sous-arbre de gauche ait une étiquette inférieure à celle du noeud considéré et que chaque noeud du sous-arbre de droite possède une étiquette supérieure à celle-ci.

Les arbres binaires de recherche peuvent être implémentés de différentes manières. Dans un langage orienté objet, ils peuvent être conçus à l'aide de 2 classes, une classe représentant l'arbre dans son ensemble (BinarySearchTree) et une autre représentant les noeuds qui constituent l'arbre (BSTNode).

La classe BinarySearchTree ne contient essentiellement que 2 attributs d'instance: une référence vers la racine de l'arbre (self.root) et le nombre de noeuds présents dans l'arbre (self.size). La classe BSTNode possède quant à elle 5 attributs d'instance: une étiquette (self.key), un contenu (self.content) ainsi que des références vers les noeuds parent (self.parent), frère gauche (self.left) et frère droit (self.right).

Afficher la solution | Masquer la solution