LG

Gnarley trees : présente tous les types de stockage de données sous forme d'arbres. Un must. Le tout accompagné d'une application de visualisation.

Archive du site

Archive de l'application avec le code du Apr 6, 2015.

Source (Apr 6, 2015).

Les avantages / inconvénients indiqués dans les tableaux sont par rapport à l'arbre présenté dans la ligne précédente.

Un dictionnaire permet l'insertion, la recherche, la modification et la suppression des données dans n'importe quel ordre. Le stockage est réalisé sous forme d'un arbre trié.

Type	Insertion et optimisation	Suppression	Commentaire
Dictionnaire, Arbre binaire de recherche	On descend à droite si plus grand, à gauche si plus petit. On insère lorsque l'enfant n'existe pas. Complexité : entre $O(log(n))$ et $O(n)$	Si un seul enfant, on fait la liaison entre le père et l'enfant. Si deux enfants, on remplace le nœud par l'enfant le plus gauche dans l'arbre de l'enfant à droite. Complexité : entre $O(log(n))$ et $O(n)$	Insertion et suppression simple à implémenter mais arbre peu équilibré. Source 1, Archive 1, Source 2, Archive 2, Source 3, Archive 3
Dictionnaire, Rotation On se base sur un arbre existant.	On n'insère pas, on optimise seulement. On remonte d'un niveau le nœud choisi et le parent descend. Soit 4 blocs : le nœud et son parent, un bloc par enfant du nœud et leur descendance, un bloc pour l'autre enfant du parent et sa descendance. Le bloc du centre (lié au nœud montant) devient lié au parent (qui descend) et son niveau ne change donc pas. Les deux blocs des extrémités ne changent pas de parent. Le bloc lié au parent descend avec lui et le bloc lié à l'enfant monte avec lui.	-	L'objectif de cette opération est de réduire la hauteur de l'arbre. Source, Archive
Dictionnaire, AVL tree Base : arbre binaire de recherche.	Insertion : identique à l'arbre binaire de recherche. Optimisation : on remonte le chemin du nouveau nœud. À chaque nœud on calcule la différence de profondeur maximale entre les deux enfants. Si la différence est d'au moins de 2, on ne remonte plus. Si le chemin du dessous est droite-droite ou gauche-gauche, on ne fait qu'une seule rotation entre le nœud et l'enfant. Si le chemin du dessous est gauche-droite ou droite-gauche, on fait deux rotations : le petit-enfant et l'enfant puis le nouveau enfant et le nœud. Complexité : $O(log(n))$	Identique à l'arbre binaire de recherche. On applique les mêmes optimisations qu'en insertion depuis le nœud supprimé. Complexité : $O(log(n))$	Avantage : la disposition de l'arbre est optimal pour fonctionner en $O(log(n))$. Inconvénient : l'insertion est plus longue et nécessite soit de stocker constamment le nombre de niveaux maximum en dessous de chaque nœud soit de parcourir toute la descendance de chaque nœud du parcours du nouveau nœud. Source, Archive
Dictionnaire, 2-3 tree Un nœud simple a 0 ou 2 enfants. Un nœud double a 0 ou 3 enfants.	Insertion : on descend à droite si plus grand, à gauche si plus petit, au milieu si entre deux. On insère dans le nœud existant qui n'a pas d'enfant, par ordre croissant. Optimisation : si le nœud possède 3 valeurs, on le sépare en 3 nœuds. Le nœud de gauche a comme enfants les valeurs inférieures au nœud du centre et le nœud de droite a comme enfants les valeurs supérieures au nœud du centre. Le nœud du centre est intégré au nœud parent. On recommence l'opération tant que le nœud parent a 3 valeurs. Complexité : $O(log(n))$	Identique à l'arbre binaire de recherche. Si on supprime la valeur à gauche du nœud, on parcourt l'arbre enfant du centre et non celui de droite. Si un nœud se retrouve sans valeur, on récupère une valeur du parent et on fusion l'un des nœuds avec l'autre pour respecter le bon nombre d'enfants. Complexité en $O(log(n))$	Avantage : pas de stockage de données supplémentaire ou d'enfants à parcourir. Tous les nœuds les plus inférieurs ont le même niveau. Inconvénient : deux données à comparer par nœud à la place d'une seule.
Dictionnaire, 2-3-4-tree cf. B-tree d'ordre 4	-	-	-
Dictionnaire, B-tree Entre $(B-1)/2$ et $B-1$ données par nœud. Jusqu'à B enfants.	Insertion : on descend à droite si plus grand, à gauche si plus petit, au nœud entre deux valeurs sinon. On insère dans le nœud existant qui n'a pas d'enfant, par ordre croissant. Optimisation : si le nœud possède B valeurs, on le sépare en 3 nœuds. Le nœud de gauche a comme enfants les valeurs inférieures au nœud du centre et le nœud de droite a comme enfants les valeurs supérieures au nœud du centre. Le nœud du centre est intégré au nœud parent. On recommence l'opération tant que le nœud parent a B valeurs.	Complexité en $O(log(n))$ Avantage : pas vraiment sûr. Peut-être une implémentation parallèle CUDA avec B = 32. Source 1, Archive 1, Source 2, Archive 2	Représentation
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. Source 1 Archive 1, Source 2 Archive 2, Source 3, Archive 3, Source 4, Archive 4	Représentation Optimisation
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. Source, Archive	Représentation Optimisation
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. Source 1, Archive 1, Source 2, Archive 2, Source 3, Archive 3, Source 4, Archive 4, Source 5, Archive 5	Représentation Optimisation 1 Optimisation 2
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 Optimisations
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. Source 1, Archive 1, Source 2, Archive 2	Représentation
Dictionnaire, Skiplist Base : tableaux de listes chaînées.	Insertion : On parcourt la première liste jusqu'à ce que la valeur soit supérieure à la valeur suivante. On passe à la liste chainée en dessous et ainsi de suite jusqu'à la dernière liste chaînée. Optimisation : Une fois la nouvelle valeur insérée, on prend une chance sur deux pour insérer la valeur dans la liste précédente. Puis on continue jusqu'à ce que la chance fasse que la valeur ne soit plus propagée à la liste chaînée précédente.	Complexité entre $O(n)$ et $O(log(n))$ Avantage : Génération aléatoire. Inconvénient : nombreuse duplication de la donnée en mémoire. Source 1, Archive 1, Source 2, Archive 2, Source 3, Archive 3, Source 4, Archive 4, Source 5, Archive 5	Représentation

Principe Data Structures and Algorithms_ Heaps Archive du 1998 le 29/04/2020

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.

Cette structure de données a pour but d'avoir accès à 2 opérations : insertion avec priorité et récupérer la priorité la plus importante. Par contre, la fusion de deux files de priorité est $O(n)$.

Les deux files de priorité du tableau ci-dessous sont stockées sous forme compact en mémoire (tableau).

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.	Source, Archive	Représentation
d-ary heap Une donnée par nœud. Jusqu'à d enfants.	Identique à Heap. Aucun tri entre les enfants.	Source Archive du 05/10/2013 le 29/04/2020	Représentation

Inconvénient : stockage clairsemé en mémoire.

Avantage : fusion de deux piles en $O(1)$.

Type	Insertion	Commentaire	Exemple
Leftist heap Une donnée par nœud. Jusqu'à deux enfants.	Insertion : on compare toujours avec le nœud enfant à droite. S'il est plus grand, on descend à droite. S'il est plus petit, on devient son parent et lui l'enfant à droite. Optimisation : pour chaque nœud du chemin d'insertion : - on calcule le rang $R$ . C'est égal au $min(R(d);R(g))+1$ avec une valeur de $R$ égale 0 si le nœud enfant n'existe pas. - si le nœud frère (à gauche) possède un rang plus petit, on inverse les deux nœuds.	Source, Archive	Représentation Optimisation
Skew heap Une donnée par nœud. Jusqu'à deux enfants.	Insertion : identique à Leftist heap. Optimisation : on part de la racine et on descend toujours à droite. Pour tous les nœuds du chemin, on inverse le nœud à droite et à gauche même si le frère n'existe pas.	Avantage : pas de calcul de rang. Source 1 Archive 1 Source 2 Archive 2 Source 3 Archive 3	Représentation Optimisation
Pairing heap Une donnée par nœud. Infinité d'enfants.	Insertion : si la valeur est supérieur à la racine, le nœud devient la nouvelle racine et la racine un enfant. Si la valeur est inférieur à la racine, on insère le nœud comme enfant de la racine.	Avantage : insertion rapide. Source 1 Archive 1 Source 2 Archive 2 Source 3 Archive 3 Source 4 Archive 4 Source 5 Archive 5	Représentation
Binomial heap Une donnée par nœud. Une infinité d'enfants. Seul le nœud racine peut avoir une infinité de frères.	Insertion : la valeur est insérée comme frère aux nœuds racine avec un rang de 0. Optimisation : Seuls les nœuds du niveau racine ont un rang. Il correspond au nombre de fusion. Tant que deux nœuds racine ont le même rang, le nœud avec la plus petite valeur devient l'enfant de l'autre et celui qui reste au même niveau que les nœuds racine voit son rang incrémenter.	Avantage : moins d'enfants. Source, Archive	Représentation
Lazy binomial heap Identique à Binomial heap.	Insertion : la valeur est insérée comme frère aux nœuds racine.	Avantage : insertion instantanée. Inconvénient : la génération de l'arbre Binomial se fait lors du dépilage. Source 1 Archive 1 Source 2 Archive 2	Représentation
Fibonacci heap Identique à Lazy binomial heap.	Insertion : identique à Lazy binomial heap.	Source, Archive	Représentation