Différences

Ci-dessous, les différences entre deux révisions de la page.

--- doc:donnees:stockage [2020/04/26 23:30] – doc:stockage: -> doc:donnees:stockage: root
+++ doc:donnees:stockage [2020/05/11 00:24] (Version actuelle) – Suppression de la taille par défaut pour les images root
@@ Ligne 22: / Ligne 22: @@
 | Dictionnaire, Red-black tree \\ Base : arbre binaire de recherche. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit. \\ __Optimisation__ : 4 cas. Plusieurs cas successifs peuvent s'appliquer sur un même nœud puis on applique les cas sur le nœud parent jusqu'à la racine ou que les modifications s'arrêtent. \\ * Nœud racine rouge : il devient noir. \\ * Nœud père rouge et oncle rouge : le parent et l'oncle deviennent noir et le grand père devient rouge. \\ * Nœud père rouge et oncle noir ou absent avec le grand-père du même coté que le nœud par rapport au parent : Rotation entre le nœud et le parent. \\ * Nœud père rouge et oncle noir ou absent avec le grand-père du coté opposé au nœud par rapport au parent : Rotation entre le grand-père et le parent. \\ Une fois tout terminé, on colorise. | __Complexité__ en $O(log(n))$ \\ __Intérêt__ : amélioration de AVL tree, un seul bit de donnée supplémentaire est nécessaire. \\ [[https://www.youtube.com/watch?v=5IBxA-bZZH8|Source 1]] {{ doc:donnees:stockage:red-black_trees_in_5_minutes_insertions_strategy_-5ibxa-bzzh8.webm?linkonly |Archive 1}}, [[https://www.youtube.com/watch?v=A3JZinzkMpk|Source 2]] {{ doc:donnees:stockage:red-black_trees_in_5_minutes_insertions_examples_-a3jzinzkmpk.mp4?linkonly |Archive 2}}, [[https://www.cs.swarthmore.edu/~adanner/cs41/f08/LLRB.pdf|Source 3]], {{ doc:donnees:stockage:llrb.pdf |Archive 3}}, [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.9178&rep=rep1&type=pdf|Source 4]], {{ doc:donnees:stockage:10.1.1.136.9178.pdf |Archive 4}} | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree.png?200|}} \\ Optimisation \\ {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree-2.png?200|}} {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree-3.png?200|}} {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree-4.png?200|}} {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree-5.png?200|}} {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree-6.png?200|}} |
 | Dictionnaire, AA tree \\ Base : arbre binaire de recherche. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit. Le nouveau nœud a un point de 1. \\ __Optimisation__ : \\ * Si le nœud a un enfant du coté opposé au parent et que l'enfant, le nœud et le parent ont le même point, on fait une rotation entre le nœud et le parent et on incrémente le poids du nœud. \\ * Si le nœud a un parent à droite avec le même poids, on fait une rotation entre le nœud et le parent. | __Complexité__ en $O(log(n))$ \\ __Intérêt__ : amélioration de Red-black tree avec un algorithme d'optimisation plus simple mais plus long et c'est un nombre qui est stocké à la place d'un seul bit. \\ [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.6192&rep=rep1&type=pdf|Source]], {{ doc:donnees:stockage:10.1.1.118.6192.pdf |Archive}} | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-8-aa_tree.png?200|}} \\ Optimisation \\ {{:doc:donnees:stockage:1-dictionaries-8-aa_tree-2.png?200|}} |
-| Dictionnaire, Scapegoat \\ Base : arbre binaire de recherche avec un cœf $0.5 \leqslant \alpha < 1$. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit. \\ __Optimisation__ : \\ * Une fois la nouvelle valeur insérée, on vérifie que la hauteur globale de l'arbre $h(T)$ (le nombre de liens entre le nœud racine et le nœud le plus bas) est $\leqslant$ à $ h_\alpha(n)$ $= \frac{log(n)}{log(1/\alpha)}$ avec n le nombre de nœuds de l'arbre entier. Le non respect de cette condition est nécessaire mais non suffisant pour réorganiser l'arbre. Ensuite, il faut trouver le premier nœud, en partant du nouveau nœud et en remontant jusqu'à la racine, qui ne respecte pas la condition de largeur du sous-arbre : $s(x) \leqslant \alpha \cdot s(x.parent)$ avec $s(x)$ le nombre de nœud dans le sous arbre ayant comme nœud racine $x$. Une fois trouvé, on réorganise le sous-arbre ayant comme nœud racine $x.parent$. \\ * On linéarise le sous-arbre. On prend le nœud racine et on fait une rotation depuis le nœud enfant gauche qui devient le nœud racine. Et on continue jusqu'à ce que le nœud racine n'ait plus d'enfant à gauche. On descend alors à droite et on recommence avec les enfants à gauche et ainsi de suite jusqu'à ce qu'il n'y ait plus d'enfant. \\ * On repart du nœud racine du sous-arbre et on fait une rotation avec le nœud enfant droit. On descend à droite du nouveau nœud racine et on fait une rotation avec le nœud enfant droit. On recommence à faire un rotation un nœud sur deux. Puis on repart du nœud racine et on recommence en faisant une rotation sur un nœud enfant à droite sur deux. On recommence jusqu'à ce que l'arbre soit équilibré. J'ai remarqué une particularité simple, on fait 2 fois moins de rotation à chaque passe (arrondi à l'entier inférieur) : si le sous-arbre a 30 nœuds, la première passe, on fait 15 rotations, la 2ème 7 rotations, la 3ème 3 et la 4ème 1. | __Complexité__ en $O(log(n))$ \\ __Avantage__ : recherche parfaitement en $O(log(n))$. \\ __Inconvénient__ : il faut trouver le $\alpha$ et l'insertion est lente car elle nécessite de fréquente reconstruction de l'arbre. \\ [[http://people.scs.carleton.ca/~maheshwa/Honor-Project/scapegoat.pdf|Source 1]], {{ doc:donnees:stockage:scapegoat.pdf |Archive 1}}, [[http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f07/Artikler/03/Galperin93.pdf|Source 2]], {{ doc:donnees:stockage:galperin93.pdf |Archive 2}}, [[http://www.geeksforgeeks.org/scapegoat-tree-set-1-introduction-insertion/|Source 3]], {{ doc:donnees:stockage:scapegoat_tree_set_1_introduction_and_insertion_-_geeksforgeeks.mhtml |Archive 3}}, [[http://user.it.uu.se/~arnea/ps/gb.pdf|Source 4]], {{ doc:donnees:stockage:gb.pdf |Archive 4}}, [[http://user.it.uu.se/~arnea/ps/gbimpl.pdf|Source 5]], {{ doc:donnees:stockage:gbimpl.pdf |Archive 5}} | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree.png?200|}} \\ Optimisation 1 \\ {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-2.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-3.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-4.png?200|}} \\ Optimisation 2 \\ {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-5.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-6.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-7.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-8.png?200|}} |
+| Dictionnaire, Scapegoat \\ Base : arbre binaire de recherche avec un cœf $0.5 \leqslant \alpha < 1$. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit. \\ __Optimisation__ : \\ * Une fois la nouvelle valeur insérée, on vérifie que la hauteur globale de l'arbre $h(T)$ (le nombre de liens entre le nœud racine et le nœud le plus bas) est $\leqslant$ à $ h_\alpha(n)$ $= \frac{log(n)}{log(1/\alpha)}$ avec n le nombre de nœuds de l'arbre entier. Le non respect de cette condition est nécessaire mais non suffisant pour réorganiser l'arbre. Ensuite, il faut trouver le premier nœud, en partant du nouveau nœud et en remontant jusqu'à la racine, qui ne respecte pas la condition de largeur du sous-arbre : $s(x) \leqslant \alpha \cdot s(x.parent)$ avec $s(x)$ le nombre de nœud dans le sous arbre ayant comme nœud racine $x$. Une fois trouvé, on réorganise le sous-arbre ayant comme nœud racine $x.parent$. \\ * On linéarise le sous-arbre. On prend le nœud racine et on fait une rotation depuis le nœud enfant gauche qui devient le nœud racine. Et on continue jusqu'à ce que le nœud racine n'ait plus d'enfant à gauche. On descend alors à droite et on recommence avec les enfants à gauche et ainsi de suite jusqu'à ce qu'il n'y ait plus d'enfant. \\ * On repart du nœud racine du sous-arbre et on fait une rotation avec le nœud enfant droit. On descend à droite du nouveau nœud racine et on fait une rotation avec le nœud enfant droit. On recommence à faire un rotation un nœud sur deux. Puis on repart du nœud racine et on recommence en faisant une rotation sur un nœud enfant à droite sur deux. On recommence jusqu'à ce que l'arbre soit équilibré. J'ai remarqué une particularité simple, on fait 2 fois moins de rotation à chaque passe (arrondi à l'entier inférieur) : si le sous-arbre a 30 nœuds, la première passe, on fait 15 rotations, la 2ème 7 rotations, la 3ème 3 et la 4ème 1. | __Complexité__ en $O(log(n))$ \\ __Avantage__ : recherche parfaitement en $O(log(n))$. \\ __Inconvénient__ : il faut trouver le $\alpha$ et l'insertion est lente car elle nécessite de fréquente reconstruction de l'arbre. \\ [[http://people.scs.carleton.ca/~maheshwa/Honor-Project/scapegoat.pdf|Source 1]], {{ doc:donnees:stockage:scapegoat.pdf |Archive 1}}, [[http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f07/Artikler/03/Galperin93.pdf|Source 2]], {{ doc:donnees:stockage:galperin93.pdf |Archive 2}}, [[http://www.geeksforgeeks.org/scapegoat-tree-set-1-introduction-insertion/|Source 3]], {{ :doc:donnees:stockage:scapegoat_tree_set_1_introduction_and_insertion_-_geeksforgeeks_2020-04-26_11_52_59_pm_.html |Archive 3}}, [[http://user.it.uu.se/~arnea/ps/gb.pdf|Source 4]], {{ doc:donnees:stockage:gb.pdf |Archive 4}}, [[http://user.it.uu.se/~arnea/ps/gbimpl.pdf|Source 5]], {{ doc:donnees:stockage:gbimpl.pdf |Archive 5}} | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree.png?200|}} \\ Optimisation 1 \\ {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-2.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-3.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-4.png?200|}} \\ Optimisation 2 \\ {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-5.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-6.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-7.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-8.png?200|}} |
 | Dictionnaire, Splay \\ Base : arbre binaire de recherche. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit. Mais on insère pas, on se base sur le nœud en fin de parcours pour l'optimisation. \\ __Optimisation__ : on remonte le nœud jusqu'en haut de l'arbre. Rotation selon 3 cas : \\ * Fils de la racine de l'arbre : rotation du nœud. \\ * Le grand-père est du même coté que le nœud par rapport au parent : rotation du nœud qui monte d'un cran puis rotation à nouveau du nœud qui monte encore d'un cran. \\ * Le grand-père est du coté opposé par rapport au parent : rotation du parent du nœud puis rotation du nœud. \\ Puis lier le nouveau nœud au nouveau nœud racine. | __Complexité__ en $O(log(n))$ \\ __Avantage__ : tri sans stocker la moindre information supplémentaire en se basant uniquement sur le père et le grand père. \\ __Inconvénient__ : nombreuses rotations et l'arbre n'est pas équilibré. | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-12-splay_tree.png?200|}} \\ Optimisations \\ {{:doc:donnees:stockage:1-dictionaries-12-splay_tree-2.png?200|}}{{:doc:donnees:stockage:1-dictionaries-12-splay_tree-3.png?200|}}{{:doc:donnees:stockage:1-dictionaries-12-splay_tree-4.png?200|}}{{:doc:donnees:stockage:1-dictionaries-12-splay_tree-5.png?200|}} |
 | Dictionnaire, Treap \\ Base : arbre binaire de recherche. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit. \\ __Optimisation__ : \\ Une fois le nœud inséré, on lui attribut un point aléatoire. On effectue des rotations successifs entre le nœud et le parent jusqu'à ce que le poids du nœud soit inférieur au point du nœud parent. | __Complexité__ entre $O(n)$ et $O(log(n))$ \\ __Avantage__ : Génération aléatoire. \\ [[https://faculty.washington.edu/aragon/pubs/rst96.pdf|Source 1]], {{ doc:donnees:stockage:rst96.pdf |Archive 1}}, [[https://cis.temple.edu/~wolfgang/cis551/martinez.pdf|Source 2]], {{ doc:donnees:stockage:martinez.pdf |Archive 2}} | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-9-treap.png?200|}} |
@@ Ligne 29: / Ligne 29: @@
 ====File de priorité (Queue)====
 ===Stockage interne sous forme d'un tableau===
-Principe [[https://www.cs.auckland.ac.nz/software/AlgAnim/heaps.html|Data Structures and Algorithms_ Heaps]], {{ doc:donnees:stockage:data_structures_and_algorithms_heaps.mhtml |Archive}}
+Principe [[https://www.cs.auckland.ac.nz/software/AlgAnim/heaps.html|Data Structures and Algorithms_ Heaps]] {{ :doc:donnees:stockage:data_structures_and_algorithms_heaps_2020-04-29_6_23_14_pm_.html |Archive du 1998 le 29/04/2020}}
-{{:doc:donnees:stockage:heap5.gif?301|}}{{:doc:donnees:stockage:heap6.gif?271|}}
+{{:doc:donnees:stockage:heap5.gif|}}{{:doc:donnees:stockage:heap6.gif|}}
 Tous les nœuds d'une rang horizontal doivent être remplis avant de passer au rang inférieur. Le rang en cours se remplit de gauche à droite sans laisser de nœud vide.
@@ Ligne 40: / Ligne 40: @@
 ^ Type ^ Insertion ^ Commentaire ^ Exemple ^
 | Heap \\ Une donnée par nœud. Jusqu'à deux enfants. | __Insertion__ : on insère le nœud à la suite de l'arbre. \\ __Optimisation__ : on remonte le nœud jusqu'à ce que la valeur du nœud parent soit supérieure. | [[http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf|Source]], {{ doc:donnees:stockage:heaps.pdf |Archive}} | Représentation \\ {{:doc:donnees:stockage:2-priority_queues-1-heap.png?200|}} |
-| d-ary heap \\ Une donnée par nœud. Jusqu'à d enfants. | Identique à Heap. \\ Aucun tri entre les enfants. | [[http://blog.mischel.com/2013/10/05/the-d-ary-heap/|Source]], {{ doc:donnees:stockage:the_d-ary_heap_jim_s_random_notes.mhtml |Archive}} | Représentation \\ {{:doc:donnees:stockage:2-priority_queues-2-d-ary_heap.png?200|}} |
+| d-ary heap \\ Une donnée par nœud. Jusqu'à d enfants. | Identique à Heap. \\ Aucun tri entre les enfants. | [[http://blog.mischel.com/2013/10/05/the-d-ary-heap/|Source]] {{ :doc:donnees:stockage:the_d-ary_heap_jim_s_random_notes_2020-04-29_6_38_57_pm_.html |Archive du 05/10/2013 le 29/04/2020}} | Représentation \\ {{:doc:donnees:stockage:2-priority_queues-2-d-ary_heap.png?200|}} |
 ===Stockage interne sous forme d'arbres===
 __Inconvénient__ : stockage clairsemé en mémoire.
-<note tip>Pourtant, ils ont tous le nom ''heap'', il est possible de tout stocker sous forme d'une pile ?</note>
+<WRAP center round tip 60%>
+Pourtant, ils ont tous le nom ''heap'', il est possible de tout stocker sous forme d'une pile ?
+</WRAP>
 __Avantage__ : fusion de deux piles en $O(1)$.