Arbres AVL / rouge-noir

Insérez 1–31 clés entières signées en base 10 de −9999 à 9999, en utilisant au plus 512 caractères. Virgules ou espaces séparent les clés ; les entrées de virgule vides et les virgules finales sont invalides. Les zéros de tête et un signe plus optionnel sont acceptés. Points décimaux, exposants, notation hexadécimale et nombres partiels sont rejetés. Les clés en double sont lues mais ignorées : l’arbre représente un ensemble.

Pas montre une opération réelle : attacher un nouveau nœud, une rotation simple gauche ou droite, un groupe de changements de couleur, une insertion achevée ou un doublon ignoré. Une double rotation a deux cadres de rotation séparés. Les comptes de rotations comptent les rotations individuelles ; les comptes de recoloration comptent les groupes qui changent réellement les couleurs, y compris rétablir une racine noire. Clés lues inclut la clé courante depuis son cadre d’insertion. Le compte de clés uniques exclut les doublons.

Les rotations préservent l’ordre de recherche binaire : toutes les clés du sous-arbre gauche sont plus petites, toutes celles du sous-arbre droit plus grandes. Inordre liste les clés de gauche à droite. L’équilibre AVL est la hauteur gauche moins la hauteur droite, entre −1 et 1 après chaque insertion achevée. Ici un sous-arbre vide a une hauteur 0 et une feuille une hauteur 1.

La variante rouge-noir utilise la réparation d’insertion classique, pas la variante left-leaning. La racine et les feuilles NIL omises sont noires ; les nœuds rouges n’ont pas d’enfants rouges ; tout chemin d’un nœud à une feuille NIL a le même nombre de nœuds noirs. Le tableau de nœuds compte le nœud courant s’il est noir et compte la feuille NIL finale ; NIL seul a donc une hauteur noire 1. Un tiret indique des hauteurs noires inégales pendant la réparation. Les lettres de couleur complètent les couleurs des nœuds.

Les instantanés intermédiaires peuvent violer temporairement l’équilibre ou les propriétés rouge-noir. Le résumé ne les confirme qu’aux frontières d’insertion achevée ou de doublon. Les contours marquent les nœuds affectés ; un contour en tirets marque l’ancienne racine de sous-arbre d’une rotation. Son enfant promu et toute racine de sous-arbre déplacée sont nommés sous l’action.

Lancer reprend une trace en pause et redémarre une trace terminée. Retour et Pas à pas permettent de parcourir les opérations dans les deux sens. Effacer efface la trace et conserve les saisies. Modifier les clés ou le type efface le résultat. L’exemple de réparation sélectionne rouge–noir ; les autres conservent le type. Entrée insère une nouvelle ligne ; Ctrl/Commande+Entrée exécute. Les saisies brutes, même inachevées, la sélection, la vitesse, les détails ouverts et l’étape courante sont enregistrés localement. Un rechargement ou un retour interne restaure une étape valide en pause ; la lecture ne reprend jamais automatiquement. Les grands arbres défilent sans réduire les libellés. L’insertion équilibrée est O(log n) ; les instantanés indépendants et leur dessin ajoutent du travail dans ce visualiseur borné.

Sources : MIT 6.006 (2011), cours 6, arbres AVL ; MIT 6.046 (2005), cours 10, arbres rouge-noir.

L’opération actuelle et l’arbre sont affichés en premier. Les détails du parcours contiennent les compteurs et les clés triées ; les détails des nœuds ouvrent le tableau à défilement local. Pause apparaît uniquement pendant la lecture. Le compteur d’étapes disparaît à la fin.

Le stockage local est limité à 100000 caractères sérialisés. Au-delà, la copie précédente est conservée ; téléchargez toutes les clés avant de recharger ou de quitter la page. La navigation interne conserve le brouillon courant. Une trace accepte au plus 31 clés et 512 caractères ; les brouillons plus longs restent modifiables mais leur exécution est refusée. Les anciennes saisies enregistrées restent lisibles ; les anciennes versions ne stockaient pas les étapes.