arbre de Stern-Brocot

Écrivez 0/1 à gauche et 1/0 à droite. Entre ces deux bornes, additionnez les nombres du haut, puis ceux du bas : vous obtenez 1/1. Recommencez dans chaque intervalle ainsi créé. Entre 1/1 et 1/0 apparaît par exemple 2/1.

Ces insertions forment l’arbre de Stern-Brocot. Chaque embranchement resserre deux fractions autour d’une fraction recherchée. En choisissant à chaque fois le côté qui la contient, on finit par atteindre toute fraction positive écrite sous forme irréductible, une seule fois.

L’arbre de Stern-Brocot est un arbre binaire infini qui organise les nombres rationnels strictement positifs sous la forme de fractions irréductibles. Sa construction part de deux bornes formelles, 0/1 et 1/0. La seconde sert de borne vers l’infini ; elle n’est pas elle-même un nombre rationnel positif.

Considérons deux fractions contiguës. Le nombre p désigne le numérateur de la fraction de gauche, q son dénominateur, p′ le numérateur de droite et q′ son dénominateur. On insère entre elles leur médiante : $\frac{p+p^{\mathrm{\prime }}}{q+q^{\mathrm{\prime }}}\backslash frac\{p+p\text{'}\}\{q+q\text{'}\}$. Cette règle additionne séparément les numérateurs et les dénominateurs ; elle ne calcule pas une moyenne arithmétique. Appliquée à toutes les paires contiguës nouvellement formées, elle engendre les niveaux successifs de l’arbre.

Dans cette construction, les fractions voisines vérifient $p^{\mathrm{\prime }}q-p{q}^{\mathrm{\prime }}=1p\text{'}q-pq\text{'}=1$. Cette relation garantit que leur médiante est irréductible. Chaque fraction rationnelle strictement positive apparaît alors exactement une fois. L’unicité concerne le nombre sous sa forme réduite : 10/6 ne crée donc pas un second nœud distinct de 5/3.

Cherchons la fraction irréductible 5/3 dans l’arbre. Les données sont la cible 5/3, la borne gauche initiale 0/1 et la borne droite initiale 1/0. À chaque étape, on calcule la médiante des bornes, puis on compare sa valeur à 5/3.

1. La première médiante vaut $\frac{0+1}{1+0}=\frac{1}{1}\backslash frac\{0+1\}\{1+0\}=\backslash frac11$. Comme 5/3 est supérieur à 1/1, la nouvelle borne gauche est 1/1.
2. La médiante de 1/1 et 1/0 vaut 2/1. Comme 5/3 est inférieur à 2/1, la nouvelle borne droite est 2/1.

3. La médiante de 1/1 et 2/1 vaut $\frac{1+2}{1+1}=\frac{3}{2}\backslash frac\{1+2\}\{1+1\}=\backslash frac32$. Comme 5/3 est supérieur à 3/2, la nouvelle borne gauche est 3/2.
4. La médiante de 3/2 et 2/1 vaut $\frac{3+2}{2+1}=\frac{5}{3}\backslash frac\{3+2\}\{2+1\}=\backslash frac53$ : la cible est atteinte.

Le contrôle est direct : 5 et 3 n’ont aucun diviseur commun supérieur à 1, et les dernières bornes vérifient 2 × 2 − 3 × 1 = 1. Le chemin obtenu est droite, gauche, droite depuis 1/1 ; chaque comparaison explique l’embranchement choisi.

Pour retrouver une fraction positive précise, on la compare à la médiante courante. Si elle est plus grande, on conserve l’intervalle droit ; si elle est plus petite, on conserve l’intervalle gauche. L’égalité arrête la recherche.

Pour énumérer des fractions sans doublon, on parcourt les niveaux de l’arbre. Cette organisation est préférable à une liste brute de couples numérateur-dénominateur lorsque le critère observable est l’absence de formes équivalentes comme 5/3 et 10/6.

Pour encadrer un rationnel pendant une recherche, on garde les deux fractions contiguës qui l’entourent. Leur médiante fournit le test suivant. Une comparaison décimale peut aider à lire le choix, mais les produits croisés évitent les erreurs d’arrondi.

Médiante et moyenne arithmétique. La médiante de 1/1 et 2/1 est 3/2, car on additionne séparément les numérateurs et les dénominateurs. Leur moyenne arithmétique vaut aussi 3/2 dans ce cas particulier, mais l’accord ne se généralise pas : pour 1/2 et 2/1, la médiante vaut 3/3, tandis que la moyenne vaut 5/4.

Arbre de Stern-Brocot et arbre de probabilités. Le premier classe des fractions positives irréductibles par médiantes. Un arbre de probabilités porte des probabilités sur des branches. La présence de fractions ne suffit donc pas : le test décisif est la règle qui engendre les nœuds.

La borne 1/0. Son dénominateur nul signale qu’elle sert de borne formelle au départ. Il ne faut ni la compter parmi les rationnels positifs ni lui appliquer les opérations ordinaires sur les fractions.

Une écriture non réduite. Chercher 10/6 comme un nouveau nœud conduit à un faux doublon. Il faut d’abord réduire la fraction en 5/3, qui est l’unique représentant présent dans l’arbre.

Deux fractions prises au hasard. La règle de la médiante ne suffit pas, à elle seule, à produire une fraction irréductible. Ainsi, 1/3 et 1/5 donnent 2/8, réductible en 1/4. Dans l’arbre, on l’applique à des voisines contiguës vérifiant $p^{\mathrm{\prime }}q-p{q}^{\mathrm{\prime }}=1p\text{'}q-pq\text{'}=1$.

Un arbre infini. Aucun niveau fini ne contient toutes les fractions positives. Une fraction donnée se trouve après un nombre fini de choix, mais l’énumération complète n’a pas de dernier niveau.

Fraction continue — Une autre écriture structurée des rationnels, utile pour prolonger l’étude des chemins et des approximations.

Les fractions continues, — Un développement éditorial consacré à cette autre manière d’organiser l’information portée par une fraction.

Le peuple des rationnels — Un prolongement sur l’ensemble auquel appartiennent toutes les fractions placées dans l’arbre.