Get best of the week

Arbres rouge-noir en javascript

image

Salut Habr! Arbres rouge-noir récemment étudiés. J'ai essayé de visualiser les détails du fonctionnement des algorithmes d'insertion et de suppression sur d3.js. J'espère que le résultat aidera à gagner du temps pour ceux qui étudient les algorithmes en javascript. Vous pouvez le voir ici . Le code source de l'implémentation à partir duquel je me suis appuyé ici . Sous les détails courts du chat.

Rechercher des solutions existantes


L'objectif principal de l'idée était de comprendre la mise en œuvre de l'algorithme et de le visualiser. La première étape a été de rechercher une implémentation avec des explications complètes et compréhensibles et du code js. Dans le processus de recherche, il était regrettable que les auteurs aient parfois inachevé la source, par exemple, il existe un algorithme d'insertion, mais pas de suppression. Ou ils font une visualisation comme celle-ci , mais ils ne fournissent pas de liens vers la source. J'ai ensuite trouvé cet excellent article. Mais au moins tuer, je ne comprends toujours pas pourquoi l'auteur a inséré le code avec des images et n'a pas donné de lien vers le code source sur demande dans les commentaires. Il y a aussi un paquet npm red-black-tree , dont le code source entier est: 'in progress ...' dans le fichier Lisezmoi. A également trouvé une implémentation populaire des arbres rouge-noir sur js, dont dépendent beaucoup de packages et des millions de téléchargements par semaine, mais le code y a cinq ans.

Priorisation et spécification des tâches


Cerveaux de Porakinin, j'ai décidé que la lisibilité et l'intelligibilité du code à des fins éducatives étaient plus importantes, alors j'ai pris comme base l'article mentionné au début, et non le paquet npm. L'implémentation s'est avérée plus pratique et visuelle en termes de lecture de code. Dans l'article, l'auteur commence par un arbre binaire, puis l'étend au rouge-noir. Pour la visualisation, il semble tout à fait logique d'hériter d'un arbre rouge-noir et de faire un arbre animé. Par conséquent, après avoir retapé le code et m'assurer qu'il fonctionne, j'ai commencé à dessiner un arbre animé. D3.js. vient à la rescousse. Il existe de merveilleuses transitions qui vous permettent de déplacer les éléments vers les positions souhaitées et de les transformer en états appropriés, tout au long de l'algorithme.

La signification des arbres rouge-noir


J'ai longtemps réfléchi, comme de manière simple, pour expliquer quoi. Probablement, tout de même, vous devez lire la théorie à partir de différentes sources. Comme le dit le proverbe: "Vous ne jetterez pas de mots d'une chanson." Mais de simples conclusions sommaires peuvent être formulées en un mot. L'essentiel est qu'il existe plusieurs cas lors de l'insertion et de la suppression d'un élément, selon les «grands-pères», les «papas», les «oncles», les «enfants», les «frères» qui repeignent et se déplacent (tournent) du côté où il y a moins d'éléments . Par conséquent, il n'arrive jamais que le chemin du nœud le plus éloigné au nœud racine soit trop long, de sorte que la recherche de l'élément souhaité dans une telle structure est très rapide. Eh bien, cela est compensé par la complexité de l'insertion et de la suppression.

More articles:


All Articles