Arbre 2-3

Invention
Type	Arbre B
Date	1970
Suivi par	Arbre 2-3-4

En informatique théorique, un arbre 2-3 est une structure de données arborescente où chaque nœud ayant des enfants ( nœud interne ) a soit deux enfants (nœud 2) et une étiquette, soit trois enfants (nœud 3) et deux étiquettes. Un arbre 2–3 est un arbre B d'ordre 3. Les feuilles de l'arbre n'ont pas d'enfants et ont une ou deux étiquettes^,. Les arbres 2-3 ont été inventés par John Hopcroft en 1970.

Les arbres 2-3 doivent être équilibrés, c'est-à-dire que chaque feuille doit être à la même profondeur. Cela implique que chaque sous-arbre gauche, du milieu, et droit d'un nœud contiennent des quantités proches de données.

Définitions

On dit qu'un nœud interne est un 2-nœud s'il possède un élément de données et deux enfants.

On dit qu'un nœud interne est un 3-nœud s'il possède deux éléments de données et trois enfants.

Un 4-nœud, comportant trois éléments de données, peut être créé temporairement lors de la manipulation de l'arbre, mais n'est jamais stocké de manière permanente dans l'arbre.

2-nœud
3-nœud

On dira que $T$ est un arbre 2–3 si et seulement si l'une des affirmations suivantes est vraie :

$T$ est vide. C'est-à-dire que $T$ n'a aucun nœud.
$T$ est un 2-nœud d'étiquette a, de fils gauche p et de fils droit q, alors
- $p$ et $q$ sont des arbres 2-3 de même hauteur.
- $a$ est plus grand que tout élément de $p$ .
- $a$ est plus petit que tout élément de $q$ .
T est un 3-nœud d'étiquettes a et b où a<b, de fils gauche p, de fils du milieu q et de fils droit r, alors
- $p$ , $q$ et $r$ sont des arbres 2-3 de même hauteur.
- $a$ est plus grand que tout élément de $p$ et plus petit que tout élément de $q$ .
- $b$ est plus grand que tout élément de $q$ et plus petit que tout élément de $r$ .

Propriétés

Chaque nœud interne est un 2-nœud ou un 3-nœud.
Toutes les feuilles sont au même niveau.
Toutes les données sont conservées en ordre trié.

Voir aussi

Références

↑ Donald E. Knuth, The Art of Computer Programming, vol. 3, Addison Wesley, 1998 (ISBN 978-0-201-89685-5), « 6.2.4 » :
« The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3. »
↑ R. Hernández, J. C. Lázaro, R. Dormido et S. Ros, Estructura de Datos y Algoritmos, Prentice Hall, 2001 (ISBN 84-205-2980-X)
↑ Alfred V. Aho, John E. Hopcroft et Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974 (ISBN 978-0-201-00029-0, lire en ligne ), pp.145–147
↑ Thomas Cormen, Introduction to Algorithms, London, The MIT Press, 2009, 504 (ISBN 978-0-262-03384-8, lire en ligne )
↑ Robert Sedgewick et Kevin Wayne, Algorithms, Addison Wesley, 2011 (ISBN 978-0-321-57351-3), « 3.3 »

Portail de l'informatique théorique

[1] Donald E. Knuth, The Art of Computer Programming, vol. 3, Addison Wesley, 1998 (ISBN 978-0-201-89685-5), « 6.2.4 » :
« The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3. »

[2] R. Hernández, J. C. Lázaro, R. Dormido et S. Ros, Estructura de Datos y Algoritmos, Prentice Hall, 2001 (ISBN 84-205-2980-X)

[3] Alfred V. Aho, John E. Hopcroft et Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974 (ISBN 978-0-201-00029-0, lire en ligne ), pp.145–147

[4] Thomas Cormen, Introduction to Algorithms, London, The MIT Press, 2009, 504 (ISBN 978-0-262-03384-8, lire en ligne )

[A4-5] Robert Sedgewick et Kevin Wayne, Algorithms, Addison Wesley, 2011 (ISBN 978-0-321-57351-3), « 3.3 »