Arbres de recherche

Les arbres de recherche stockent des clés ordonnées dans une structure hiérarchique de sorte que la recherche, l'insertion et la suppression suivent un chemin de la racine à la feuille ; les variantes auto-équilibrées maintiennent ce chemin court pour garantir des opérations en temps logarithmique.

Definition

Un arbre de recherche est une structure de données arborescente qui maintient les clés dans un ordre trié selon un invariant d'ordre par nœud, supportant une recherche, une insertion, une suppression et des requêtes basées sur l'ordre efficaces ; un arbre de recherche équilibré contraint en outre sa forme de sorte que la hauteur reste logarithmique par rapport au nombre de clés.

Scope

Ce sujet couvre les structures de dictionnaire ordonnées basées sur des arbres : l'arbre binaire de recherche et son invariant d'ordre, les schémas d'auto-équilibrage qui limitent la hauteur (AVL, rouge-noir, et autres), et les arbres équilibrés multi-voies tels que les B-arbres conçus pour le stockage externe. Il aborde les opérations que ces structures supportent au-delà de la simple recherche — prédécesseur, successeur, requêtes de plage et parcours ordonné — et les contraste avec les tables de hachage, qui ne préservent pas l'ordre.

Core questions

• Comment l'invariant d'ordre de l'arbre binaire de recherche transforme-t-il la recherche en un parcours de la racine à la feuille ?
• Pourquoi un arbre déséquilibré peut-il se dégrader en temps linéaire, et comment l'équilibrage l'empêche-t-il ?
• Quelles rotations ou règles structurelles maintiennent les arbres AVL et rouge-noir équilibrés ?
• Pourquoi les B-arbres sont-ils mieux adaptés au stockage sur disque et en base de données que les arbres binaires ?
• Quand les opérations préservant l'ordre justifient-elles le coût supplémentaire par rapport à une table de hachage ?

Key concepts

• invariant de l'arbre binaire de recherche
• rotations d'arbre
• arbres AVL
• arbres rouge-noir
• B-arbres
• hauteur et équilibre de l'arbre
• parcours en ordre (in-order traversal)
• requêtes de plage et de successeur

Key theories

L'équilibrage de la hauteur garantit des opérations logarithmiques

En maintenant un invariant d'équilibre par des rotations ou des règles structurelles, les arbres auto-équilibrés conservent une hauteur O(log n), garantissant une recherche, une insertion et une suppression en O(log n) dans le pire des cas, quelle que soit l'ordre d'entrée.

Arbres multi-voies pour la mémoire externe

Les B-arbres stockent de nombreuses clés par nœud pour correspondre aux tailles des blocs de disque, minimisant le nombre d'accès lents à la mémoire externe ; cela en fait la structure standard pour les bases de données et les systèmes de fichiers.

Clinical relevance

Les arbres de recherche sont essentiels aux systèmes nécessitant un accès ordonné : les arbres rouge-noir implémentent des cartes et des ensembles ordonnés dans les bibliothèques standard, les B-arbres et leurs variantes sont la structure d'index dominante dans les bases de données relationnelles et les systèmes de fichiers, et les arbres équilibrés supportent les requêtes de plage, la planification d'intervalles et les structures de recherche géométrique.

History

Les arbres AVL, les premiers arbres binaires de recherche auto-équilibrés, ont été introduits par Adelson-Velsky et Landis en 1962. Bayer et McCreight ont introduit les B-arbres en 1972 pour les grands index ordonnés, et les arbres rouge-noir ont été développés par Guibas et Sedgewick en 1978 comme un schéma d'équilibrage pratique, devenant la base de nombreuses implémentations de bibliothèques standard.

Key figures

• Georgy Adelson-Velsky
• Evgenii Landis
• Rudolf Bayer
• Robert Sedgewick
• Robert Tarjan

Seminal works

• bayer1972
• cormen2009

Frequently asked questions

Pourquoi ne pas toujours utiliser une table de hachage au lieu d'un arbre de recherche ?

Les tables de hachage offrent des recherches moyennes plus rapides mais sans ordre. Les arbres de recherche maintiennent les clés triées, permettant des requêtes de plage, une itération ordonnée et des recherches de prédécesseur/successeur en O(log n), ce que les tables de hachage ne peuvent pas faire efficacement. Le choix dépend de l'importance de l'ordre.

Pourquoi les bases de données utilisent-elles des B-arbres au lieu d'arbres binaires de recherche ?

Les B-arbres regroupent de nombreuses clés dans chaque nœud pour correspondre à la taille d'un bloc de disque, de sorte qu'une recherche accède à beaucoup moins de blocs de mémoire externe lents qu'un arbre binaire ayant le même nombre de clés. Cela minimise les E/S, qui dominent les performances dans les bases de données et les systèmes de fichiers.