Nora prépare une rangée de fiches fictives pour le service. Chacune porte une valeur entière créée pour la feuille. Camille doit remettre la position de la plus petite valeur dans une portion demandée, sans déplacer les fiches. Aucun rangement matériel ni temps de recherche réel n'est mesuré. Elles vont conserver deux ordres différents : les positions de la rangée et les valeurs qui décident des premières fiches d'un arbre.
Durham Manufacturing présente des catégories de rangement.
raaco présente des catégories de rangement.
Akro-Mils présente des catégories de rangement.
Ces catégories seules ont été lues. Aucun objet, image, agencement ou procédé réel ne fournit les arbres et les calculs de cette feuille.
La rangée porte sept valeurs, aux positions zéro à six : sept, trois, cinq, deux, six, quatre, huit. La demande sur une portion conserve ses deux extrémités incluses. Une position fait partie du résultat : remettre seulement deux ne dit pas encore où Camille devra prendre la fiche. Nous employons un arbre cartésien classique de minimum, sans invention revendiquée. Les valeurs sont ici distinctes ; les égalités recevront ensuite une règle séparée.
Partager la rangée depuis son minimum ne la trie pas
Nora place la position trois, de valeur deux, à la racine. Les positions zéro, un, deux doivent rester dans la branche gauche ; quatre, cinq, six dans la droite. Dans la première branche, le minimum est trois à la position un : zéro devient son enfant gauche et deux son enfant droit. Dans la seconde, quatre à la position cinq prend le rôle de racine locale : quatre devient son enfant gauche, six son enfant droit. Camille conserve les sept positions dans cette disposition, sans copier la fiche trois dans chacune des deux branches qu'elle vient de séparer.
La lecture gauche, fiche, droite de cet arbre redonne les positions zéro, un, deux, trois, quatre, cinq, six. Les valeurs lues ainsi restent sept, trois, cinq, deux, six, quatre, huit. Nora refuse donc d'étiqueter les branches « petites valeurs » et « grandes valeurs ». La branche droite de la racine porte quatre, six et huit, mais la gauche porte également des valeurs plus grandes que deux. Les côtés désignent des positions dans la rangée. La règle sur les valeurs est verticale : chaque fiche porte une valeur inférieure à celles de ses descendants, et non une séparation numérique entre ses deux côtés.
Camille essaie à tort de trier les fiches avant de construire ce dessin. Elle obtiendrait deux, trois, quatre, cinq, six, sept, huit, qui donne une chaîne de minima successifs. La portion demandée des positions deux à quatre ne représenterait plus cinq, deux, six, mais quatre, cinq, six. Son résultat deviendrait quatre au lieu de deux. Nora retire cette préparation. La construction doit comparer les valeurs en gardant leurs anciennes positions ; l'ordre numérique ne peut remplacer l'ordre d'arrivée avant une question qui porte précisément sur cet ordre d'arrivée.
Le premier ancêtre commun donne un minimum de portion
Camille demande les positions deux à quatre. Pour remonter depuis deux, elle rencontre un puis trois ; depuis quatre, elle rencontre cinq puis trois. La première fiche commune aux deux remontées, en partant des extrémités, est trois. Sa valeur deux est effectivement le minimum de cinq, deux, six. Nora remet la position trois avec cette valeur. Les deux extrémités ne sont pas sœurs et le résultat n'était ni l'une ni l'autre : leurs chemins se rejoignent au niveau qui contient la portion entière, sans exiger de lire les trois valeurs dans l'ordre sur une nouvelle bande.
Pour la portion quatre à six, les deux chemins rencontrent immédiatement cinq comme ancêtre commun le plus profond. Nora remet quatre à la position cinq. La racine globale trois, de valeur deux, était aussi un ancêtre commun de ces deux fiches ; elle ne convient pourtant pas, car sa position n'appartient pas à la portion quatre à six. Camille conserve donc le mot « premier » dans la remontée. Une fiche commune quelconque aurait fourni un minimum d'un ensemble plus large. La profondeur de l'ancêtre retenu ferme ici la portée de la réponse, plutôt que de chercher la plus petite valeur de tout l'arbre.
Pour comprendre cette appartenance, Nora prend les extrémités i et j avec i inférieur à j. Si leur premier ancêtre commun n'est aucune des deux, elles se trouvent dans ses branches opposées. Sa position se place alors entre i et j, puisque la lecture de gauche précède sa position et celle de droite la suit. Si l'ancêtre est l'une des extrémités, il appartient déjà à la portion. Tous les noms de cette portion sont contenus dans son sous-arbre, dont les positions forment un intervalle continu. La règle de minimum vertical donne donc une valeur au plus égale à chacune d'elles, à une position effectivement autorisée.
Une demande réduite à la position deux a aussi sa réponse. La fiche deux est son propre ancêtre commun et remet cinq. Camille ne commence pas obligatoirement par son parent un, qui porte trois mais se trouve hors de cette portion d'une seule fiche. Nora conserve les remontées comme des chemins comprenant leur point de départ. Cette convention permet de traiter ensemble une portion entière, une portion qui commence à sa racine locale et une portion réduite à une place. Il n'y a pas de fiche invisible de minimum placée entre la rangée et l'arbre.
Construire la droite conserve les sous-arbres déjà reçus
Nora souhaite maintenant former le même arbre en recevant les fiches dans leur ordre, plutôt qu'en recherchant chaque minimum depuis une copie entière. Elle conserve une pile des fiches situées sur la branche de droite, depuis la racine jusqu'à la dernière reçue. Les valeurs y croissent. Après la seule position zéro, la pile contient zéro, de valeur sept. Quand un arrive avec trois, zéro en sort et devient l'enfant gauche de un. La pile ne contient plus que un ; la fiche zéro demeure dans l'arbre. Camille distingue cette sortie de la pile de la suppression d'une fiche dans le dossier.
La position deux, de valeur cinq, ne fait sortir aucune fiche : trois est plus petit que cinq. Deux devient l'enfant droit de un, et la pile contient un puis deux. La position trois arrive ensuite avec deux. Elle fait sortir deux, puis un. La dernière sortie, un, devient son enfant gauche, avec ses deux enfants zéro et deux conservés. Trois devient la nouvelle racine. Nora refuse un dessin qui accrocherait seulement deux à gauche de trois et laisserait un séparé : c'est tout le sous-arbre reçu par un qui doit être déplacé, pas seulement la dernière fiche rencontrée au premier test.
À l'arrivée de quatre, de valeur six, la racine trois reste plus petite et prend quatre à droite. La pile porte trois puis quatre. Cinq arrive avec quatre : elle fait sortir quatre, mais pas trois. Cinq remplace donc quatre comme enfant droit de trois, et quatre devient son enfant gauche. Six, de valeur huit, se place enfin à droite de cinq. Nora retrouve exactement le dessin de la première construction. Dans l'étape de cinq, quatre n'a ni changé de valeur ni disparu : elle se trouve toujours après trois dans la lecture des positions, mais sous la nouvelle fiche qui a pris la tête de cette branche.
La dernière fiche sortie avait déjà toutes les sorties précédentes dans son sous-arbre. En la donnant comme enfant gauche à la nouvelle, Camille conserve donc ensemble les positions qu'elle vient de retirer de la pile. La fiche encore au sommet, s'il en reste une, est plus petite que la nouvelle et devient son parent à droite. Sans sommet restant, la nouvelle peut devenir racine. Ces deux attaches préservent l'ordre des positions et la règle verticale des valeurs. Nora garde ces invariants auprès des gestes remplis de trois et cinq ; la croissance de la pile seule n'aurait pas attesté que les sous-arbres étaient encore reliés correctement.
Chaque fiche entre dans cette pile une seule fois, au moment de son arrivée. Une sortie est définitive pour cette pile : la fiche quitte la branche droite et ne sera pas réinsérée par la réception des suivantes. Sur sept fiches, Camille peut donc effectuer au plus sept entrées et sept sorties, même si la réception de trois a provoqué deux sorties successives. Cette borne concerne ces gestes de construction. Elle ne mesure pas la durée d'une consultation réelle, ni ne garantit que chaque question future sur deux positions remontera un nombre fixe de liens. Nora sépare le coût de préparation de celui de la lecture d'une portion.
Deux valeurs égales demandent un départage cohérent
Une branche distincte reçoit quatre, deux, deux, cinq, un, un aux positions zéro à cinq. Nora veut que chaque question remette la première position parmi les minima égaux. Elle compare donc les couples valeur, position : la valeur départage d'abord, la plus petite position ensuite. La racine devient quatre, premier un ; cinq, second un, reste dans sa branche droite. Dans la branche gauche, un, premier deux, précède deux, second deux, dans la hiérarchie. Camille construit ainsi un arbre déterminé sans prétendre que deux valeurs numériquement égales sont devenues différentes sur la fiche.
À l'arrivée de la position deux, sa valeur deux ne doit pas faire sortir la position un, également de valeur deux. La position précédente gagne le départage. Deux devient donc enfant droit de un ; cinq à la position trois se place encore à droite de deux. La réception de quatre, valeur un, retire ces fiches de la pile et garde un comme tête du sous-arbre gauche. La réception de cinq, autre un, conserve quatre en racine. Nora utilise partout la comparaison des mêmes couples. Une pile qui supprimerait aussi les égalités donnerait au contraire la priorité à la dernière position reçue.
Sur la portion un à deux, la remise doit être la position un. Sur quatre à cinq, elle doit être quatre. Les deux conventions, première ou dernière position minimale, remettraient dans chaque cas la même valeur, deux ou un ; cela ne permet pas de les confondre. Camille inscrit également la position retournée et contrôle la fiche effectivement prise. Si Nora demandait désormais la dernière place minimale, elle devrait changer le départage dans la construction et dans les comparaisons des réponses. Garder l'ancien arbre puis remplacer seulement le mot « première » dans la légende ne donnerait pas les chemins nécessaires à cette autre sélection.
Deux fenêtres qui se recouvrent servent au minimum, pas à la somme
Nora revient à la rangée initiale et prépare une autre représentation des questions. Elle inscrit le minimum, avec sa position, dans chaque fenêtre de longueur un, deux puis quatre. Une fenêtre de quatre positions se partage en deux fenêtres de deux consécutives ; elle compare leurs deux couples pour garder le gagnant. Elle n'ajoute pas leurs valeurs. La position conservée demeure une position de la rangée complète. Camille peut donc comparer les résultats de cette table avec les ancêtres du dessin, même si les deux préparations ne conservent pas les mêmes liens ni les mêmes informations intermédiaires.
La portion un à cinq possède cinq positions. Camille prend la fenêtre de longueur quatre commençant à un et celle de longueur quatre finissant à cinq. La première contient trois, cinq, deux, six et remet deux à trois. La seconde contient cinq, deux, six, quatre et remet également deux à trois. Ensemble, elles couvrent la portion entière et se recouvrent sur deux, trois, quatre. Comparer les deux réponses donne encore deux à trois. Nora accepte cette double présence de la même fiche : elle ne multiplie pas sa valeur ni son rang, elle choisit seulement le plus petit couple parmi deux listes qui la contiennent.
Le recouvrement n'autorise pas la même opération pour une somme. Les deux fenêtres totalisent seize et dix-sept ; les additionner donnerait trente-trois. La portion demandée vaut seulement vingt. Les trois positions communes portent cinq, deux, six, total treize, exactement l'excès reçu. Nora refuse donc trente-trois et conserve vingt si la demande est une somme, qui doit utiliser des parts disjointes ou un autre compte corrigeant le recouvrement. L'opération de minimum accepte de comparer deux fois le même candidat ; l'addition compte réellement deux contributions. Ce choix de fenêtres n'est pas une permission générale de superposer des morceaux pour toutes les questions.
Pour une longueur L supérieure à zéro, Camille choisit la plus grande puissance de deux k au plus égale à L. Les fenêtres de longueur k placées au début et à la fin couvrent la portion : L est inférieur à deux k, donc aucun espace ne demeure entre elles. Chaque position demandée appartient à au moins l'une, et aucune position extérieure n'y entre. Comparer leurs minima suffit ainsi à la demande, quel que soit le recouvrement. Nora conserve cette justification de couverture avec la règle de comparaison, plutôt qu'un exemple de cinq positions qui aurait été extrapolé à des longueurs sans vérifier les fenêtres choisies.
Ajouter une fiche ne laisse pas toujours l'ancienne racine
Une nouvelle arrivée prolonge la rangée initiale par un, à la position sept. La pile finale trois, cinq, six porte deux, quatre, huit : les trois fiches en sortent devant un. La dernière, trois, devient l'enfant gauche de sept avec tout l'ancien arbre. Sept est désormais racine. Camille constate que les anciennes réponses sur zéro à six restent les mêmes, mais que toute question couvrant sept choisit cette nouvelle fiche. Nora conserve donc les anciens sous-arbres et remplace leur lien de sommet. Ajouter simplement sept comme enfant droit de six violerait la règle verticale, puisque huit aurait alors un descendant de valeur un.
Une autre branche prolonge au contraire l'ancienne rangée par neuf. Cette fois, la pile trois, cinq, six reste intacte et sept devient enfant droit de six. La racine globale demeure trois. Les deux branches commencent avec les mêmes sept fiches et la même position nouvelle ; elles diffèrent par sa valeur et donc par les attaches réellement autorisées. Nora ne cumule pas ces arrivées sur une seule feuille. Chacune possède son arbre complet et sa pile finale, qui permettent de contrôler pourquoi une arrivée change tout le sommet tandis que l'autre prolonge seulement l'extrémité droite.
L'ajout d'une fiche n'a pas modifié les valeurs des anciennes portions ; la question sur un à cinq remet encore deux à trois dans chacune de ces branches. Mais la table de fenêtres préparée pour sept positions n'a aucun résultat pour une fenêtre contenant la position sept. Camille doit compléter les entrées nécessaires avant d'utiliser cette table sur une question prolongée. Le maintien d'un ancien résultat ne prouve pas que toute la représentation est devenue valide pour la rangée agrandie. Nora remet les réponses anciennes sous leurs anciennes bornes et les réponses nouvelles seulement après mise à jour des liens ou des fenêtres qui les concernent.
Une correction intérieure change des liens sans changer l'ordre d'arrivée
Une dernière branche remplace seulement deux à la position trois par neuf dans la rangée initiale. Les positions restent zéro à six. Le minimum global devient trois à un, qui prend zéro à gauche. Sa branche droite, positions deux à six, possède quatre à cinq pour minimum ; deux, de valeur cinq, se trouve à sa gauche, avec quatre, de valeur six, à droite de deux et trois, de valeur neuf, à gauche de quatre. Six reste à droite de cinq. Camille a reconstruit les attaches depuis les valeurs corrigées, plutôt que de conserver trois comme racine en lui donnant seulement sa nouvelle étiquette neuf.
La portion deux à quatre contenait auparavant cinq, deux, six et remettait trois. Elle contient désormais cinq, neuf, six et remet deux, de valeur cinq. Sur l'ancien dessin, le premier ancêtre commun de ses extrémités serait encore trois, devenue neuf : ce résultat est faux. La portion zéro à deux conserve au contraire son minimum trois à un, puisqu'aucune de ses valeurs n'a changé. Nora garde cette réponse inchangée mais retire l'ancien chemin de la première question. Elle ne déduit pas de la stabilité d'une portion voisine que les attaches anciennes resteraient justes pour toutes les bornes.
La pile de réception décrivait l'arrivée de nouvelles positions à droite. Elle n'offre pas directement un geste de correction d'une fiche intérieure déjà retirée de cette pile. Camille choisit ici de reconstruire l'arbre complet depuis la rangée corrigée, avec les mêmes règles de positions et de minimum. Nora conserve ce choix explicite, sans lui attribuer la borne d'une seule arrivée ni annoncer une mise à jour locale de tous les liens. La correction de trois a changé la racine et plusieurs attaches ; cette réalisation montre ce qui doit être revérifié avant de remettre des questions, même quand une seule valeur a été remplacée.
La forme conserve les places gagnantes, mais pas leurs nombres
Nora crée enfin une rangée sept fois dix, trois fois dix, cinq fois dix, deux fois dix, six fois dix, quatre fois dix, huit fois dix. Toutes les comparaisons et tous les départages donnent le même arbre que la rangée initiale. Chaque portion possède donc la même position minimale. Pourtant, sur quatre à six, la valeur à remettre est quarante, alors que l'ancien dessin accompagnait cette position de quatre. Camille garde les valeurs sur leurs fiches si la commande demande aussi le nombre. La structure des liens seule conserve les gagnants des comparaisons ; elle n'a pas enregistré les magnitudes qui les rendaient gagnants.
Les catégories citées n'apportent aucune règle de minimum ou de construction à ces opérations sur positions.