Arbre 2-3-4
- 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:
ARBRE — La distinction entre arbre et herbe remonte à une antiquité éloignée. Théophraste (vers 300 av. J. C.) en avait déjà fait la base de sa classification des végétaux, non sans quelque raison à en croire d’actuels botanistes. On sait que Hutchinson… … Encyclopédie Universelle
arbre — ARBRE. s. m. Plante boiseuse, qui croît en grosseur et en hauteur plus que toutes les autres plantes, et qui pousse différentes branches. Grand arbre. Gros arbre. Arbre haut et droit. Arbre tortu, branchu, touffu. Arbre sec. Arbre mort. Arbre… … Dictionnaire de l'Académie Française 1798
arbre — ARBRE. s. m. La premiere r se prononce aussi bien que la seconde, la plus grande des plantes qui est de substance boiseuse, qui croist en grosseur & en hauteur & pousse ordinairement plusieurs branches. Grand arbre. gros arbre. arbre haut & droit … Dictionnaire de l'Académie française
arbre — Arbre, m. penac. Signifie en general toute plante de grosses racines, gros tronc escorçu, eslevée en fueillu et escorçu branchage, Arbor, dont il est fait par Methatese. Arbre franc, est le contraire de sauvage, comme si l on disoit apprivoisé,… … Thresor de la langue françoyse
arbre — marbre … Dictionnaire des rimes
arbre — obs. form of arbor … Useful english dictionary
Arbre — Pour les articles homonymes, voir Arbre (homonymie). Les arbres actuels sont principalement représentés par des espèces du groupe des p … Wikipédia en Français
arbre — (ar br ) s. m. 1° Grand végétal ligneux, et, dans le langage spécial de la botanique, végétal dont le tronc ligneux s élève à plus de six mètres. • Le troisième tomba d un arbre Que lui même il voulut enter, LA FONT. Fabl. XI, 8. • On peut… … Dictionnaire de la Langue Française d'Émile Littré
ARBRE — s. m. Végétal ligneux dont la tige, plus ou moins élevée, ne se garnit ordinairement de branches et de feuilles qu à une certaine hauteur. Grand arbre. Gros arbre. Arbre haut et droit. Arbre tortu, branchu, touffu. Arbre sec. Arbre mort. Arbre… … Dictionnaire de l'Academie Francaise, 7eme edition (1835)
Arbre B — Schéma définissant un arbre B. En informatique un arbre B (appelé aussi B arbre par analogie au terme anglais « B tree ») est une structure de données en arbre équilibré. Les arbres B sont principalement mis en œuvre dans les mécanismes … Wikipédia en Français
ARBRE — n. m. Végétal ligneux dont la tige, plus ou moins élevée, ne se garnit ordinairement de branches et de feuilles qu’à une certaine hauteur. Grand arbre. Bel arbre. Arbre haut et droit. Arbre branchu, touffu. Arbre mort. Arbre qui se dépouille.… … Dictionnaire de l'Academie Francaise, 8eme edition (1935)
