Nora prépare un index fictif de fiches numérotées. Camille devra retrouver un numéro, en ajouter un entre deux anciens, en retirer un et isoler une plage. Les numéros servent à la recherche ; une autre valeur, appelée priorité, décide des attaches verticales. Aucun temps de consultation ou rangement matériel n'est mesuré. Les deux valeurs demeurent sur chaque fiche pendant les changements.
Trois notices du Metropolitan Museum of Art sont citées pour leurs catégories de catalogue seulement.
La première notice indique la catégorie « Books » : https://www.metmuseum.org/art/collection/search/336400 .
La deuxième indique la catégorie « Drawings » : https://www.metmuseum.org/art/collection/search/336500 .
La troisième indique aussi « Drawings » : https://www.metmuseum.org/art/collection/search/336600 .
Deux règles fixent un premier arbre
Les numéros initiaux sont 10,20,30 et 40. Leurs priorités respectives sont 40,10,30 et 20, toutes distinctes. Un numéro plus petit se recherche à gauche, un plus grand à droite. Verticalement, chaque parent doit porter une priorité plus petite que celle de ses enfants. Cette construction classique à clés et priorités ne constitue pas une invention.
La première fiche est 20, dont la priorité 10 est la plus petite. À gauche, elle porte 10 de priorité 40. À droite, elle porte 40 de priorité 20, lui-même avec 30 de priorité 30 à gauche. La lecture gauche, fiche, droite redonne 10,20,30,40. Les priorités lues dans cet ordre ne sont pas triées. Elles fixent les parents, tandis que les numéros fixent les côtés. Construire cet arbre statique ne remplit pas encore les commandes de changement.
Insérer au milieu ne prolonge pas la dernière branche
Camille reçoit 25 avec la priorité 5. Pour trouver son emplacement selon les numéros, elle compare 25 à 20, puis 40, puis 30. Elle arrive à la branche gauche vide de 30, où 25 peut être ajouté sans renommer une ancienne fiche. Cette place conserve l'ordre de recherche, mais donne à 30, priorité 30, un enfant de priorité 5 : la règle verticale échoue.
Elle fait d'abord remonter 25 au-dessus de 30 par une rotation à droite de cette petite branche. Trente devient l'enfant droit de 25 ; les autres branches de l'arbre restent à leur place. La priorité 5 domine désormais 30, mais 25 reste sous 40, dont la priorité 20 est encore trop grande pour le garder comme enfant. Camille effectue donc une deuxième rotation à droite, cette fois sous 40. Vingt-cinq prend sa place de tête locale,40 devient son enfant droit et récupère 30 comme enfant gauche. La fiche 30 n'est ni abandonnée ni attachée à gauche de 25 : son numéro est supérieur à 25 et inférieur à 40. Camille conserve ce morceau intermédiaire entre ces deux numéros pendant le mouvement.
Vingt-cinq est maintenant l'enfant droit de 20. Une troisième rotation, à gauche de 20, le fait monter à la racine. Vingt reste à gauche de 25, avec 10 à sa gauche ;40 reste à droite, avec 30 à sa gauche. Les priorités de chaque parent sont plus petites que celles de leurs enfants, et la lecture des numéros est 10,20,25,30,40. Camille ne se contente pas de constater que 5 est devenu le plus petit nombre du dessin : elle vérifie aussi les attaches de 10 et 30, qui n'ont pas été les fiches tournées au dernier geste. L'insertion intérieure a transformé plusieurs liens, tout en gardant les deux valeurs de chaque fiche et leur place dans l'ordre numérique.
Une recherche de 30 dans le nouvel arbre compare 25, puis 40, puis 30. Une recherche de 25 s'arrête dès sa première comparaison. Celle de 10 compare 25,20 puis 10 ; elle doit conserver le lien ancien entre 20 et 10 après la remontée de 25. Nora contrôle également l'absence de 22 : après 25 puis 20, la recherche atteint la droite vide de 20. Elle ne remet pas 20 comme résultat au seul motif qu'il était le dernier numéro visité. Les changements sont validés sur les anciennes recherches comme sur la nouvelle fiche ; faire réussir seulement une recherche de 25 aurait laissé ouvertes des pertes de branches pendant les rotations.
La priorité sert à choisir les mouvements, pas à répondre à la comparaison d'un numéro demandé. Si Camille recherchait 30 en comparant ses priorités aux 5,10 ou 20 rencontrées, elle n'appliquerait plus la règle de l'index. De même, échanger les numéros 20 et 25 dans l'ancien dessin pour mettre la meilleure priorité au sommet ne transporterait pas les bonnes branches. Nora garde donc les deux champs ensemble pendant la rotation. La valeur 5 reste attachée au numéro 25, et la valeur 10 au numéro 20. La commande insère une nouvelle fiche ; elle n'autorise pas de réétiqueter une ancienne pour obtenir une silhouette favorable.
Retirer la racine demande une réunion de ses deux côtés
Une autre branche repart de l'arbre initial à quatre fiches, avant l'insertion de 25. Nora retire 20. Il reste une branche gauche contenant 10 et une branche droite contenant 40 avec 30 à gauche. Leurs numéros sont tous séparés :10 précède chaque numéro de l'autre branche.
Camille choisit la tête de plus petite priorité entre 10, priorité 40, et 40, priorité 20. Quarante doit donc devenir la nouvelle racine. Elle conserve son côté droit vide, mais ne peut simplement installer 10 comme seul enfant gauche en oubliant 30. Il faut réunir 10 avec l'ancienne branche gauche de 40, qui contient 30. Dans cette réunion plus petite,30 de priorité 30 gagne contre 10 de priorité 40. Trente prend 10 à gauche et reste lui-même à gauche de 40. L'arbre remis possède donc 40, puis 30 à gauche, puis 10 à gauche de 30. Chaque ancienne fiche conservée se retrouve une seule fois, avec sa priorité initiale, et aucune fiche 20 invisible n'est utilisée pour guider les recherches suivantes.
Une recherche de 10 traverse désormais 40,30 puis 10, alors qu'elle traversait 20 puis 10 avant le retrait. Une recherche de 30 traverse 40 puis 30 ;40 est reconnu immédiatement. Ces chemins ne sont pas tous raccourcis par la disparition d'une fiche. Camille ne retire donc pas une comparaison à chaque ancienne recherche pour annoncer un nouveau coût. Pour 20, les comparaisons avec 40,30 puis 10 conduisent à la droite vide de 10 : le numéro supprimé est bien absent. Nora peut remettre l'arbre réduit et ces chemins précis, plutôt qu'une règle générale disant que retirer une racine rend chaque consultation plus rapide. La commande de retrait modifie réellement le point de départ et les suites qui restent accessibles.
La réunion conserve sa permission numérique à chaque étape. Si la tête gauche gagne, elle garde sa branche gauche et réunit sa branche droite avec l'autre arbre. Si la tête droite gagne, elle garde sa droite et réunit sa gauche avec le premier arbre. Dans le cas reçu,40 a gagné puis 30 a gagné ; cela a placé 10 à gauche de 30, lui-même à gauche de 40. Nora ne choisit pas le gagnant depuis son numéro :10 était plus petit, mais sa priorité 40 ne lui permettait pas d'être parent de 30 ou 40. Les comparaisons de priorité décident la forme de la réunion ; la séparation préalable des numéros garantit que cette forme demeure un index ordonné.
Découper retourne deux arbres, pas deux listes de fiches perdues
Nora revient à l'arbre contenant 25. Elle veut isoler les numéros au plus égaux à 22, sans retirer aucune fiche de la collection complète. Camille doit rendre deux arbres séparés : un pour la plage inférieure, l'autre pour les numéros plus grands.
La racine 25 dépasse 22. Elle appartiendra donc au second arbre, avec toute sa branche droite 40 et 30. Camille descend dans sa branche gauche 20. Vingt est au plus égal à 22 : il appartient au premier arbre et garde 10 à gauche. Sa droite est vide, donc aucun numéro supplémentaire ne doit être transféré. Camille rend 20 avec 10 comme premier arbre, puis 25 avec 40 et 30 comme second. Elle enlève bien le lien qui plaçait 20 sous 25 dans le dessin complet. Sinon, la seconde pièce contiendrait encore une partie de la première et une recherche dans celle-ci pourrait traverser une fiche déclarée hors de sa plage. Le découpage change les liens des pièces, sans modifier leurs numéros ou leurs priorités.
Une coupure au plus égale à 25 donnerait une autre remise. Vingt-cinq conserverait 20 et 10 dans le premier arbre ;40 avec 30 formerait le second. Camille garde le sens large de la borne pour décider de quel côté reste 25. Pour réunir ces deux pièces, elle compare leurs têtes de priorités 5 et 20 :25 reprend la racine et la réunion de sa droite vide avec 40 rétablit l'ancienne droite. Elle retrouve exactement l'arbre précédant la coupure. Cette restauration vérifie les attaches, pas seulement la liste ordonnée des cinq numéros. Revenir à un dessin valide quelconque ne suffirait pas à prouver que toutes les fiches et leurs priorités avaient été conservées pendant la séparation.
La procédure de coupure ne traite qu'un côté à chaque fiche rencontrée. Sous une tête dont le numéro est au plus égal à la borne, tout le côté gauche est déjà du bon côté ; seule la droite demande un partage supplémentaire. Sous une tête trop grande, toute la droite est conservée du côté supérieur, et seule la gauche est partagée. Les pièces remontées par la récursion reprennent ensuite leur place sous cette tête. Dans la coupure 22, cela a laissé 10 sous 20 et 30 sous 40 sans leur appliquer une seconde décision inutile. Nora contrôle cette conservation des sous-arbres complets ; elle ne promet pas un nombre constant de fiches visitées pour toute forme d'arbre.
Extraire une plage doit garder les trois morceaux
La commande devient 20≤numéro≤30. Camille coupe d'abord avant 20, puis après 30. Comme les numéros sont entiers dans cette fiche, elle utilise les bornes larges 19 et 30. Le milieu doit rester conservé, tandis que les deux morceaux extérieurs peuvent être réunis pour une autre consultation.
Après la première coupure,10 est isolé dans le morceau inférieur. Le reste possède 25 en racine,20 à gauche,40 à droite avec 30 à gauche. La seconde coupure conserve 25,20 et 30 au milieu ;40 reste dans le morceau supérieur. Camille rend donc trois pièces dont les numéros sont respectivement 10 ;20,25,30 ;40. Dans la pièce centrale,25 garde 20 à gauche et 30 à droite. Elle a retiré 40 de ce milieu sans perdre la fiche 30 qui se trouvait auparavant sous lui. Nora peut consulter 30 dans le milieu par 25 puis 30, ou constater que 40 n'y figure plus. L'extraction porte sur les numéros de la plage, pas sur toutes les fiches situées sous la même racine dans l'ancien dessin.
Camille réunit 10 et 40 pour former un index extérieur. Les priorités choisissent 40 comme racine avec 10 à gauche. Cet arbre ne suffit pourtant pas à restaurer le milieu par une réunion aveugle avec sa racine 25. Les numéros extérieurs ne sont pas tous plus petits que ceux du milieu :40 dépasse 20,25 et 30. Si elle applique la réunion ordonnée comme si l'extérieur était la première plage,25 de priorité 5 gagne, mais le côté contenant 40 peut se retrouver sous 20 à gauche de 25. Une recherche de 40 partirait au contraire à droite de 25 et ne le retrouverait pas là. La règle de priorité peut être satisfaite tandis que la recherche numérique est devenue fausse.
Nora conserve donc les limites des trois morceaux, même si elle a produit temporairement une consultation de l'extérieur. Pour restaurer la collection, elle réunit d'abord 10 avec le milieu 20,25,30, puis ce résultat avec 40. Chaque réunion respecte cette fois la séparation de tous les numéros entre ses deux entrées. Les attaches redeviennent celles de l'arbre à racine 25, gauche 20 avec 10, droite 40 avec 30. Camille garde également le milieu comme résultat d'extraction si la commande demandait de le remettre seul, plutôt que déclarer sa disparition nécessaire à la restauration. Les deux emplois sont distingués dans la préparation ; ils n'autorisent pas de compter une même fiche simultanément dans deux collections actives qui partageraient leurs liens.
Un tirage de priorités donne un coût moyen, pas un plafond équilibré
Pour une expérience mathématique séparée, les quatre numéros 10,20,30 et 40 sont fixés avant le tirage. Leurs priorités sont ensuite une permutation uniforme de 1,2,3 et 4. Les vingt-quatre permutations sont toutes autorisées. Une recherche présente compte chaque comparaison avec un numéro, y compris celle qui reconnaît la fiche.
Pour la recherche de 10, la fiche 20 est ancêtre exactement si elle possède la plus petite priorité parmi 10 et 20 : cela arrive dans la moitié des permutations. Trente est ancêtre de 10 si sa priorité est la plus petite parmi 10,20,30, soit dans un tiers des permutations. Quarante l'est dans un quart. En ajoutant la comparaison avec 10 lui-même, Camille obtient un coût moyen 1+1/2+1/3+1/4, soit 25/12. Elle n'ajoute pas une fois chaque fiche de l'index pour toutes les recherches. Les événements d'ancêtre ne sont pas supposés indépendants ; additionner leurs indicatrices pour le nombre de comparaisons suffit à obtenir leur moyenne.
Pour la recherche de 20, l'ancêtre 10 compte avec probabilité 1/2,30 avec 1/2 et 40 avec 1/3. Le coût moyen est donc 1+1/2+1/2+1/3=7/3. Par la symétrie de l'ordre des quatre clés, les recherches de 30 et 40 ont les moyennes 7/3 et 25/12. Nora peut refaire le compte en construisant l'arbre de chacune des vingt-quatre permutations : les totaux par numéro sont 50,56,56 et 50 comparaisons. Leur somme 212 correspond au total moyen 53/6 pour une recherche de chacun des quatre noms. Si le numéro demandé est lui aussi uniforme et indépendant, le coût moyen d'une seule recherche vaut 53/24. Cette dernière moyenne demande une règle de requête supplémentaire ; elle ne décrit pas toutes les consultations possibles.
Le tirage qui donne les priorités 1,2,3,4 aux numéros croissants produit une chaîne vers la droite. Pour rechercher 40, Camille compare 10,20,30 puis 40, quatre comparaisons. Ce tirage existe parmi les vingt-quatre, donc une promesse de trois comparaisons au plus serait fausse sous le seul tirage uniforme. Nora conserve la moyenne 53/24 avec cette réalisation défavorable. Elle peut préférer un dessin fixe où 20 est premier,10 à gauche,30 à droite puis 40 sous 30 : les quatre recherches y coûtent 2,1,2 et 3, total 8, moyenne 2. Mais choisir explicitement cette forme n'est pas la même procédure que tirer uniformément les priorités et accepter la forme obtenue.
La moyenne ne se transporte pas à un autre protocole qui attend les priorités avant de fixer les numéros. Nora reçoit alors quatre fiches encore sans numéro, tire leurs quatre priorités, puis attribue 10 à la plus petite,20 à la suivante,30 à la troisième et 40 à la plus grande. Quelle que soit la permutation reçue sur les fiches, les priorités croissent maintenant avec les clés. L'arbre remis est toujours la chaîne 10,20,30,40. Les recherches uniformes coûtent en moyenne(1+2+3+4)/4=5/2, et 40 demande toujours quatre comparaisons. Les priorités ont bien été tirées, mais elles n'étaient plus indépendantes de l'ordre numérique finalement assigné. Camille conserve ce second protocole comme autre commande, sans lui appliquer la moyenne calculée pour des clés déjà fixées.
Ce que Nora conserve après les changements
Les insertions, retraits et coupures gardent les numéros et priorités de chaque fiche dans les pièces remises. L'insertion de 25 a changé la racine par trois rotations ; le retrait de 20 a réuni ses deux côtés ; l'extraction 20 à 30 a conservé trois morceaux pour permettre une restauration ordonnée. Les coûts tirés au hasard restent attachés aux numéros fixés avant ce tirage. La fiche ne transforme aucune de ces constructions en vitesse observée de consultation.
Les notices ne fournissent aucun arbre ni procédé de recherche.