Nora prépare un petit index pour un livre privé fictif. Il contient quatre noms ordonnés, A, B, C et D. Camille souhaite les retrouver par comparaisons successives avec des noms placés sur une fiche en arbre. Les recherches et leurs nombres de répétitions sont entièrement donnés pour l'exercice, sans lecteur observé ni temps de consultation mesuré. Nora cherchera d'abord le plus petit total de comparaisons pour les noms présents, puis ajoutera des recherches qui doivent conclure à une absence.
Une notice du Met classe une œuvre parmi les estampes.
Une autre notice du Met classe une œuvre parmi les estampes.
Une troisième notice du Met classe une œuvre parmi les estampes.
Ces notices ont été lues pour leurs catégories. Aucun sujet ou procédé artistique n'est repris ; les noms, arbres et recherches sont créés ici.
Nous employons des arbres de recherche ordonnés classiques, sans invention revendiquée. Comparer un nom demandé au nom d'une fiche donne trois issues : plus petit, égal ou plus grand. L'égalité termine la recherche ; les deux autres issues suivent respectivement la branche gauche ou droite. Chaque nom figure une seule fois. Tous les noms d'une branche gauche doivent précéder celui de la fiche qui la porte ; tous ceux d'une branche droite doivent le suivre. Une comparaison compte une opération dans notre convention, quelle que soit son issue.
Un nom souvent demandé n'est pas toujours le meilleur premier choix
Camille reçoit treize recherches : quatre demandent A, deux B, trois C et quatre D. Elle propose de commencer par A, qui partage avec D la plus grande fréquence. Pour les demandes plus grandes que A, elle poursuit sur C ; B est à gauche de C, D à droite. A demande alors une comparaison, C deux, B et D trois. Le total vaut quatre pour A, six pour B, six pour C et douze pour D, soit vingt-huit. La construction respecte l'ordre et retrouve les quatre noms, mais Nora n'a pas encore reçu de preuve que ce premier choix minimise le total.
Nora essaie C en premier. Une demande plus petite passe à A ; si elle est plus grande que A, elle rejoint B. Une demande plus grande que C rejoint directement D. Les profondeurs, en comptant la première comparaison, sont deux pour A, trois pour B, une pour C et deux pour D. Le total devient huit, six, trois et huit, soit vingt-cinq. Camille choisit cette candidate plutôt que sa première feuille à vingt-huit. Le nom C est demandé trois fois, moins que A et D ; la décision tient compte des conséquences de sa position pour toutes les recherches, pas seulement de son propre poids.
Une demande de B traverse concrètement C, A puis B dans cette feuille. La première comparaison constate B plus petit que C ; la seconde B plus grand que A ; la troisième reconnaît l'égalité. Une demande de D compare seulement C puis D. Nora conserve ces chemins auprès du total. Elle ne divise pas vingt-cinq par treize pour annoncer que toutes les demandes prendraient la même durée ou le même nombre de comparaisons. B reste à trois comparaisons et C à une ; le total additionne les treize recherches effectivement posées.
Choisir les branches depuis des intervalles conserve l'ordre
Pour certifier le meilleur arbre, Nora examine d'abord les petites branches possibles. Avec A et B seulement, de poids quatre et deux, placer A en premier donne quatre plus deux fois deux, soit huit. Placer B en premier donnerait deux plus deux fois quatre, soit dix. La meilleure branche de ces deux noms commence donc par A. Pour B et C, de poids deux et trois, commencer par C donne trois plus quatre, soit sept ; commencer par B donnerait deux plus six, soit huit. Pour C et D, commencer par D donne quatre plus six, soit dix, au lieu de trois plus huit, soit onze.
Ces comptes sont relatifs au premier niveau de chaque petite branche. Lorsqu'une branche de A et B est placée sous C, chacune de ses six recherches a déjà comparé C avant de commencer cette branche. Ses huit comparaisons propres deviennent donc quatorze dans l'arbre entier. Nora ne place pas huit directement dans le total en oubliant ce passage commun. À côté, les quatre demandes de D passent également par C et demandent chacune encore une comparaison. Camille peut ainsi recomposer vingt-cinq : treize premières comparaisons sur C, huit dans la branche A–B, puis quatre sur D.
La branche de trois noms A, B et C possède un poids total de neuf. Si elle commence par A, ses neuf premières comparaisons sont suivies du meilleur arbre B–C, coût sept : total seize. Si elle commence par B, elles sont suivies de A, coût quatre, et de C, coût trois : encore seize. Si elle commence par C, elles sont suivies de la branche A–B de coût huit : total dix-sept. Nora conserve donc deux réalisations minimales de coût seize pour ce même intervalle, l'une avec A en premier, l'autre avec B. Elle ne choisit pas entre elles avant de connaître l'emploi de cette branche dans le livrable.
Pour B, C et D, les poids totalisent également neuf. Les premiers choix B, C et D donnent respectivement neuf plus dix, neuf plus deux plus quatre, et neuf plus sept : dix-neuf, quinze et seize. La meilleure branche commence cette fois par C, avec B à gauche et D à droite. Les deux intervalles de poids neuf n'ont donc pas reçu la même décision. Camille garde les noms de chaque intervalle auprès du coût, plutôt qu'un seul résultat pour toutes les branches comportant trois noms et totalisant neuf recherches.
Nora peut maintenant examiner chacun des quatre premiers choix sur l'ensemble. Toutes les treize recherches consomment une première comparaison. Avec A en premier, la meilleure suite B–C–D coûte quinze, d'où vingt-huit. Avec B, la branche gauche A coûte quatre et la droite C–D dix, d'où vingt-sept. Avec C, la gauche A–B coûte huit et D quatre, d'où vingt-cinq. Avec D, la branche A–B–C coûte seize, d'où vingt-neuf. Le minimum est vingt-cinq, avec C en premier. Les branches déjà remplies donnent une réalisation de ce minimum, tandis que les quatre décompositions excluent un arbre moins coûteux.
Cette recherche couvre les arbres ordonnés parce que le premier nom choisi impose les noms de chaque côté. Tout ce qui précède C doit rester dans sa branche gauche, tout ce qui le suit dans sa branche droite ; les branches ne peuvent ensuite échanger un nom pour alléger librement leur poids. Nora applique le même partage à chaque intervalle restant. Pour quatre noms, quatorze formes d'arbres ordonnés sont possibles ; leur énumération séparée retrouve vingt-cinq. Camille conserve cependant le calcul par intervalles comme certificat lisible, sans donner quatorze arbres dessinés au lecteur pour qu'il devine lequel a été choisi.
Une rotation change les profondeurs sans changer l'ordre des noms
Camille veut placer A en premier sans renommer les fiches. Elle transforme l'arbre choisi en faisant remonter A au-dessus de C. C devient la branche droite de A ; B, qui se trouvait à droite de A, rejoint maintenant la gauche de C ; D demeure à droite de C. La lecture ordonnée des noms reste A, B, C, D. Une demande de B compare A, puis C, puis B ; le déplacement de B a conservé sa place entre A et C. Nora accepte cette nouvelle forme comme un arbre de recherche valide, avant de comparer son coût à celui de la forme initiale.
Dans cette rotation, A passe de profondeur deux à un, C de un à deux, D de deux à trois et B reste à trois. Les changements pondérés valent moins quatre pour A, plus trois pour C, plus quatre pour D et zéro pour B. Le total augmente donc de trois, passant de vingt-cinq à vingt-huit. Camille ne déplace pas seulement les deux noms A et C en gardant toutes les autres branches à leur ancienne place. D subit aussi la profondeur nouvelle de C ; B doit changer de branche pour conserver l'ordre. La comparaison porte sur la rotation entière effectivement construite.
Nora essaie volontairement une autre opération qui échange seulement les noms A et D dans l'ancien arbre, sans changer ses branches. La fiche située à gauche de C porte alors D. Une recherche de D compare d'abord C, constate que D est plus grand et part à droite, où elle rencontre A. La branche vide qui suit ne contient pas D. Le nom demandé demeure présent quelque part dans le dessin, mais la règle des comparaisons ne conduit plus à lui. Nora retire cette opération de ses choix autorisés. Dans l'index ordonné, une permutation de noms ne se juge donc pas seulement à leurs profondeurs pondérées.
Une recherche absente doit atteindre une branche vide
Nora ajoute une nouvelle série à la commande. Les treize recherches de noms présents demeurent quatre, deux, trois et quatre ; dix autres demandent un nom strictement supérieur à D. Ce nom n'est pas introduit dans l'index : les dix recherches doivent annoncer absent. Camille compte encore seulement les comparaisons avec un nom existant. Rencontrer une branche vide termine la recherche sans comparaison de nom supplémentaire. La branche vide n'est ni une cinquième fiche ni une égalité avec D.
Dans l'arbre commençant par C, chacune de ces dix demandes compare C, puis D, et atteint la branche vide située à droite de D. Elle consomme deux comparaisons. Le total des recherches présentes reste vingt-cinq ; les dix absences ajoutent vingt, d'où quarante-cinq. Nora retire donc vingt-cinq de la rubrique « toutes les recherches », sans modifier les anciens comptes des noms présents. La nouvelle commande a ajouté des consultations remplies, qui contribuent au critère même si elles ne retrouvent aucune fiche à remettre.
Camille donne alors D comme premier nom, avec B dans sa branche gauche ; A est à gauche de B et C à droite. Les profondeurs des noms présents sont trois pour A, deux pour B, trois pour C et une pour D. Leur total vaut douze, quatre, neuf et quatre, soit vingt-neuf. Il dépasse les vingt-cinq de la précédente feuille. Mais chaque recherche au-dessus de D s'arrête désormais après sa seule comparaison avec D : elle rejoint immédiatement la branche vide de droite. Les dix absences ajoutent dix, et le total devient trente-neuf. Nora choisit ce nouvel arbre pour l'ensemble des vingt-trois recherches.
Pour vérifier que trente-neuf est minimal, Camille reprend le partage par intervalles en incluant les recherches absentes dans le poids de la branche qu'elles empruntent. Quand une branche non vide reçoit une recherche, sa première comparaison coûte un, qu'elle finisse ensuite par une égalité ou une absence. Pour chacune des quatre racines possibles, les meilleurs totaux deviennent quarante-neuf avec A, quarante-sept avec B, quarante-cinq avec C et trente-neuf avec D. L'énumération des quatorze arbres confirme ces bornes. Nora ne retient donc pas D seulement parce qu'il semble proche de la branche vide recherchée : elle possède un choix construit et une exclusion de tous les premiers choix concurrents.
Le nouveau minimum avec A en premier montre pourquoi une ancienne branche ne pouvait pas être recopiée sans contrôle. La forme à vingt-huit donnait trois comparaisons aux absences au-dessus de D, donc cinquante-huit au total. Une autre forme commence par A, puis D dans sa branche droite, avec C sous D et B sous C. Les noms présents y coûtent vingt-neuf ; les absences n'y comparent que A et D, donc ajoutent vingt. Elle atteint quarante-neuf, meilleur que cinquante-huit tout en gardant A comme premier nom. Les recherches ajoutées ont aussi changé le meilleur arbre à l'intérieur d'une racine imposée.
Deux minima de même coût peuvent avoir des recherches plus longues différentes
Le premier choix D admet deux branches gauches minimales sur A, B et C. Dans l'une, A vient en premier dans cette branche, C à sa droite, puis B à gauche de C. Dans l'autre, B vient en premier, avec A à gauche et C à droite. Chacune avait un coût relatif seize pour les neuf recherches de ces trois noms. Sous D, leur première comparaison commune ajoute neuf ; les quatre recherches de D ajoutent quatre, et les dix absences dix. Les deux arbres atteignent donc trente-neuf. Nora conserve cette égalité plutôt que déclarer unique une forme choisie simplement parce qu'elle l'a dessinée d'abord.
Camille remplit une recherche de B dans chacune. Avec la branche gauche commençant par A, elle compare D, A, C puis B : quatre comparaisons. Avec celle commençant par B, elle compare D puis B : deux. A demande en revanche deux comparaisons dans la première forme et trois dans la seconde. Les poids quatre pour A et deux pour B compensent exactement ces changements dans le total ; C reste à trois et D à une. Nora peut donc expliquer l'égalité trente-neuf tout en montrant des chemins individuels différents, réellement compatibles avec les mêmes noms et les mêmes répétitions.
Nora ajoute alors une limite de trois comparaisons pour chaque nom présent, sans abandonner le minimum total. La première branche gauche échoue sur B, à quatre. La seconde donne trois pour A, deux pour B, trois pour C et une pour D ; elle satisfait la limite et conserve trente-neuf. Nora choisit cette deuxième réalisation et retire la première de la remise active. Il ne s'agit pas d'abaisser une moyenne par arrondi : aucun total n'a changé. Une contrainte portant sur chaque recherche a sélectionné une forme parmi deux minima déjà remplis.
Une absence indique un intervalle, pas un nom nouveau
Camille vérifie enfin les cinq issues d'absence dans cet arbre choisi : avant A, entre A et B, entre B et C, entre C et D, puis après D. Dans les quatre premières, la recherche compare D puis B, avant de comparer A ou C selon son côté. Une demande entre A et B va à gauche de B, compare A, puis rejoint sa branche droite vide. Une demande entre B et C va à droite de B, compare C, puis rejoint sa branche gauche vide. Les deux se terminent après trois comparaisons, mais elles n'ont pas identifié le même intervalle d'absence.
Pour une demande après D, la seule comparaison avec D suffit à rejoindre la branche droite vide. Nora ne lui remet pas D comme résultat au motif qu'il était le dernier nom effectivement comparé. L'égalité n'a jamais été constatée. Elle remet absent avec l'intervalle après D, et conserve la recherche entre A et B avec son autre intervalle. Les dix demandes absentes de la commande chiffrée appartenaient toutes au premier de ces cas, après D ; aucun poids imaginaire n'a été ajouté aux quatre autres intervalles pendant le choix à trente-neuf. Leur contrôle ferme les destinations possibles de la procédure, sans modifier rétroactivement la série qui a déterminé son optimum.
La première feuille conserve C comme premier nom et vingt-cinq comparaisons pour les treize recherches présentes. La seconde conserve D, puis la branche gauche B avec A et C, et trente-neuf comparaisons pour ces treize recherches plus dix absences au-dessus de D. Nora garde les noms, leur ordre, les répétitions et les chemins qui produisent chaque compte. Les arbres sont des constructions de la page privée fictive, sans essai de consultation auprès de proches ni promesse de durée réelle. La décision remise peut cependant être refaite avec les comparaisons qui l'ont effectivement choisie.
Les Éditions privées donnent une forme aux voix, aux archives et aux histoires que vous souhaitez transmettre.
Découvrir Codex de Maison →