Arbre de Van Emde Boas

Complexité en temps
Découvreur ou inventeur	Peter van Emde Boas
Date de découverte	1975
Pire cas
Moyenne
Meilleur cas
Pire cas
Moyenne
Meilleur cas

Un arbre de Van Emde Boas, aussi appelé une file de priorité de Van Emde Boas prononcé en néerlandais : [vɑn 'ɛmdə 'boːɑs]), connu aussi sous le nom arbre vEB, est une structure de données sous forme d'arbre qui implémente un tableau associatif avec des clés formées d'entiers à $m$ bits. Elle réalise toutes les opérations en temps $O(\log m)$ ou, de manière équivalente, en temps $O(\log \log M)$ , où $M=2^{m}$ est le plus grand nombre d'éléments que peut contenir l'arbre. Il ne faut pas confondre $M$ avec le nombre d'éléments effectivement présents dans l'arbre, nombre qui sert, dans d'autres structures de données, à mesurer l'efficacité de la structure. Un arbre vEB a de bonnes performances quand il contient beaucoup d'éléments. La structure de données a été inventée par l'informaticien théoricien néerlandais Peter van Emde Boas en 1975^[1]^,^[2]^,^[3].

Structure

Les clés utilisées dans un arbre vEB sont des entiers de $m$ bits, donc des entiers compris entre 0 et $M-1$ , où $M=2^{m}$ . Ce nombre est aussi le nombre maximal de données contenues dans un tel arbre. On suppose, pour simplifier, que $m$ lui-même est une puissance de 2.

Un arbre vEB T de taille $M$ , à clés dans $\{0,\ldots ,M-1\}$ , est composé

d'un arbre vEB de taille ${\sqrt {M}}$ appelé le « sommaire », ou « top » et noté T.top
d'un tableau, noté aussi « bottom », de ${\sqrt {M}}$ arbres « feuilles » vEB de taille ${\sqrt {M}}$ , indicé par les entiers de $\{0,\ldots ,{\sqrt {M}}-1\}$ , notés T.bottom[0], etc., T.bottom[ ${\sqrt {M}}-1$ ].

L'arbre sommaire et les arbres feuilles sont de taille ${\sqrt {M}}$ et ont pour clés des entiers de $m/2$ bits, composés à partir des clés pour l'arbre T : Si $x$ est un entier sur $m$ bits, alors $x=a2^{m/2}+b$ , où $a$ est l'entier écrits sur les $m/2$ bits de poids fort de $x$ , et $b$ l'entier représenté par les $m/2$ bits de poids faible. Les entiers $a$ et $b$ sont aussi notés de manière plus fonctionnelle hi(x) et lo(x). L'arbre sommaire contient, pour $a$ , un pointeur vers l'arbre feuille d'indice $a$ , si cet arbre n'est pas vide, et la valeur associée à la clé $b$ dans l'arbre feuille est la valeur cherchée. Ainsi, la valeur associée à x dans T est la valeur associée à $b$ dans l'arbre T.bottom[a], ou encore T.bottom[hi(x)].lo(x).

De plus, un arbre vEB T maintient deux valeurs $T.\min$ et $T.\max$ qui contiennent la plus petite et la plus grande valeur présente dans l'arbre. Ces valeurs ne figurent pas ailleurs dans l'arbre. Si l'arbre est vide, on pose $T.\min =M$ et $T.\max =-1$ . Une variante consiste à maintenir un champ additionnel T.taille qui simplifie ce test.

Opérations

Un arbre vEB réalise les opérations d'un tableau associatif ordonné, ce qui comprend les opérations usuelles d'un tel tableau, et deux autres opérations, relatives à l'ordre, qui sont suivant et précédent^[4] qui donnent l'élément immédiatement supérieur respectivement inférieur présent dans l'arbre ; en plus les opérations minimum et maximum retournent respectivement le plus petit et le plus grand élément contenu dans l'arbre. Ces deux éléments sont trouvés en temps constant $O (1)$ , parce qu'ils figurent à des emplacements séparés dans l'arbre^[5].

insérer : insère la paire (clé,valeur) ;
supprimer : supprime la paire (clé,valeur) donnée par la clé ;
chercher : retourne la valeur associée à une clé donnée ;
suivant : retourne la paire (clé, valeur) avec la plus petite clé strictement supérieure à la clé donnée ;
précédent : retourne la paire (clé, valeur) avec la plus petite clé strictement inférieur à la clé donnée ;
minimum : retourne la plus petite valeur contenue dans l'arbre ;
maximum : retourne la plus grande valeur contenue dans l'arbre .

Détail des opérations

L'opération suivant(T, x) cherche le successeur de x dans l'arbre : On test d'abord si x est inférieur à l'élément minimum ou supérieur à l'élément maximum dans l’arbre. Dans le premier cas, le successeur est T.min, dans le deuxième cas, il n'y a pas de successeur et la réponse est M. Sinon, on pose x = a ${\sqrt {M}}$ + b, avec a= hi(x) et b=lo(x), et on teste si b est plus petit que le maximum de l'arbre feuille T.bottom[a] ; dans l'affirmative, on la cherche récursivement dans ce sous-arbre, mais avec le paramètre b. Sinon, le successeur est le min de l'arbre T.bottom[c], où c est le suivant de a dans l'arbre sommaire ; on cherche dans l'arbre suivant dans le sommaire et on retourne son plus petit élément.

Formellement :

fonction suivant(T, x).
    si x < T.min alors
        retourner T.min
    si x ≥ T.max alors 
        retourner M
    poser x = a ${\sqrt {M}}$  + b
    si b < T.bottom[a].max alors
        retourner a ${\sqrt {M}}$  + suivant(T.bottom[a], b)
    sinon
        c = suivant(T.top,a+1);
        retourner c ${\sqrt {M}}$  + T.bottom[c].min
end

La fonction effectue un nombre constant d'opérations avant un éventuel appel récursif avec un paramètre dont la taille est la racine carrée. Ceci donne pour le temps de calcul la formule $T(m)=T(m/2)+O(1)$ , d'où un temps en $O (log m) = O (log log M)$ .

Insertion

L'appel insérer(T, x) insère la valeur x dans l'arbre vEB T, comme suit :

Si T est vide ou contient un seul élément, l'insertion ne pose pas de problème (sauf qu'ils rallongent le code). Dans les autres cas, il y a deux étapes :

Si $x<T.\min$ , on échange x et $T.\min$ , de même pour $x$ et $T.\max$
Ensuite, on procède à la véritable insertion : avec $x=a{\sqrt {M}}+b$ , on cherche l'entrée pour a dans l'arbre sommaire, et si elle n'existe pas, on la crée, puis on insère la clé b dans l'arbre feuille.

Formellement :

fonction insérer(T, x)
    si T est vide alors
        T.min = T.max = x;
        retourner
    si T est un singleton alors
        si x < T.min alors T.min = x
        si x > T.max alors T.max = x
    si x < T.min alors
        échanger(x, T.min)
    si x > T.max alors
        échanger(x, T.max)
    poser x = a ${\sqrt {M}}$  + b
    si T.bottom[a] est vide alors
      insérer(T.top,a)
    insérer(T.bottom[a] , b))
end

La clé pour l'efficacité de cette procédure est le fait que l’insertion d'un élément dans un arbre vEB vide prend un temps constant. Ainsi, même quand l'algorithme fait deux appels récursifs, le premier de ces appel consiste en l'insertion dans un sous-arbre vide et prend un temps constant. Ceci donne à nouveau la relation de récurrence $T(m)=T(m/2)+O(1)$ comme ci-dessus et donc un temps en $O (log log M)$ ..

Suppression

La suppression est, comme toujours, l'opération la plus délicate. L'appel supprimer(T, x) qui supprime x de l'arbre vEB T opère comme suit :

Si x est le seul élément présent dans T, on pose $T.\min =M$ et $T.\max =-1$ pour indiquer que l’arbre résultant est vide.
Sinon, si x = T.min, on cherche la valeur immédiatement supérieure y dans l'arbre, on l'enlève de sa place et on pose T.min=y. La valeur y est T.max si l’arbre est un singleton, ou la plus petite valeur du premier des arbres présents dans le sommaire, soit T.bottom[T.top.min].min, et elle peut donc être trouvée en temps constant ; on opère de manière symétrique si x = T.max ; on cherche la valeur immédiatement inférieure y dans l'arbre et on pose T.max=y. La valeur y immédiatement inférieure est T.min (si l’arbre est un singleton) ou T.bottom[T.top.max].max.
Si x≠T.min et x≠T.max on supprime x dans le sous-arbre T.bottom[a] qui contient x.
Enfin, dans tous les cas, si on supprime un élément dans un sous-arbre singleton, on supprime aussi le sous-arbre.

Formellement :

fonction supprimer(T, x)
    si T.min = T.max = x alors
        T.min = M ; T.max = −1
        retourner
    si x = T.min alors
        T.min = T.bottom[T.top.min].min
        retourner
    si x = T.max alors
        T.max = T.bottom[T.top.max].max
        retourner
   poser x = a ${\sqrt {M}}$  + b
    supprimer(T.bottom[a], b)
    si T.bottom[a] est vide then
        supprimer(T.top, a)
end

À nouveau, l'efficacité de la procédure provient du fait que la suppression dans un arbre vEB réduit à un singleton prend un temps constant.

Discussion

L'hypothèse que m est une puissance de 2 n'est pas indispensable : le fonctions hi(x) et lo(x) peuvent aussi bien retourner l'entier formé des $\lceil m/2\rceil$ plus forts bits et des $\lfloor m/2\rfloor$ plus faibles bits de x,sans changer l'algorithme et son évaluation en temps.

L'implémentation décrite ci-dessus occupe une place en $O (M) = O (2 m)$ . La formule de récurrence pour la place prise par un arbre vEB est

S(M)=O({\sqrt {M}})+({\sqrt {M}}+1)\cdot S({\sqrt {M}})

,

ou, en posant $u={\sqrt {M}}$ ,

S(u^{2})=cu+(1+u)S(u)

pour une constante $c$ . Une résolution directe de $S(u^{2})=u+(1+u)S(u)$ , avec $S(4)=1$ , donne

S(u^{2})=u^{2}-2

ce qui prouve, après quelques ajustements, que $S(M)=O(M)$ ^[6].

Pour des petits arbres, la place additionnelle requise est importante puisqu'elle les linéaire en fonction de la taille maximale, et non de la taille effective. D'autres variantes ont été proposées pour ces cas, comme les tries. On peut aussi remplaces les tables par une table de hachage, ce qui réduit la place à $O (n log M)$ , pour $n$ éléments contenus dans la structure aux dépens d'un coût aléatoire. Les arbres de van Emde Boas peuvent être randomisés pour obtenir une majoration en espace en $O(n)$ au lieu de $S(M)=O(M)$ ^[6], en remplaçant les tables bottom par des tables de hachage. Une telle modification occupe une place en $O(n\log \log M)$ . Mais si on utilise $m/2^{i}$ bits par entrée dans la table de hachage au i-ème niveau de récursion, la structure ne prend qu'un place en $O(n)$ . Si un hachage dynamique parfait est employé, les recherches se font toujours en $O(\log \log M)$ dans le pire des cas, mais les insertions et suppressions prennent un temps amorti moyen en $O(\log \log M)$ .

D'autres structures, y compris les Y-fast trie (en) et les X-fast trie (en) ont été proposées ; elles ont des complexités en temps comparable pour les requêtes et les modifications, et utilisent aussi des tables de hachage pour réduire la complexité en place.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Van Emde Boas tree » (voir la liste des auteurs).

↑ Peter van Emde Boas, « Preserving order in a forest in less than logarithmic time », Foundations of Computer Science (Conference Proceedings,‎ 1975, p. 75-84 (ISSN 0272-5428, DOI 10.1109/SFCS.1975.26).
↑ Peter van Emde Boas, « Preserving order in a forest in less than logarithmic time and linear space », Information Processing Letters, vol. 6, n^o 3,‎ 1977, p. 80–82 (ISSN 0020-0190, DOI 10.1016/0020-0190(77)90031-X).
↑ Peter Van Emde Boas, R. Kaas et E. Zijlstra, « Design and implementation of an efficient priority queue », Mathematical Systems Theory, vol. 10,‎ 1976, p. 99–127 (DOI 10.1007/BF01683268l, présentation en ligne)
↑ Gudmund Skovbjerg Frandsen, « Dynamic algorithms: Course notes on van Emde Boas trees »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}, University of Aarhus, Department of Computer Science.
↑ (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, Cambridge (Mass.), MIT Press, 2009, 3^e éd., xix+1312 (ISBN 978-0-262-03384-8, 978-0-262-53305-8 et 9780262259460, SUDOC 136281273, présentation en ligne), « Chapter 20: The van Emde Boas tree », p. 531–560
↑ ^{a et b} A. Rex, « Determining the space complexity of van Emde Boas trees ».

Voir aussi

Bibliographie

De nombreux cours sont accessibles, notamment :

Erik Demaine (enseignant), Sam Fingeret, Shravas Rao, Paul Christiano (scribes), « Lecture 11 notes », 6.851: Advanced Data Structures (Spring 2012), Massachusetts Institute of Technology, 22 mars 2012 (consulté le 22 février 2018).
Keith Schwarz, « van Emde Boas Trees », CSS 116: Data Structures, Stanford University, 2016 (consulté le 22 février 2018).
Dana Moshkovitz et Bruce Tidor, « Lecture 15 : van Emde Boas Data Structure », Design and Analysis of Algorithms, Course 6.046J/18.410J, sur ocw.mit.edu, MIT OpenCourseWare, 2012 (consulté le 22 février 2018)
Harald Räcke, « Part 3. Data Structures; 10 van Emde Boas Trees », Effiziente Algorithmen und Datenstrukturen I, Technische Universität München, 2014.
Eduardo Laber, David Sotelo, « Van Emde Boas Trees », Departimento de Informatica, Université pontificale catholique de Rio de Janeiro.

Filmographie

Erik Demaine, « Lecture 4: Divide & Conquer: van Emde Boas Trees », sur MIT : vidéo d'un cours sur les arbres de Van Emde Boas.

Articles connexes

Portail de l'informatique théorique

[1] Peter van Emde Boas, « Preserving order in a forest in less than logarithmic time », Foundations of Computer Science (Conference Proceedings,‎ 1975, p. 75-84 (ISSN 0272-5428, DOI 10.1109/SFCS.1975.26).

[van_Emde_Boas1977-2] Peter van Emde Boas, « Preserving order in a forest in less than logarithmic time and linear space », Information Processing Letters, vol. 6, n^o 3,‎ 1977, p. 80–82 (ISSN 0020-0190, DOI 10.1016/0020-0190(77)90031-X).

[3] Peter Van Emde Boas, R. Kaas et E. Zijlstra, « Design and implementation of an efficient priority queue », Mathematical Systems Theory, vol. 10,‎ 1976, p. 99–127 (DOI 10.1007/BF01683268l, présentation en ligne)

[4] Gudmund Skovbjerg Frandsen, « Dynamic algorithms: Course notes on van Emde Boas trees »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}, University of Aarhus, Department of Computer Science.

[5] (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, Cambridge (Mass.), MIT Press, 2009, 3^e éd., xix+1312 (ISBN 978-0-262-03384-8, 978-0-262-53305-8 et 9780262259460, SUDOC 136281273, présentation en ligne), « Chapter 20: The van Emde Boas tree », p. 531–560

[mo-6] {a et b} A. Rex, « Determining the space complexity of van Emde Boas trees ».

[1]

[2]

[3]

[4]

[5]

[6]

v · m Arbre enraciné
Arbre binaire	Arbre binaire de recherche Arbre de fouille Arbre cartésien MVP Tree (en) Top tree (en) T-tree (en)
Arbre équilibré	AA tree (en) Arbre AVL LLRB tree (en) Arbre bicolore Arbre bouc-émissaire Arbre splay Treap
Arbre B	B*-tree (en) Bx-tree (en) UB-tree (en) 2-3 tree (en) Arbre 2-3-4 (a,b)-tree (en) Dancing tree Htree (en)
Trie	Arbre des suffixes Arbre radix Arbre ternaire de recherche X-fast trie (en) Y-fast trie (en)
Partition binaire de l'espace trees	Quadtree Octree Arbre kd (relaxé) Implicit k-d tree (en) Vp-tree
Arbres non binaires	Arbre exponentiel Fusion tree (en) arbre d'intervalles arbre PQ arbre de portée (range tree) arbre SPQR arbre de Van Emde Boas
Arbre de base de données spatiales	R-arbre R+ tree (en) R* tree (en) X-tree (en) M-tree (en) arbre de segments Hilbert R-tree (en) Priority R-tree (en)
Autres arbres	Arbre de Merkle Arbre couvrant de poids minimal Arbre syntaxique Arbre de la syntaxe abstraite Finger tree (en) Order statistic tree (en) Arbre métrique Cover tree (en) BK-tree (en) Doubly chained tree iDistance (en) Link-cut tree (en) Fenwick tree (en) Tas Binaire Binomial Fibonacci Arbre cousu

Structure

Opérations

Détail des opérations

Suivant

Insertion

Suppression

Discussion

Notes et références

Voir aussi

Bibliographie

Filmographie

Articles connexes