Arbre 2-3-4

Un arbre 2-3-4 est un 2-4 arbre B ou arbre B d'ordre 2, c'est-à-dire un arbre comportant uniquement des 2-nœuds, 3-nœuds et 4-nœuds (un N-nœud étant un nœud possédant N-1 clés et N fils), et dont les fils bornent les clés dans les sous arbres (on se reportera à l'article arbre B pour une définition précise).

En tant qu'arbre B, on peut l'utiliser pour implémenter le type abstrait table de symboles. Les opérations de recherche, d'insertion et de suppression sont en O(ln n).

L'aspect le plus intéressant des arbres 2-3-4 est leur représentation sous forme d'arbres bicolores :

  • Un 2-nœud est représenté par un nœud noir seul.
  • Un 3-nœud est représenté par un nœud rouge plus son père noir (un 3-nœud peut être orienté à droite ou à gauche selon que le nœud rouge est le fils droit ou gauche).
  • Un 4-nœud est représenté par 2 nœuds rouges plus leur père noir.

Cette représentation est plus simple à manipuler car il s'agit d'un arbre binaire de recherche, de plus elle gaspille moins de place mémoire quand l'arbre contient peu de 4-nœuds.


Wikimedia Foundation. 2010.

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

Regardez d'autres dictionnaires:

  • Voie 9 3/4 — Univers de Harry Potter L univers de Harry Potter est un monde magique dans lequel le personnage de fiction Harry Potter évolue au sein de la saga littéraire du même nom, écrite par J. K. Rowling. Sommaire 1 Magie 2 Géographie 3 Objets …   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

  • 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 (Informatique) — Pour les articles homonymes, voir Arbre (homonymie) . Un arbre binaire En informatique, un arbre est une …   Wikipédia en Français

  • Arbre (informatique) — Pour les articles homonymes, voir Arbre (homonymie) . Un arbre binaire En informatique, un arbre est une …   Wikipédia en Français

  • Arbre (théorie des graphes) — Arbre (informatique) Pour les articles homonymes, voir Arbre (homonymie) . Un arbre binaire En informatique, un arbre est une …   Wikipédia en Français

  • Arbre De Probabilité — Cet article fait partie de la série Mathématiques élémentaires Algèbre Logique Arithmétique Probabilités …   Wikipédia en Français

  • Arbre balancé — Arbre B Schéma définissant un arbre B. Un arbre B (appelé aussi B arbre par analogie au terme anglais « B tree ») est un arbre équilibré qui est principalement mis en œuvre dans les mécanismes de gestion de bases de données et de… …   Wikipédia en Français

Share the article and excerpts

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