Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Arbre bicolore
Résumé
Un arbre bicolore, ou arbre rouge-noir ou arbre rouge et noir est un type particulier d'arbre binaire de recherche équilibré, 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 nomme symmetric binary B-trees (littéralement « arbres B binaires symétriques »). Chaque nœud de l'arbre possède en plus de ses données propres un attribut binaire qui est souvent interprété comme sa « couleur » (rouge ou noir). Cet attribut permet de garantir l'équilibre de l'arbre : lors de l'insertion ou de la suppression d'éléments, certaines propriétés sur les relations entre les nœuds et leurs couleurs doivent être maintenues, ce qui empêche l'arbre de devenir trop déséquilibré, y compris dans le pire des cas. Durant une insertion ou une suppression, les nœuds sont parfois réarrangés ou changent leur couleur afin que ces propriétés soient conservées.
Le principal intérêt des arbres bicolores réside dans le fait que malgré les potentiels réarrangements ou coloriages des nœuds, la complexité (en le nombre d'éléments) des opérations d'insertion, de recherche et de suppression est logarithmique. De plus, cette structure est économe en mémoire puisqu'elle ne requiert qu'un bit supplémentaire d'information par élément par rapport à un arbre binaire classique.
En 1972, Rudolf Bayer conçut une structure de données qui était un cas particulier d'arbre B d'ordre 4 dans lequel chaque chemin entre la racine et les feuilles de l'arbre avait le même nombre de nœuds, ce qui en faisait des arbres parfaitement équilibrés (sans toutefois être des arbres binaires de recherche). Bayer les nomma « arbres B binaires symétriques », et furent ensuite popularisés sous l'appellation d'arbres 2-3-4.
Dans un article datant de 1978 intitulé A Dichromatic Framework for Balanced Trees, Leonidas John Guibas et Robert Sedgewick construisirent les arbres rouge-noir à partir des arbres-B binaires symétriques.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.