Enoncé 31. Arbres  Corrigé 31

Problème : Arbre binaires enfilés

Définitions : Un arbre de recherche binaire (arb) est un arbre tel que :

1. tous les noeuds du sous arbre gauche d'un noeud avec l'information x ont des valeurs strictement inférieures à x.

2. tous les noeuds du sous arbre droit d'un noeud avec l'information x ont des valeurs strictement supérieures à x.

Il est en plus dit enfilé à droite (arbfd) si tout noeud au lieu de contenir un pointeur Nil dans son champ droit, il contient un pointeur vers son successeur inordre( T1 N T2).

Le modèle sur ces sortes d'arbres est celui sur les arbres binaire augmenté des deux opérations suivantes :

Enfilé(n) : fonction booléenne égale à Vrai si le pointeur droit indique un enfilement, Faux sinon.

Aff-enfilé(n, v) : Rendre le noeud n enfilé ou pas selon la valeur logique de v.

Construction : Donner l'arbfd(en mettant en relief les enfilements) obtenu après l'insertion, dans cet ordre, des données suivantes : 55, 45, 65, 35, 40, 60, 62, 63, 25, 33.

Donner l'algorithme qui construit un arbfd à partir d'une suite de M nombres.

Suivant : Ecrire le module Suivant(S) qui fournit l'adresse du noeud qui suit S en inordre dans un arbfd de racine R.( S étant une adresse de noeud). Nil sinon.

Pluspetitx : Ecrire la fonction Pluspetitx(V) qui recherche le noeud dans l'arbre avec la plus petite valeur X telle que X >= V, V donnée. Nil sinon.

Requête a intervalle : Utiliser Suivant et Pluspetit pour écrire le module Requête(a, b) qui fournit l'ensemble des données x d'un arbfd de racine R telles que a <= x <= b , a et b données et pouvant ne pas appartenir à l'arbre.

Précédent : On veut avoir en plus l'opération Précédent (qui donne le noeud de valeur immédiatement inférieure) conçue de manière analogue à la fonction Suivant, c'est à dire avec l'idée d'enfilement). Que faut-il rajouter au niveau du noeud? Justifier. Donner l'arbre correspondant à l'exemple considéré.