Cet article explore une méthode de construction d'une structure arborescente basée sur la récursion, particulièrement adoptée pour optimiser la gestion des sous-arbres identiques. L'objectif est de construire un ordinateur virtuel représenté par un arbre binaire, où la répétition de sous-structures peut être efficacement gérée par le partage de nœuds.

Fonction calculerProfondeurMaximale

Cette fonction détermine la profondeur maximale nécessaire pour représenter un intervalle donné dans une structure d'arbre binaire complète. Elle est essentielle pour dimensionner correctement la structure et alllouer les ressources nécessaires.

void calculerProfondeurMaximale(int debut, int fin, int debutCible, int finCible) {
   int milieu = debut + (fin - debut) / 2;
   if (debut == debutCible && fin == finCible) {
       int profondeur = 0;
       int longueurIntervalle = fin - debut + 1;
       while (longueurIntervalle > 0) {
           profondeur++;
           longueurIntervalle >>= 1;
       }
       if (profondeur > profondeurMax) {
           profondeurMax = profondeur;
       }
       return;
   }
   if (finCible <= milieu) {
       calculerProfondeurMaximale(debut, milieu, debutCible, finCible);
   } else if (debutCible > milieu) {
       calculerProfondeurMaximale(milieu + 1, fin, debutCible, finCible);
   } else {
       calculerProfondeurMaximale(debut, milieu, debutCible, milieu);
       calculerProfondeurMaximale(milieu + 1, fin, milieu + 1, finCible);
   }
}
   

La complexité de cette fonction est de O(log R), où R représente la limite supérieure de l'intervalle.

Fonction construireStructure

Cette fonction procède à la construction de l'arbre binaire en identifiant et en partageant les sous-arbres récurrents. Elle utilise un mécanisme de chaînes de suffixes pour lier les nœuds communs.

void construireStructure(int noeudActuel, int debutIntervalle, int finIntervalle, int debutCible, int finCible, bool creerNouveauNoe, std::pair<int int=""> precedent) {
   int milieu = debutIntervalle + (finIntervalle - debutIntervalle) / 2;

   if (debutIntervalle == debutCible && finIntervalle == finCible) {
       int profondeurRequise = 0;
       int longueur = finIntervalle - debutIntervalle + 1;
       while (longueur > 0) {
           profondeurRequise++;
           longueur >>= 1;
       }
       relationsArbre[precedent.first].push_back({profondeurRequise, precedent.second});
       return;
   }

   if (creerNouveauNoe) {
       noeudActuel = ++compteurNoeuds;
   }
   if (creerNouveauNoe && precedent.first != 0) {
       relationsArbre[precedent.first].push_back({noeudActuel, precedent.second});
   }

   if (debutCible > milieu) {
       construireStructure(noeudActuel, milieu + 1, finIntervalle, debutCible, finCible, true, {noeudActuel, 1});
   } else if (finCible <= milieu) {
       construireStructure(noeudActuel, debutIntervalle, milieu, debutCible, finCible, creerNouveauNoe, {noeudActuel, 0});
   } else {
       construireStructure(noeudActuel, debutIntervalle, milieu, debutCible, milieu, creerNouveauNoe, {noeudActuel, 0});
       construireStructure(noeudActuel, milieu + 1, finIntervalle, milieu + 1, finCible, true, {noeudActuel, 1});
   }
}
   </int>

• noeudActuel: Identifiant du nœud courant.
• debutIntervalle, finIntervalle: L'intervalle numérique couvert par le nœud courant.
• debutCible, finCible: L'intervalle cible à représenter.
• creerNouveauNoe: Indicateur booléen pour décider si un nouveau nœud doit être créé.
• precedent: Une paire contenant l'identifiant du nœud précédent et le poids de l'arête le reliant.

La complexité de cette fonction est également de O(log R).

Fonction Princpiale

La fonction principale orchestre le processus. Elle commence par calculer la profondeur maximale requise, initialise les structures pour le partage de sous-arbres, puis appelle la fonction de construction. Enfin, elle affiche le nombre total de nœuds uniques et la structure de l'arbre résultant.

int main() {
   std::cin >> limiteInferieure >> limiteSuperieure;
   profondeurMax = 0;
   calculerProfondeurMaximale(0, (1 << 20) - 1, limiteInferieure, limiteSuperieure);

   compteurNoeuds = profondeurMax;
   for (int i = 2; i <= profondeurMax; ++i) {
       relationsArbre[i].push_back({i - 1, 0});
       relationsArbre[i].push_back({i - 1, 1});
   }
   compteurNoeuds++;
   construireStructure(compteurNoeuds, 0, (1 << 20) - 1, limiteInferieure, limiteSuperieure, false, {0, 0});

   std::cout << compteurNoeuds << '\n';
   for (int i = 1; i <= compteurNoeuds; ++i) {
       std::cout << relationsArbre[i].size() << ' ';
       for (const auto& arc : relationsArbre[i]) {
           std::cout << arc.first << ' ' << arc.second << ' ';
       }
       std::cout << '\n';
   }
   return 0;
}
   

La complexité totale du programme est de O(log R).