Qu'est-ce que Arbre binaire de recherche (binary search tree) ?

Arbre binaire dans lequel, pour chaque nœud, toutes les valeurs du sous-arbre gauche sont plus petites et toutes celles du sous-arbre droit plus grandes que celle du nœud. La recherche, l'insertion et la suppression prennent un temps proportionnel à la hauteur de l'arbre, et un parcours infixe visite les valeurs dans l'ordre croissant.

Nom japonais: 二分探索木

« Arbre binaire de recherche (binary search tree) » apparaît dans 4 questions d'entraînement réparties sur 1 thèmes, dont Structures de données et algorithmes.

Domaine: Structures de données et algorithmes

Recherche, insertion et suppression

Une recherche part de la racine et passe à l'enfant gauche si la cible est plus petite que le nœud, ou à l'enfant droit si elle est plus grande, et recommence jusqu'à trouver une correspondance ou jusqu'à ce qu'il n'y ait plus d'enfant. L'insertion effectue une recherche et rattache un nouveau nœud à l'endroit où la recherche s'est arrêtée faute d'enfant. La suppression retire un nœud qui a zéro ou un enfant et reconnecte l'enfant ; un nœud qui a deux enfants est remplacé par la plus petite valeur de son sous-arbre droit (ou la plus grande de son sous-arbre gauche), et c'est ce nœud-là qui est supprimé. Chaque opération prend un temps proportionnel au nombre de niveaux entre la racine et une feuille (la hauteur de l'arbre).

Arbres déséquilibrés et arbres auto-équilibrés

Un arbre binaire de recherche de n nœuds a une hauteur d'environ log₂ n s'il est équilibré, mais insérer des valeurs dans l'ordre trié, comme 1, 2, 3, …, produit une chaîne unique qui s'étend d'un seul côté, de hauteur n−1. Une recherche y prend alors O(n), comme dans une liste chaînée. Les arbres AVL et les arbres rouge-noir sont des arbres binaires de recherche auto-équilibrés qui se réorganisent par des opérations appelées rotations à chaque insertion et suppression, ce qui maintient la hauteur en O(log n) ; ils servent aux dictionnaires et ensembles ordonnés de nombreux langages de programmation.

Ordres de parcours

Parmi les façons de visiter tous les nœuds d'un arbre figurent le parcours préfixe, qui visite chaque nœud en premier ; le parcours infixe, qui visite le sous-arbre gauche, le nœud, puis le sous-arbre droit ; le parcours postfixe, qui visite d'abord les enfants ; et le parcours en largeur (parcours par niveaux), qui visite l'arbre niveau par niveau. Le parcours infixe d'un arbre binaire de recherche énumère les valeurs dans l'ordre croissant, ce qui donne un listage trié. Le parcours postfixe d'un arbre d'expression donne la notation polonaise inverse.

S'entraîner : questions sur Arbre binaire de recherche (binary search tree)

Quand on parcourt un arbre binaire de recherche dans l'ordre infixe (sous-arbre gauche, puis le nœud, puis sous-arbre droit), dans quel ordre se présentent les valeurs des nœuds visités ? On suppose toutes les valeurs distinctes.

ADans l'ordre croissant (la plus petite d'abord)
BDans l'ordre où elles ont été insérées
CPar proximité avec la racine (les moins profondes d'abord)

Afficher la réponse et l'explication

Réponse : A. Dans l'ordre croissant (la plus petite d'abord)

Dans un arbre binaire de recherche, pour chaque nœud, toutes les valeurs du sous-arbre gauche sont plus petites que celle du nœud et toutes celles du sous-arbre droit sont plus grandes. Visiter le sous-arbre gauche, le nœud puis le sous-arbre droit parcourt donc les valeurs de la plus petite à la plus grande : le résultat est dans l'ordre croissant. Visiter les nœuds par proximité avec la racine est un parcours en largeur (parcours par niveaux), qui avance niveau par niveau, de gauche à droite. L'ordre d'insertion influe sur la forme de l'arbre, mais ne correspond à l'ordre d'aucun de ces parcours.

On insère dans cet ordre les valeurs 50, 30, 70, 20, 40, 60, 80 dans un arbre binaire de recherche vide. Dans quel ordre les nœuds sont-ils visités quand on parcourt l'arbre dans l'ordre postfixe (sous-arbre gauche, sous-arbre droit, puis le nœud) ?

A50, 30, 20, 40, 70, 60, 80
B20, 40, 30, 60, 80, 70, 50
C20, 30, 40, 50, 60, 70, 80

Afficher la réponse et l'explication

Réponse : B. 20, 40, 30, 60, 80, 70, 50

La racine est 50 ; son enfant gauche est 30 (avec les enfants 20 et 40) et son enfant droit est 70 (avec les enfants 60 et 80). Le parcours postfixe visite le sous-arbre gauche sous la forme 20, 40, 30 et le sous-arbre droit sous la forme 60, 80, 70, et seulement ensuite la racine 50. 50, 30, 20, 40, 70, 60, 80 est le résultat du parcours préfixe, qui visite chaque nœud en premier, et 20, 30, 40, … celui du parcours infixe. Le parcours postfixe sert quand les enfants doivent être traités d'abord, par exemple pour supprimer un arbre ou pour produire la notation postfixée à partir d'un arbre d'expression.

Questions fréquentes

En quoi un arbre binaire de recherche diffère-t-il d'un tas ?

Un arbre binaire de recherche suit la règle « plus petit à gauche, plus grand à droite » : il permet donc de chercher n'importe quelle valeur et d'énumérer les valeurs dans l'ordre. Un tas binaire suit seulement la règle « un parent est plus grand (ou plus petit) que ses enfants » : il permet de retirer rapidement le maximum (ou le minimum), mais ne convient pas à la recherche de valeurs quelconques.

Quand utiliser un arbre binaire de recherche ou un arbre B ?

En mémoire, on utilise des arbres binaires de recherche auto-équilibrés ; pour les supports lus par blocs, comme les disques et les SSD, on utilise des arbres B (arbres B+), qui gardent l'arbre peu profond en plaçant de nombreuses clés dans chaque nœud.

« Arbre binaire de recherche (binary search tree) » dans les explications

Dans un arbre binaire de recherche, pour chaque nœud, toutes les valeurs du sous-arbre gauche sont plus petites que celle du nœud et toutes celles du sous-arbre droit sont plus grandes.
Quand on parcourt un arbre binaire de recherche dans l'ordr…
Un arbre équilibré n'aurait qu'environ log₂ 1000 ≈ 10 niveaux ; utiliser un arbre binaire de recherche auto-équilibré comme un arbre AVL ou un arbre rouge-noir, qui se réorganise à chaque insertion et suppression, maintient donc le pire cas en O(log n).
On insère dans cet ordre les valeurs 1, 2, 3, …, 1000 dans …
Un arbre binaire de recherche de 100 millions d'enregistrements demande au moins 27 niveaux environ, et lire un bloc différent à chaque niveau est lent.
Quelle est la raison principale pour laquelle les arbres B …

Questions mentionnant « Arbre binaire de recherche (binary search tree) » (4)

Termes associés

Parcours en largeur (breadth-first search) Liste chaînée (linked list) Algorithme de Dijkstra Algorithme glouton (greedy) Complexité temporelle (notation grand O) File d'attente Parcours en profondeur (depth-first search) Pile (stack) Programmation dynamique Recherche dichotomique (recherche binaire)

Retour au glossaire