multitudinous

Projet ALGAV Master STL @UPMC 2017-2018

Author : Kaan YAGCI - 3201099

1. Présentation

1.1 Structure 1 : Patricia - Tries

---

RAPPEL

Trie : Représentation arborescente d'un ensemble de clés en évitant de répeter les préfixes communs.

• prem(cle) : Renvoie la première caractère de la clé.
• reste(cle) : Renvoie la clé privée de son premier caractère
• car(e,i) : Renvoie la i-ème caractère de la clé
• lgueur(cle) : Renvoie le nombre de caractères de la clé.

---

Question 1.1

Dans le vrai vie, on dit qu'un mot est fini quand il ne reste plus de caractères. Pour cela je choisi le caractère numéro 0 parmi les 128 caractères ASCII pour indiquer la fin d'un mot. Ce caractère est le caractère NUL (https://fr.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange)

Question 1.2

Pour la réalisation de la structure Patricia-tries j'ai créé et utilisé les classes suivantes :

---

TODO :

• Insert file structure

---

• Noeud : La classe qui représente le structure du noeud. Elle contient un objet de type Noeud qui peut être undefined qui représente le noeud père s'il y en a un, une chaîne de caractères appelé cle qui représente la clé du noeud et une liste des objets de type Noeud qui représente les fils du noeud (les sous arbres dans le cas le noeud est la racine d'une arbre de recherche) et les primitives d'un structure noeud. (Dans le cas d'une feuille la liste des fils sont vide). Ces primitives sont les suivants :

  • constructor(cle,fils,pere) : La fonction permet d'identifier un objet Noeud. Il prend une chaîne de caractères cle qui représente la clé du noeud, une liste des objets de type Noeuds qui représente la liste des fils du noeud et un objet de type Noeud qui peut être undefined dans le cas du neoud est une racine qui représente le père du noeud.

     constructor(cle : string, fils : Array<Noeud>, pere? : Noeud) {
          this.cle = cle;
          this.fils = fils;
          this.pere = pere;
     }

  • getPere() : La fonction qui retourne le père du noeud et undefined si le noeud est le père d'un arbre. getPere() : void -> Noeud|undefined

     public getPere(): Noeud|undefined {
         return this.pere;
     }

  • getCle() : La fonction retourne la clé du noeud. getCle(): void -> string

     public getCle(): string {
         return this.cle;
     }

  • getFils() : La fonction retourn la liste des fils du noeud. getFils(): void -> Array<Noeud>

     public getFils(): Array<Noeud> {
          return this.fils;
     }

  • setPere(p) : La fonction permet de reinitialiser le père du noeud avec l'objet de type Noeud passé en paramètre. setPere(p): Noeud|undefined -> Noeud|undefined

     public setPere(p : Noeud|undefined): Noeud|undefined {
          return this.pere = p;
      }

  • setCle(c) : La fonction permet de reinitialiser la clé du noeud avec la clé passée en paramètres. setCle(c): string -> string

     public setCle(c : string): string {
          return this.cle = c;
     }

  • setFils(f) : La fonction permet de reinitialiser la liste des fils du noeud avec la nouvelle liste f passée en paramètres. setFils(f): Array<Noeud> -> Array<Noeud>

     public setFils(f : Array<Noeud>): Array<Noeud> {
          return this.fils = f;
     }

  • prem() : La fonction renvoie la première caractère de la clé du noeud. prem(): void -> string

     public prem(): string {
          return this.cle.split('')[0];
     }

  • reste() : La fonction renvoie la clé privée de son premier caractère.

     public reste(): string {
          return this.cle.slice(1);
     }

  • car(i) : La fonction renvoie la ième caractère de la clé. car(i): number -> string

     public car(i : number): string {
          return this.cle.split('')[i];
     }   

  • lgueur() : La fonction renvoie le nombre de caractères de la clé. lgueur(): void -> number

     public lgueur(): number {
          return this.cle.length;
     }

  • compare(n) : La fonction permet de comparer le noeud avec le noeud passé en paramètre. Elle compare la clé du noeud actuelle avec la clé du noeud passé en paramètres. compare(n): Noeud -> number

     public compare(n : Noeud): number {
          if (this.cle < n.getCle()) {
              return -1;
          }
          if (this.cle > n.getCle()) {
              return 1;
          }
          return 0;
     }

  • update() : La fonction permet de mettre à jour la liste des noeud fils du noeud. Elle trie la liste dans l'ordre l'alphabétique. update(): void -> Array<Noeud>

     public update(): Array<Noeud> {
          return this.fils = this.fils
                                 .sort(
                                          (a: Noeud, b: Noeud) => 
                                          a.compare(b)
                                       );
     } 

  • add(mot) : La fonction permet d'ajouter le mot passé en paramètres dans le noeud. add(mot): string -> boolean

     public add(mot : string) : boolean {
          /* La constante encommun contiens les caractères en commun au début du mot de la clé et le mot à insérer */
          const encommun = match2Strings(this.cle,mot);
          if (encommun.length > 0)
          {
              if (encommun === this.cle) {
                  /* Si la clé est un préfixe du mot à insérer  */
                  const reste = mot.slice(encommun.length);
                  if (reste.length === 0)
                  {
                      console.log('Le mot à ajouter est la même que la clé.');
                      if (this.fils.length > 0)
                      {
                          console.log("On check s'il contient la feuille indiquant la fin du mot");
                          for (var f of this.fils) {
                              if (f.getCle() === '\0') {
                                  console.log('Le mot ' + mot + 'existe déjà dans l\'arbre!!!');
                                  return false;
                              }
                          }
                      }
                      console.log("La feuille indiquant la fin du mot a été ajouté à la liste des fils");
                      this.fils.push(new Noeud('\0',new Array<Noeud>(),this));
                      return true;
                  }
                  for (var f of this.fils) {
                      if (match2Strings(f.getCle(),reste).length > 0) {
                          /* Si on trouve le noeud à insérer */
                          return f.add(reste);
                      }
                  }
                  /* Si on n'a pas trouvé un noeud avec caractère en commun */
                  /* On crée une feuille avec le reste des caractères */
                  const faj = new Noeud(reste,new Array<Noeud>(),this);
                  /* On regarde d'abord s'il y a déjà des fils dans la liste des fils */
                  if (this.fils.length === 0) 
                  {
                      /* S'il y en a aucun c'est à dire qu'on essaie d'ajouter à une feuille */
                      /* Donc on ajoute une feuille pour indiquer la fin du mot dans la liste des fils */
                      this.fils.push(new Noeud("\0",new Array<Noeud>(),this));
                  }
                  /* On l'ajoute à la liste des fils */
                  this.fils.push(faj);
                  /* On met à jour la liste des fils */
                  this.update();
                  return true;
              }
              if (encommun.length < this.cle.length)
              {
                  const aux = this.cle.slice(encommun.length);
                  const nn = new Noeud(aux,this.fils,this);
                  this.fils = new Array<Noeud>();
                  this.cle = encommun;
                  this.fils.push(new Noeud(mot.slice(encommun.length),new Array<Noeud>(),this));
                  this.fils.push(nn);
                  this.update();
                  return true;
              }
              return false;
          }
          if (this.pere !== undefined)
          {
              console.log('Le mot ' + mot + ' existe déjà dans l\'arbre');
          }
          return false;
     }

  • isFeuille() : La fonction permet de déterminer si le noeud est une feuille. isFeuille(): void -> boolean

     public isFeuille(): boolean {
          return this.fils.length === 0;
     }

  • showOnConsole() : La fonction permet d'afficher le contenu du noeud dans la console. showOnCOnsole() : void -> void

     public showOnConsole(): void {
          console.log('Clé : ' + this.cle);
          if (this.isFeuille()) {
              console.log('Est une feuille');
          }
          else {
                  console.log('Fils : ' + this.fils.length + ' fils');
                  for (var f of this.fils) {
                      f.showOnConsole();
                  }
          }       
     }

• Arbre : La classe qui répresente la structure de l'arbre de recherche, en stockant un objet de type Noeud comme la racine de l'arbre et des primitives d'une stucture d'arbre de recherhe. Les primitives sont les suivants :

  • constructor() : La fonction permet d'identifier un objet Arbre.

     constructor(racine: Noeud) {
          this.racine = racine;
     }

  • getRacine() : La fonction qui renvoie la racine d'un arbre. getRacine(): void -> Noeud

     public getRacine(): Noeud {
          return this.racine;
     }

  • setRacine(nouvelleRacine) : La fonction permet de changer la racine de l'arbre. setRacine(r): Noeud -> Noeud

     public setRacine(r: Noeud): Noeud {
          return this.racine = r;
     }

  • compare(a) : La fonction permet de comparer l'arbre avec un autre objet de type Arbre. compare(a): void -> number

     public compare(a: Arbre): number {
          return this.racine.compare(a.getRacine());
     }

  • canAdd(mot) : Le prédicat qui permet de tester si le mot passé en paramètre peut être ajouté dans l'arbre. canAdd(mot): string -> boolean

     public canAdd(mot: string): boolean {
      return match2Strings(this.racine.getCle(),mot).length > 0;
     }

  • add(mot) : La fonction permet d'ajouter le mot passé en paramètre à l'arbre. Ici nous testons quand même la possibilité d'ajout du mot dans l'arbre. add(mot): string -> boolean

     public add(mot: string): boolean {
          if (this.canAdd(mot)) {
              return this.racine.add(mot);
          } 
          else {
              return false;
          }
     }

  • showOnConsole() : La fonction permet d'afficher l'arbre sur le console pour une affichage basique. showOnConsole(): void->void

     public showOnConsole(): void {
          console.log('Racine ');
          this.racine.showOnConsole();
     }

• PatriciaTrie : La classe qui représente la structure Patricia-tries. Elle régroupe des objets Arbre sous une liste et contient les primitives d'un structure Patricia-tries. Les primitives sont les suivants :

  • constructor() : La fonction qui permet de identifier un objet PatriciaTrie.

     constructor() {
          this.noeuds = new Array<Arbre>();
     }

  • update() : La fonction permet de trier la liste des sous-arbres alphabétiquement. Cette fonction est privée parce qu'elle est destiné uniquement à l'usage l'interne de l'objet PatriciaTrie. update(): void -> Arbre[]

     private update(): Array<Arbre> {
          return this.noeuds = this.noeuds.sort((a : Arbre, b : Arbre) => a.
          compare(b)); 
     }

  • add(m) : La fonction qui permet d'ajouter un mot dans le patricia-trie. Elle trouve le sous arbre qu'elle doit ajouter le mot (crée une s'il n'y en existe pas) et mis à jour la liste des sous arbres pour qu'elle restent triée pour pour le cas qu'il n'y en a aucun sous-arbre existant que nous pouvons ajouter le mot passé en paramètres. Cette fonction n'est pas sensible à la casse pour éviter tout futur conflit. add(m): string -> boolean

     public add(m: string): boolean {
          const mot = m.toLowerCase();
          for (var n of this.noeuds) {
              if (n.canAdd(mot)) {
                  return n.add(mot);
              }
          }
          console.log('Le mot ' + mot + ' sera ajouté comme étant un nouveau arbre dans la liste des arbres');
          this.noeuds.push(new Arbre(new Noeud(mot,new Array<Noeud>())));
          return true;
     }

  • showOnConsole() : La fonction permet qui permet d'afficher l'objet dans le console. Pour une affichage basique. showOnConsole(): void -> void

     public  showOnConsole(): void {
          console.log('Patricia trie of ' +
                      this.noeuds.length + 
                      ' elements'
                     );
          for (var n of this.noeuds) {
              n.showOnConsole();
          }
     }

Question 1.3

L'exemple de base défini dans l'énoncé est le suivant A quel genial professeur de dactylographie sommes nous redevables de la superbe phrase ci dessous, un modele du genre, que toute dactylo connait par coeur puisque elle fait appel a chacune des touches du clavier de la machine a ecrire ?. J'ai fais l'hypothèse que ça ne soit pas sensible à la casse pour éviter les conflits liés aux changement de code ASCII par rapport à sa casse. Donc on obtient un Patricia-tries de 16 sous arbres. Le command suivant permet d'exécuter ces tests sur la console.

   npm run question13

1.2 Structure 2 : Tries Hybrides

---

RAPPEL

Trie Hybride : Une trie hybride est un arbre ternaire dont chaque noeud contient un caractère et une valeur (non vide lorsque le noeud réprésente une clé). Chaque noeud a 3 pointeurs : un lien Inf (resp. Eq, resp. Sup) vers le sous arbre dont le premier caractère est inférieur (resp. égal, resp. supérieur) à son caractère.

---

Question 1.4

Pour la réalisation de la structure tries hybrides j'ai crée la classe TrieHybride. C'est la classe qui contient tous les attributs et les fonctions concernant le structure tries hybrides. Ces attributs sont suivantes :

• valeur : Attribut de type entier facultatif qui représente la valeur de la racine (s'il y en a une). valeur : number|undefined

   private valeur: number|undefined;

• cle : Attribut de type chaîne de caractères représente la clé de la racine. cle: string

   private cle: string;

• pere : Attribut de type TrieHybride qui permet représente le père de l'arbre (s'il y en a un, undefined sinon). pere: TrieHybride|undefined

   private pere: TrieHybride|undefined; 

• inf : Attribut de type TrieHybride qui représente le sous-arbre Inf de l'arbre (s'il y en a un. undefined sinon). inf : TrieHybride|undefined

   private inf: TrieHybride|undefined;

• eq : Attribut de type TrieHybride qui représente le sous-arbre Eq de l'arbre (s'il y en a un, undefined sinon). eq: TrieHybride|undefined

   private eq: TrieHybride|undefined;

• sup : Attribut de type TrieHybride qui représente le sous-arbre Sup de l'arbre (s'il y en a un undefined sinon) sup: TrieHybride|undefined

   private sup: TrieHybride|undefined;

HYPOTHESE: Tous ces attributs sont privées.

Ses fonctions sont suivants :

• constructor(cle,valeur,inf,eq,sup,pere) : Le fonction permet d'identifier un objet TrieHybride. Les paramètres cle,valeur,inf,eq,sup,pere sont tous des paramètres facultatifs représentent la clé,la valeur, le sous-arbre inf, le sous-arbre eq, le sous-arbre sup et le pere de la racine. Dans le cas de non présence d'un des paramètres, celui ci est initalisé à la valeur null.

   constructor(cle?: string, 
               valeur?: number, 
               inf?: TrieHybride, 
               eq?: TrieHybride, 
               sup?: TrieHybride,
               pere?: TrieHybride) 
    {
        if (cle)
        {
            this.cle = cle;
        }
        else
        {
            this.cle = '\0';
        }
        this.valeur = valeur;
        this.inf = inf;
        this.eq = eq;
        this.sup = sup;
        this.pere = pere;
    }

• getValeur() : Fonction retourne la valeur de la racine de l'arbre (et undefined s'il y en a pas) getValeur(): void -> number|undefined

   public getValeur(): number|undefined {
        return this.valeur;
   }

• getCle() : Fonction retourne la clé de la racine de l'arbre getCle(): void -> string

    public getCle(): string {
        return this.cle;
    }

• getInf() : Fonction retourne le sous-arbre Inf de l'arbre (undefined s'il y en a pas). getInf(): void -> TrieHybride|undefined

   public getInf(): TrieHybride|undefined {
        return this.inf;
   }

• getEq() : Fonction retourne le sous-arbre Eq de l'arbre (undefined s'il y en a pas). getEq(): void -> TrieHybride|undefined

   public getEq(): TrieHybride|undefined {
        return this.eq;
   }

• getSup() : Fonction retourne le sous-arbre Sup de l'arbre (undefined s'il y en a pas). getSup(): void -> TrieHybride|undefined

   public getSup(): TrieHybride|undefined {
        return this.sup;
   }

• getAllSuccessors() : Fonction retourne la liste de tous les sous-arbres. getAllSuccessors(): void -> Array<TrieHybride|undefined>

   public getAllSuccessors(): Array<TrieHybride|undefined> {
        return new Array<TrieHybride|undefined>(this.inf,this.eq,this.sup);
   }    

• getPere() : Fonction retourne le pere de l'arbre (s'il y en a, undefined sinon) getPere(): void -> TrieHybride|undefined

   public getPere(): TrieHybride|undefined {
        return this.pere;
   }

• setValeur(valeur) : Fonction permet de changer la valeur de la racine de l'arbre. setValeur(valeur): number|undefined -> number|undefined

   public setValeur(valeur: number|undefined): number|undefined {
        return this.valeur = valeur
   }

• setCle(cle) : Fonction permet de changer la clé de la racine de l'arbre. setCle(cle): string -> string

   public setCle(cle: string): string {
        return this.cle = cle;
   }

• setInf(inf) : Fonction permet de changer le sous-arbre Inf de l'arbre. setInf(inf): TrieHybride|undefined -> TrieHybride|undefined

   public setInf(inf: TrieHybride|undefined): TrieHybride|undefined {
        return this.inf = inf;
   }

• setEq(eq) : Fonction permet de changer le sous-arbre Eq de l'arbre. setEq(eq): TrieHybride|undefined -> TrieHybride|undefined

   public setEq(eq: TrieHybride|undefined): TrieHybride|undefined {
        return this.eq = eq;
   }

• setSup(sup) : Fonction permet de changer le sous-arbre Sup de l'arbre. setSup(sup): TrieHybride|undefined -> TrieHybride|undefined

   public setSup(sup: TrieHybride|undefined): TrieHybride|undefined {
        return this.sup = sup;
   }

• setPere(p) : Fonction permet de changer le père de la racine de l'arbre. setPere(p): TrieHybride|undefined -> TrieHybride|undefined

   public setPere(p: TrieHybride|undefined): TrieHybride|undefined {
        return this.pere = p;
   }

• prem() : Fonction renvoie la première caractère de la clé de la racine de l'arbre. prem(): void -> string

   public prem(): string {
        return this.cle.split('')[0];
   }

• reste() : Fonction renvoie la clé de la racine privée de son premier caractère reste(): void -> string

   public reste(): string {
        return this.cle.slice(1);
   }

• car(i) : Fonction renvoie la ième caractère de la clé de la racine. car(i): number -> string

   public car(i : number): string {
        return this.cle.split('')[i];
   }

• lgueur() : Fonction renvoie le nombre de caractères de la clé de la racine. lgueur(): void -> number

   public lgueur(): number {
        return this.cle.length;
   }

• estVide() : Fonction permet de déterminer si l'arbre est vide estVide(): void -> boolean

   public estVide(): boolean {
        return (this.cle === '\0') && 
               (
                    (this.inf === undefined) ||
                    (this.inf.getCle() === '\0')
               ) &&
               (
                    (this.eq === undefined) ||
                    (this.eq.getCle() === '\0')
               ) &&
               (
                    (this.sup === undefined) ||
                    (this.sup.getCle() === '\0')
               ) &&
               (this.valeur === undefined);
   }

• compare(t) : Fonction permet de comparer deux tries hybrides. compare(t): TrieHybride -> number

   public compare(t: TrieHybride): number {
        if (this.cle < t.getCle())
        {
            return -1;
        }
        if (this.cle > t.getCle()) 
        {
            return 1;
        }
        return 0;
    }

• add(mot) : Fonction permet d'ajouter un mot au trie hybride. add(mot): string -> TrieHybride

   public add (mot: string, v:number): TrieHybride {
        const mt = mot.split('');
        var aux: TrieHybride = this;
        for (var i = 0; i < mt.length; i++) {
            if (i === mt.length-1) {
                aux = aux.addChar(mt[i],v);
                console.log('Ajout du mot ' + mot + ' est terminé!');
            }
            aux = aux.addChar(mt[i],undefined);
            //console.log('Ajout du caractère ' + mt[i] + ' est terminé');
        }
        return this;
   }

• addChar(char) : Fonction permet d'ajouter qu'un seul caractère au trie hybride. Cette fonction est privée parce qu'elle est destiné uniquement à l'usage dans la classe. addChar(char): string -> TrieHybride

   private addChar (char: string, v: number|undefined): TrieHybride 
   {
        if (this.estVide() === true) 
        {
            this.cle = char;
            this.valeur = v;
            return this;
        }
        else
        {
            if (char.localeCompare(this.cle) < 0)
            {
               if (this.inf === undefined)
               {
                   this.inf = new TrieHybride();
               }
               return this.inf.addChar(char,v);
            }
            if (char.localeCompare(this.cle) > 0) 
            {
                if (this.sup === undefined)
                {
                   this.sup = new TrieHybride();
                }
                return this.sup.addChar(char,v);
            }
            if (this.valeur === undefined) {
                this.valeur = v;
            }
            if (this.eq === undefined)
            {
                this.eq = new TrieHybride();
            }
            return this.eq;
         }
   }

Question 1.5

On insère le même phrase que la questio 1.3 appelé exemple de base. Cet insetion nous donne un trie hybride de 40 mots. Le command suivant permet d'exécuter ces tests sur la console.

   npm run question15

2. Fonctions avancées pour chacune des structures.

Question 2.6

4. Complexités

Question 4.10

L'étude de la complexités des fonctions de la question 2.6 sont les suivants :

• Les fonctions du structure Patricia Tries sont les suivants:

  • La fonction recherche(arbre,mot) -> booleéen de la classe ArbreFactory est le suivant :

      static recherche(arbre: PatriciaTrie|TrieHybride, mot:string):boolean {
              return arbre.recherche(mot);
  }

  Il fait dont un simple appel à la fonction recherche du structure Patricia Tries. On étudie donc la complexité de la fonction recherhce(mot) de la classe Patricia Trie qui le suivant :

      public recherche(mot: string,verbose: boolean = false): boolean
      {
          mot = mot.toLowerCase();
          if (verbose) 
          {
              console.log("On recherche le mot " + mot + " dans le patricia tries");
          }
          for (var n of this.noeuds)
          {
              if (verbose) 
              {
                  console.log("On trouve le sous-arbre dont la clé à sa racine est un préfixe du mot " + mot);
              }
              if (
                      (n.racine !== undefined) &&
                      (mot.indexOf(n.racine.getCle()) === 0)
                 )
              {
                  if (verbose) 
                  {
                      console.log("Si on a trouvé l'arbre qu'on cherche. On lance notre recherche dessus");
                  }
                  return n.recherche(mot,verbose);
              }
          }
          if (verbose) 
          {
              console.log("Si un tel arbre n'exsiste pas alors on retourne false");
          }
          return false;
      }

  Dans le pire des cas le fonction parcourt tous la liste des sous-arbres, et à la fin il fait un appel à la fonction recherche(mot) de la classe ArbreNoeudSimple qui est le suivant :

      public recherche(mot: string, verbose: boolean = false): boolean 
      {
         
          mot = mot.toLowerCase();
          if (verbose) 
          {
              console.log("On controle d'abord si le mot est vide");
          }
          if (mot.length === 0)
          {
              if (verbose) 
              {
                  console.log("Le mot et vide alors on retourne true");
              }
              return true;
          }
          else
          {
              if (verbose) 
              {
                  console.log("Le mot n'est pas vide. Alors on contrôle d'abord si l'arbre est vide");
              }
              if (this.estArbreVide() === true)
              {
                  if (verbose) 
                  {
                      console.log("Si l'arbre est vide alors on retourne false");
                  }
                  return false;
              }
              else
              {
                  if (verbose) 
                  {
                      console.log("Si l'arbre n'est pas vide alors on contrôle si la clé de la racine de l'arbre est un préfixe du mot");
                  }
                  if (
                          (this.racine !== undefined) &&
                          (mot.indexOf(this.racine.getCle()) === 0)
                      )
                  {
                      if (verbose) 
                      {
                          console.log("Si la racine de l'arbre est bien définie et que la clé de la racine de l'arbre est un préfixe du mot " + mot);
                          console.log("On trouve les caractères du mot privé de la clé de la racine de l'arbre");
                      }
                      const mreste = mot.slice(this.racine.getCle().length);
                      
                      if (verbose) 
                      {
                          console.log("Les caractères du mot privé de la clé de la racine de l'arbre est " + mreste);
                          console.log("On contrôle d'abord si cette reste est  vide");
                      }
   
                      if (mreste.length === 0)
                      {
                          if (verbose) 
                          {
                              console.log("Si cette reste est vide. Alors on contrôle d'abord si c'est une feuille");
                          }
                          if (this.estFeuille())
                          {
                              if (verbose) 
                              {
                                  console.log("Si c'est une feuille alors on retourne true");
                              }
                              return true;
                          }
                          else
                          {
                              if (verbose) 
                              {
                                  console.log("Si ce n'est pas une feuille alors on regarde s'il y a un arbre qui indique la fin du mot. C'est à dire s'il y a un arbre qui a '\0' commme la clé à sa racine");
                              }
                              for (var sa of this.sousArbres.filter(s => s !== undefined))
                              {
                                  if ((sa !== undefined) && (sa.racine !== undefined))
                                  {
                                      if (verbose) 
                                      {
                                          console.log("La clé de la racine est " + sa.racine.getCle());
                                          console.log("C'est la clé qu'on cherche " + (sa.racine.getCle() === "\0"));
                                      }
                                      if ((sa.racine.getCle() === "\0"))
                                      {       
                                          if (verbose) 
                                          {
                                              console.log("Si un tel arbre existe c'est à dire que le mot existe. Alors on retourne true");
                                          }
                                          return true;
                                      }
                                  }
                              }
                              return false;
                          }
                      }
                      else
                      {
                          for (var sae  of this.sousArbres.filter(sa => sa !== undefined))
                          {
                              if (
                                      (sae !== undefined) &&
                                      (sae.recherche(mreste) === true)
                                  )
                              {       
                                  return true;
                              }
                          }
                          return false;
                      }
                  }
                  else
                  {
                      if (verbose) 
                      {
                          console.log("Si la racine de l'arbre n'est pas définie ou la clé de la racine de l'arbre n'est pas un préfixe du mot " + mot + " on retourne false");
                      }
                      return false;
                  }
              }
          }
      }

  La fonction recherche du structure ArbreNoeudSimple a comme complexité dans le pire des cas O(2n). Qui fait la complexité de la fonction recherche précédent (de la classe PatriciaTrie) O(3n). Donc on peut dire que la complexité de la fonction recherche(arbre,mot) -> booleén du structure Patricia Tries est O(n).

  • La fonction ComptageMots(arbre) -> entier de la classe ArbreFactory:

     static comptageMots(arbre:PatriciaTrie|TrieHybride):number {
         return arbre.comptageDeMots();
     }

  Fonction fait un simple appel à la fonnction comptageDeMots() de la classe PatriciaTrie qui est le suivant :

      public comptageDeMots(): number
      {
          return this.noeuds.map(n => n.comptageDeMots()).reduce((a,b) => a + b, 0);
      }

  La compléxité de cette fonction est égal à la compléxité de la fonciton map de l'interface Array fois puis le compléxité e la fonction comptageDeMots() de la classe ArbreNoeudSimple plus la complexité de la fonction reduce de l'interface Array. D'après ECMA les fonctions .map et .reduce de l'interface Array ont comme complexité O(n). On va donc étudier la complexité de la fonction comptageDeMots() de la classe ArbreNoeudSimple qui est le suivant:

      public comptageDeMots(verbose:boolean = false): number
      {
          if (verbose) 
          {
              console.log("On contrôle d'abord si l'arbre est vide");
          }
          if (this.estArbreVide())
          {
              if (verbose) 
              {
                  console.log("Si l'arbre est vide alors on retourne 0");
              }
              return 0;
          }
          else
          {
              if (verbose) 
              {
                  console.log("Si l'arbre n'est pas vide alors on contrôle s'il s'agit d'une feuille");
              }
              if (this.estFeuille())
              {   
                  if (verbose) 
                  {
                      console.log("S'il s'agit d'une feuille. Alors on retourne 1");
                  }
                  return 1;
              }
              else
              {
                  if (verbose) 
                  {
                      console.log("Si ce n'est pas une feuille on lance notre fonction sur les sous-arbres definis et on fait une somme de tous");
                  }
                  return this.sousArbres.filter(sa => sa !== undefined).map(a => (<ArbreNoeudSimple>a).comptageDeMots()).reduce((accumulateur, valeurCourante) => accumulateur + valeurCourante,0);
              }
          }
      }

  La complexité dans le pire des cas de cette fonction est O(n) qui viens des complexités des fonctions filter, map et reduce de l'interface Array et de l'appels recursives de la fonction elle-mmême. Donc on peut déduire que la coplexité de la fonction ComptageMots(arbre) -> number de la classe ArbreFactory est en O(n).

  • La fonction listeDeMots(arbre) -> liste[mots] de la classe ArbreFactory est le suivant :

      static listeMots(arbre: PatriciaTrie|TrieHybride): Array<string> {
          return arbre.listeMots();
      }

  Il fait un simple appel à la fonction listeMots de la classe Patricia Tries qui est le suivant :

      public listeMots(prefixe: string = "",verbose:boolean = false): Array<string> {
          return this.noeuds.map(n => n.listeMots("",verbose)).reduce((a,b) => a.concat(b)).sort();
      }

  La complexité de cette fonction est donc la complexité de la fonciton map de l'interface Array fois la complexité de la fonction listeMots de la classe ArbreNoeudSimple plus la complexité de la fonction reduce de l'interface Array. Les fonctions map et reduce de l'interface Array ont comme complexité O(n) d'après ECMA. Donc on va étudier la complexité de la fonction listeMots de la classe ArbreNoeudSimple qui est le suivant:

      public listeMots(prefixe: string = "",verbose: boolean = false): Array<string> 
      {
          if (verbose) 
          {
              console.log("On crée une liste qui va contenir tous les mots dans l'arbre. On appele ça res");
          }
          var res = new Array<string>();
          if (verbose) 
          {
              console.log("On contrôle d'abord si l'arbre est vide");
          }
          if (this.estArbreVide())
          {
              if (verbose) 
              {
                  console.log("Si l'arbre est vide. On rajoute la préfixe à la liste des mots et on retourne res");
              }
              res.push(prefixe);
              return res;
          }
          else
          {
              if (verbose) 
              {
                  console.log("Si l'arbre n'est pas vide alors on contrôle si l'arbre est une feuille.");
              }
              if (this.estFeuille())
              {
                  if (verbose) 
                  {
                      console.log("Si l'arbre est une feuille. On contrôle si la racine de l'arbre est définie");
                  }
                  if (this.racine !== undefined)
                  {
                      if (verbose) 
                      {
                          console.log("Si la racine de l'arbre est définie. On ajoute la clé de la racine à la fin du préfixe et on rajoute le préfixe a la res");
                      }
                      const np: string = prefixe + this.racine.getCle();
                      if (verbose) 
                      {
                          console.log("Le nouvel préfixe est donc " + np);
                      }
                      res.push(np);
                      return res;
                  }
                  else
                  {
                      if (verbose) 
                      {
                          console.log("Si la racine n'est pas définie alors on rajoute le préfixe à la liste res et on retourne res");
                      }
                      res.push(prefixe);
                      return res;
                  }
              }
              else
              {
                  if (verbose) 
                  {
                      console.log("Si l'arbre n'est pas une feuille. Alors on contrôle si la racine est définie");
                  }
                  if (this.racine !== undefined)
                  {
                      if (verbose) 
                      {
                          console.log("Si la racine de l'arbre est bien défini alors on crée une nouvelle préfixe. Où on va concatener le préfixe actuel avec la clé de la racine.");
                      }
   
                      const mpre:string = prefixe + this.racine.getCle();
                      if (verbose) 
                      {
                          console.log("Ancien préfixe " + prefixe);
                          console.log("La clé à la racine " + this.racine.getCle());
                          console.log("Notre nouvelle préfixe est donc " + mpre);
                      }
                      return this.sousArbres.filter(s => s !== undefined).map(x => (<ArbreNoeudSimple>x).listeMots(mpre,verbose)).reduce((l1,l2) => l1.concat(l2), new Array());
                  }
                  else
                  {
                      if (verbose) 
                      {
                          console.log("Si la racine n'est pas définie. Alors on ajoute le préfixe à la res. Et on retourne res.");
                      }
                      res.push(prefixe);
                      return res;
                  }
              }
          }
          
      }

  La complexité de cette fonciton est en O(n) qui venant des appels recursives et des fonctions reduce et concat. Donc on peut en déduire que la complexité de la fonction listeMots(arbre) -> Liste[mots] de la classe ArbreFactory est en O(n)

  • La fonction ComptageNil(arbre) -> entier de la classe ArbreFactory est le suivant:

      public comptageNil(verbose?: boolean): number {
      return ((this.racine !== undefined)?this.racine.comptageNil():1) + 
             (this.sousArbres.filter(x => x === undefined).length) +
             ((this.pere !== undefined)?1:0) + 
             (this.sousArbres.filter(c => c !== undefined).map(v => (<ArbreNoeudSimple>v).comptageNil(verbose)).reduce((a,b) => a + b,0));
      }

  Soit n le nombre d'arbre de Patricia Tries la complexité de cette fonction est en n fois (qu'il vient de la compléxité de la fonction filter de l'interface Array) la compléxité de la fonction comptageNil de la classe ArbreNoeudSimple. On étudie donc la fonction comptageNil de la classe ArbreNoeudSimple pour conclure sur l'étude de la complexité de la fonction ComptageNil(arbre) -> entier. Cette fonction est le suivant :

      public comptageNil(verbose?: boolean): number {
          return ((this.racine !== undefined)?this.racine.comptageNil():1) + 
                 (this.sousArbres.filter(x => x === undefined).length) +
                 ((this.pere !== undefined)?1:0) + 
                 (this.sousArbres.filter(c => c !== undefined).map(v => (<ArbreNoeudSimple>v).comptageNil(verbose)).reduce((a,b) => a + b,0));
      }

  La fonction donc contrôle si la racine est bien défini et si elle est bien défini elle fait appel à la fonction comptageNil de la classe NoeudSimple parce que l'attribut racine est de cette type et rajoute cette resultat à la longueur de la liste des sousArbres qui est égal à undefined qui est aussi ajouté à 0 ou à 1 en fonction du père de l'arbre (si le père de l'arbre est défini 0 et 1 sinon) et la somme des resultats de l'appel de la fonction comptageNil sur chacune des sous-arbres. Don la complexité de cette fonction est en O(n²). D'où on peut déduire de la complexité de la fonction comptageNil(arbre) de la classe ArbreFactory pour le structure Patricia Tries.

  • La fonction Hauteur(arbre) -> entier de la classe ArbreFactory est le suivant :

      public hauteur(verbose:boolean = false):number {
          return this.noeuds.map(v => v.hauteur()).reduce((a,b) => Math.max(a,b),-1);
      }

  Cette fonction appel la fonction hauteur de chacun des sous-arbres et prend le max de tous ces resultats. Donc pour un Patricia Tries de n arbres elle fait n fois l'appel à la fonction hauteur de la classe ArbreNoeudSimple qui est le suivant :

        public hauteur(
          verbose: boolean= false
          ): number 
          {
          /* 
              Si l'arbre est vide on retourne -1
              Si l'arbre est une feuille on retourne 0
              Sinon l'hauteur est le maximum des hauteurs de ses sous-arbres  + 1 
              */
              return (this.estArbreVide() === true)?
              -1:
              ((this.estFeuille() === true)?
              0:
              ((this.sousArbres.
                  filter(x => x !== undefined).
                  map(x => (<ArbreNoeudSimple>x).hauteur()).
                  reduce((a,b) => Math.max(a,b),-1)
                  ) +
                  1
                  )
                  ); 
              }

  La complexité de cette fonction est O(n) parce qu'elle parcourt tous les sous-arbres pour trouver la branche la plus longue. Donc on peut en déduire de la complexité de cette fonction est O(n).

  • La fonction profondeurMoyen(arbre) -> entier de la classe ArbreFactory est le suivant:

      static profondeurMoyenne(arbre: PatriciaTrie|TrieHybride): number {
          return arbre.profondeurMoyen();
      }

  Cette fonction donc fait une simple appel à la fonction profondeurMoyen de la classe Patricia Tries qui est le suivant :

      public profondeurMoyen(verbose:boolean = false): number {
          return this.profondeurs(verbose).reduce((a,b) => a+b,0)/this.profondeurs().length; 
      }

  Cette fonction calcule le profondeur moyen en faisant la somme de profondeur de tous les feuilles et le divise par le nombre de feuilles dant l'arbre. On étudie donc la complexité de la fonction profondeurs qui calcule la liste des profondeurs de tous les feuilles de l'arbre qui est le suivant:

      public profondeurs(verbose:boolean=false,index:number = 0): Array<number>{
          if (this.estArbreVide())
          {
              if (verbose) 
              {
                  console.log("L'arbre est vide");
              }
              return [0];
          }
          else
          if (this.estFeuille())
          {
              if (verbose) 
              {
                  console.log("L'arbre est une feuille. Index = " + index);
              }
              return [index];
          }
          else
          {   
              if (this.pere == undefined)
              {
                  index++;
              }
              var feuilles = this.sousArbres.filter(x => (x !== undefined) && (x.estFeuille() === true));
              var nonFeuilles = this.sousArbres.filter(c => (c !== undefined) && (c.estFeuille() === false));
   
              if (verbose) 
              {
                  console.log("Le nombre des feuilles à niveau " + index + " est " + feuilles.length);
                  console.log("Le nombre des non-feuilles sont " + nonFeuilles.length);
              }
   
              var res = new Array<number>();
              for (var i = 0; i<feuilles.length; i++)
              {
                  res.push(index);
              }
              return res.concat(nonFeuilles.map(v => (<ArbreNoeudSimple>v).profondeurs(verbose,index+1))
                                               .reduce((a,c) => a.concat(c),[]));
          }
      }

  Cette fonction parcourt l'arbre niveaux par niveaux et ajoute le profondeur du niveau aux feuilles qui ont trouvé dans le niveau. Donc la complexité de cette fonction est O(n) avec n l'hauteur de l'arbre.

  • La fonction Prefixe(arbre,mot) -> entier de la classe ArbreFactory est le suivant :

      static prefixe(arbre: PatriciaTrie|TrieHybride, mot: string): number {
      return arbre.prefixe(mot);
      }

  La fonction fait simplement un appel à la fonction prefixe(mot) de la classe ArbreNoeudSimple qui est le suivant:

      public prefixe(mot:string,verbose:boolean= false): number {
          return (this.find(mot).estArbreVide() === true)?0:this.find(mot).listeMots().length;
      }

  La fonciton calcule la liste des mots de la sous-partie de l'arbre que le mot passé en paramètres est une préfixe. Donc on étudie la fonction find de la classe ArbreNoeudSimple qui est le suivant:

      public find(mot:string, verbose: boolean = false): ArbreNoeudSimple 
      {
          if ((mot.length === 0))
          {
              if (verbose) 
              {
                  console.log("Si le mot est vide. On retourne l'arbre actuel");
              }
              return this;
          }
          else
          {
              if (this.estArbreVide())
              {
                  if (verbose) 
                  {
                      console.log("Si l'arbre est vide alors on retourne undefined.");
                  }
                  return new ArbreNoeudSimple();
              }
              else
              {
                  if (verbose) 
                  {
                      console.log("Si l'arbre n'est pas vide. On regarde si la racine est définie");
                  }
                  if (this.racine !== undefined)
                  {
                      if (verbose) 
                      {
                          console.log("Si la racine de l'arbre est définie. Alors on controle si la clé est une préfixe du mot");
                      }
                      if (mot.indexOf(this.racine.getCle()) === 0)
                      {
                          if (verbose) 
                          {
                              console.log("Si la clé de la racine est une préfixe du mot. On contrôle si la clé est égale au mot");
                          }
                          if (this.racine.cle === mot)
                          {
                              if (verbose) 
                              {
                                  console.log("Si la clé est le mot on retourne this");
                              }
                              return this;
                          }
                          else
                          {
                              if (verbose) 
                              {
                                  console.log("Si la clé n'est pas le mot mais une préfixe du mot. Alors on va calculer le reste du mot. Et on va lancer notre recherche ce mot sur le sous arbre eligible");
                              }
                              const reste = mot.slice(this.racine.cle.length);
                              var eligible = this.sousArbres.filter(r => (r !== undefined) && (r.racine !== undefined) && (reste.indexOf(r.racine.getCle()) === 0));
                              if (eligible.length === 1)
                              {
                                  if (verbose) 
                                  {
                                      console.log("Si un sous-arbre eligible existe on lance notre fonction dessus ");
                                  }
                                  return (<ArbreNoeudSimple>eligible[0]).find(reste);
                              }
                              if (eligible.length === 0)
                              {
                                  if (verbose) 
                                  {
                                      console.log("Si il n'y a aucun arbre eligible.");
                                  }
                                  return new ArbreNoeudSimple();
                              }
                              if (eligible.length > 1)
                              {
                                  if (verbose)
                                  {
                                      console.log(Error,"Il y a plusieurs arbres existent");                                  
                                  }
                                  return new ArbreNoeudSimple();
                              }
                          }
                      }
                      else
                      {
                          if (verbose) 
                          {
                              console.log("Si la racine n'est pas un préfixe du mot. On retourne undefined");
                          }
                          return new ArbreNoeudSimple();
                      }
                  }
              }
          }
          if (verbose) 
          {
              console.log("On est rentré dans aucun if");
          }
          return new ArbreNoeudSimple();
      }

  Cette fonction a les mêmes démarches de la fonction recherche donc sa complexités aussi en O(n). Alors la complexité de la fonction prefixe(arbre,mot) pour le structure Patricia Tries est en O(n) qui est la même que la recherche.

  • La fonction Suppression(arbre,mot) -> PatriciaTrie de la classe ArbreFactory est le suivant:

      static suppression(arbre: PatriciaTrie|TrieHybride, mot: string): PatriciaTrie|TrieHybride {
          return arbre.supprimer(mot);
      }

  La fonction fait simplement un appel à la fonciton suppression de la classe PatriciaTrie qui est le suivant:

      public supprimer(mot:string,verbose:boolean = false): PatriciaTrie
      {
          if (verbose) 
          {
              console.log("Le nombre des mots " + this.listeMots().length);
              console.log("Les nombres des mots : " + this.noeuds.map(x => x.listeMots().length));
              console.log("Les nouvelles nombres des mots " + this.noeuds.map(x => x.supprimer(mot).listeMots().length));
              console.log("Les nombres des mots de la liste des sous arbres " + this.noeuds.map(x => x.listeMots().length))
   
          }
          this.noeuds = new Array<ArbreNoeudSimple>(...this.noeuds.map(w => w.supprimer(mot,false)));
          if (verbose) 
          {
              console.log("Les nombres des mots de la liste des sous arbres " + this.noeuds.map(x => x.listeMots().length))
          }
          return this;
      }

  La fonction parcourt la liste des arbres de la Patricia Tries et pour chacun des arbres elle appelle la fonciton supprimer(mot) de la classe ArbreNoeudSimple qui est le suivant:

      public supprimer(mot:string,verbose:boolean=false): ArbreNoeudSimple
          {
              if (verbose) 
              {
                  console.log("On contrôle d'abord si le mot existe dans l'arbre");
              }
              if (this.recherche(mot) === true)
              {
                  if (verbose) 
                  {
                      console.log("Si le mot existe dans l'arbre");
                      console.log("On retrouve la partie qui contient ce mot");
                  }
                  var partie: ArbreNoeudSimple = this.find(mot);
                  if (verbose) 
                  {
                      console.log("La variable partie contient la sous partie de l'arbre qui contient le mot " + mot);
                      console.log("On va supprimer le noeud qui indique la fin du mot de ses sous-arbres");
                      partie.showOnConsole();
                  }
                  if (partie.estFeuille())
                  {
                      if (verbose) 
                      {
                          console.log("Si la partie est une feuille. Alors on va supprimer ceci");
                          console.log("Le nombre des mots avant l'affichage" + this.listeMots().length);
                      }
                      partie.pere?partie.pere.sousArbres[partie.pere.sousArbres.indexOf(partie)] = undefined:partie.racine = undefined;
                      partie.racine = undefined;
                      while(partie.pere !== undefined)
                      {
                          partie = partie.pere;
                      }
                      if (verbose) 
                      {
                          console.log("Le nombre des mots dans la partie après while " + partie.listeMots().length);
                      }
                      return partie;
                  }
                  else
                  {
                      if (verbose) 
                      {
                          console.log("Si l'arbre n'est pas une feuille");
                          console.log("Le nombre des sous arbres " + partie.sousArbres.length);
                          console.log("le nombre des mots avant la suppression " + this.listeMots().length)
                      }
                      partie.sousArbres = partie.sousArbres.filter(c => ((c !== undefined) && (c.racine !== undefined) && (c.racine.cle !== "\0")));
                      if (verbose) 
                      {
                          console.log("Le nombre des sous arbres après" + partie.sousArbres.length);
                      }
                      while(partie.pere !== undefined)
                      {
                          partie = partie.pere;
                      }
                      if (verbose) 
                      {
                          console.log("La variable partie après while");
                          partie.showOnConsole();
                          console.log("Le nombre des mots dans la partie après while " + partie.listeMots().length);
   
                      }
                      return partie;
                  }
              }
              else
              {
                  if (verbose) 
                  {
                      console.log("Si le mot n'existe pas dans l'arbre");
                  }
                  return this;
              }
          }

  La fonction teste d'abord si le mot existe dans l'arbre et si il y existe il trouve la sous-partie associé au mot et supprime juste le noeud qui indique le fin de mots. Donc la complexité de cette fonction est le même que la recherche qui est en O(n).

• Les fonctions du structure Trie Hybride sont les suivants:

  • Fonction recherche(arbre,mot) -> booléen de la classe ArbreFactory fait simplement un appel à la fonction recherche(mot) de la classe TrieHybride qui est le suivant:

      public recherche(mot: string,verbose: boolean = false): boolean 
      {
          /**
              TODO:
          */
          mot = mot.toLowerCase();
          if (verbose) 
          {
                      console.log("On cherche le mot " + mot + " dans le trie hybride");
          }
          // - On contrôle d'abord si le mot est vide
          if (mot.length === 0)
          {
              // Si le mot est vide on retourne true
              if (verbose) 
              {
                  console.log("Si le mot est vide");
              }
              return true;
          }
          else
          {
              if (verbose) 
              {
                  console.log("Si le mot n'est pas vide. Alors on contrôle si l'arbre est vide");
              }
              // Si le mot n'est pas vide alors on contrôle si l'arbre est vide
              if (this.estArbreVide())
              {
                  // Si l'arbre est vide alors on retourne false
                  if (verbose) 
                  {
                      console.log("Si l'arbre est vide. Alors on retourne false");
                  }
                  return false;
              }
              else
              {
                  // Si l'arbre n'est pas vide, alors on contrôle si la clé de la racine de l'arbre est le premier lettre du mot passé en paramètres.
                  if (verbose) 
                  {
                      console.log("Si l'arbre n'est pas vide. Alors ");
                  }
                  if ((this.racine !== undefined) && (mot.indexOf(this.racine.getCle()) === 0))
                  {
                      // Si la clé de la racine de l'arbre est le premier caractère du mot passé en paramètres, on côntrole d'abord si le mot a plus de 1 caractères.
                      if (verbose) 
                      {
                          console.log("La clé de la racine est le premier caractère du mot passé en paramètres. On contrôle si le mot plus de 1 caractères");
                      }
                      if (mot.length > 1)
                      {
                          if (verbose) 
                          {
                              console.log("Si le mot contient plus de 1 caractères");
                          }
                          // Si le mot contient plus de 1 caractères on contrôle si l'arbre eq est défini
                          if (this.eq !== undefined)
                          {
                              // Si l'arbre eq est défini on lance notre recherche avec la reste des mots sur l'arbre eq
                              if (verbose) 
                              {
                                  console.log("L'arbre eq est bien defini. On lance notre recherche avec la reste du mot " + mot.slice(1) + " sur l'arbre eq");
                              }
                              return this.eq.recherche(mot.slice(1),verbose);
                          }
                          else
                          {
                              if (verbose) 
                              {
                                  console.log("Si l'arbre eq n'est pas defini on retourne false");
                              }
                              // Si l'arbre eq n'est pas défini alors on retoune false
                              return false;
                          }
                      }
                      else
                      {
                          if (verbose) 
                          {
                              console.log("Si le mot contient qu'un seul caractère alors on retorne true si la valeur est defini, false sinon");
                          }
                          return ((this.racine !== undefined) && (this.racine.valeur !== undefined));
                      }
                  }
                  else
                  {
                      // Si la clé de la racine n'est pas le premier lettre du mot passé en paramètres.
                      if (verbose) 
                      {
                          console.log("La clé de la racin n'est pas le premier lettre du mot passé en paramètres");
                      }
                      if (this.racine !== undefined)
                      {
                          if (verbose) 
                          {
                              console.log("La racine de l'arbre est défini");
                          }
                          if (this.racine.getCle()<mot.split('')[0])
                          {
                              if (verbose) 
                              {
                                  console.log("Si la clé de racine est plus petit que le premier caractère du mot. On contrôle si l'arbre sup existe");
                              }
                              if (this.sup === undefined)
                              {
                                 //Si l'arbre sup n'existe pas on retourne false
                                 if (verbose) 
                                 {
                                  console.log("Si l'arbre sup n'existe pas on retourne false");
                                 }
                                 return false;
                              }
                              else
                              {
                                  //Si l'arbre sup existe on lance notre recherche sur l'arbre sup avec le mot comme tel.
                                  if (verbose) 
                                  {
                                      console.log("Si l'arbre sup existe on lance notre recherche sur l'arbre sup avec le mot comme tel.");
                                  }
                                  return this.sup.recherche(mot,verbose);
                              }
                          }
                          else
                          {
                              if (verbose) 
                              {
                                  console.log("La clé de la racine de l'arbre est plus grand que le premier caractère du mot passé en paramètres. Alors on va traiter l'arbre inf");
                              }
                              if (this.inf === undefined)
                              {
                                  if (verbose) 
                                  {
                                      console.log("Si l'arbre inf n'est pas défini alors on retourne false");
                                  }
                                  return false;
                              }
                              else
                              {
                                  if (verbose) 
                                  {
                                      console.log("Si l'arbre inf est défini alors on relance notre recherche sur l'arbre inf avec le mot tel quel");
                                  }
                                  return this.inf.recherche(mot,verbose);
                              }
   
                          }
                      }
                      else
                      {
                          if (verbose) 
                          {
                              console.log("La racine de l'arbre n'est pas défini. On retourne false");
                          }
                          return false;
                      }
   
                  }
              }
          }
      }    

  En fonction du premier lettre du mot passé en paramètre la fonciton fait un appel d'elle même sur le sous-arbre concerncé (inf,eq ou sup). Et dans le cas que le mot n'a qu'un seul lettre elle cherche si la valeur de la racine de l'arbre dont le mot est la clé de la racine. Donc la complexité de cette fonction viens de parcourt des sous-arbres. La complexité de cette fonction est en O(n).

  • Fonction ComptageMots(arbre) -> entier de la classe ArbreFactory fait simplement un appel à la fonction comptageDemots() de la classe TrieHybride qui est le suivant:

      public comptageDeMots(verbose: boolean = false): number
      {
          if (verbose) 
          {
              console.log("On contrôle d'abord si l'arbre est vide");
          }
          if (this.estArbreVide())
          {
              if (verbose) 
              {
                  console.log("Si l'arbre est vide alors on retourne 0");
              }
              return 0;
          }
          else
          {
              if (verbose) 
              {
                  console.log("Si l'arbre n'est pas vide alors on contrôle si l'arbre est une feuille");
              }
              if (this.estFeuille())
              {
                  if (verbose) 
                  {
                      console.log("Si l'arbre est une feuille. Alors on retourne 1 si la valeur à la racine est définie et 0 sinon");
                  }
                  return ((this.racine !== undefined) && (this.racine.valeur !== undefined))?1:0;
              }
              else
              {
                  return  (
                              ((this.inf !== undefined)?this.inf.comptageDeMots():0) +
                              ((this.eq !== undefined)?this.eq.comptageDeMots():0) +
                              ((this.sup !== undefined)?this.sup.comptageDeMots():0) +
                              (((this.racine !== undefined) && (this.racine.valeur !== undefined))?1:0)
                          );
              }   
          }
   
      }

  La fonction fait la somme des résultats de la fonction comptageDeMots() de tous les sous-arbres et si la valeur de la racine de l'arbre indique un fin de mots 1 et 0 sinon. Pour le cas que l'arbre n'aucun sous-arbre et regarde si la racine est définie ou pas. Donc la complexité de cette fonciton est en 0(n) qui vient de la parcourt des sous-arbres.

  • Fonction ListeMots(arbre) -> Liste[mots] de la classe ArbreFactory fait simplement un appel à la fonction listeMots() de la classe TrieHybride qui est le suivant:

      public listeMots(prefixe: string = "",verbose: boolean = false): Array<string> 
      {
          if (verbose) 
          {
              console.log("On commence par créer une liste vide des chaînes de caractères qui va contenir le résultat");
          }
          var res = new Array<string>();
          if (verbose) 
          {
              console.log("On contrôle si l'arbre est vide.");
          }
          if (this.estArbreVide())
          {
              if (verbose) 
              {
                  console.log("Si l'arbre est vide alors. On retourne res");
              }
              return res.sort();
          }
          else
          {
              if (verbose) 
              {
                  console.log("Si l'arbre n'est pas vide alors on contrôle si c'est une feuille");
              }
              if (this.sousArbres.filter(x => x !== undefined).length === 0)
              {
                  if (verbose) 
                  {
                      console.log("S'il n'y a aucun sous arbres définis. Alors si c'est une feuille");
                  }
                  if (this.racine === undefined)
                  {
                      if (verbose) 
                      {
                          console.log("Si la racine n'est pas défini alors on retourne le res");
                      }
                      return res.sort();
                  }
                  else
                  {
                      if (verbose) 
                      {
                          console.log("Si la racine est bien définie alors on regarde si c'est la valeur est bien définie");
                      }
                      if (this.racine.valeur !== undefined)
                      {
                          if (verbose) 
                          {
                              console.log("Si la valeur est bien définie alors on rajoute la clé de la racine à la fin de préfixe et on ajoute ce nouvel à la res. Et on retourne la res");
                          }
                          const np = prefixe + this.racine.getCle();
                          res.push(np);
                          return res.sort();
                      }
                      else
                      {
                          if (verbose) 
                          {
                              console.log("Si la valeur de la racine n'est pas définie dans la feuille. Alors on retourne le res");
                          }
                          return res.sort();
                      }
                  }
              }
              else
              {
                  if (verbose) 
                  {
                      console.log("Si l'arbre n'est pas une feuille. On va traiter les cas de l'arbre inf,eq et sup");
                  }
                  if (this.racine === undefined)
                  {
                      if (verbose) 
                      {
                          console.log("Si la racine n'est pas définie alors on retourne res");
                      }
                      return res.sort();  
                  }
                  else
                  {
                      if (verbose) 
                      {
                          console.log("Si la racine est bien définie alors on traite d'abord le cas de la valeur à la racine est bien définie");
                      }
   
                      if (this.racine.valeur !== undefined)
                      {
                          if (verbose) 
                          {
                              console.log("Si la valeur à la racine est bien définie alors on rajoute la clé à la fin du préfixe et on rajoute ce nouveau mot à la res");
                          }
   
                          const np = (prefixe + this.racine.getCle());
   
                          if (verbose) 
                          {
                              console.log("La nouvelle clé est " + np);
                          }
                          res.push(np);
                          if (verbose) 
                          {
                              console.log("On rajoute ce nouvel à la res. On a res = " + res);
                          }
                      }
   
                      if (verbose) 
                      {
                          console.log("On traite maintenant l'arbre inf");
                      }
                      if (this.inf !== undefined)
                      {
                          if (verbose) 
                          {
                              console.log("Si l'arbre inf est bien défini alors on relance notre algo sur cet arbre inf et on concat le resultat avec la table res");
                              console.log("On appelle la fonction sur l'arbre inf avec le prefixe " + prefixe);
                          }
                          res = res.concat(this.inf.listeMots(prefixe,verbose));
                      }
   
                      if (verbose) 
                      {
                          console.log("On traite maintenant l'arbre eq");
                      }
                      if (this.eq !== undefined)
                      {
                          if (verbose) 
                          {
                              console.log("Si l'arbre eq est bien définie alors on lance notre algorithme avec le préfixe concaténe par la clé de la racine sur l'arbre eq. Et on concatène le resultat avec le res");
                          }
                          const np = prefixe + this.racine.getCle();
                          if (verbose) 
                          {
                              console.log("Le nouvel préfixe est " + np + ". On va lance l'algo avec ça sur l'arbre eq");
                          }
                          res = res.concat(this.eq.listeMots(np,verbose));
                      }
   
                      if (verbose) 
                      {
                          console.log("On traite maintenant l'arbre sup");
                      }
                      if (this.sup !== undefined)
                      {
                          if (verbose) 
                          {
                              console.log("Si l'arbre sup est bien définie. Alors on lance notre algorithme sur cet arbre et on concatène le resultat avec res");
                              console.log("On lance l'algo sur l'arbre sup avec préfixe " + prefixe);
                          }
                          res = res.concat(this.sup.listeMots(prefixe,verbose));
                      }
                      return res.sort();
                  }
              }
          }
      }

  La fonction parcourt tous les noeuds de l'arbre un par un et regarde si le noeud est un noeud qui indique la fin d'un mot. Pour cela la complexité de cette fonction est en O(n).

  • Fonction ComptageNil(arbre) -> entier de la classe ArbreFactory fait simplement un appel à la fonction comptageNil() de la classe TrieHybride qui est le suivant:

      public comptageNil(verbose: boolean = false): number {
          return (
                      ((this.inf !== undefined)?this.inf.comptageNil(verbose):1) + 
                      ((this.eq !== undefined)?this.eq.comptageNil(verbose):1) + 
                      ((this.sup !== undefined)?this.sup.comptageNil(verbose):1) +
                      ((this.racine !== undefined)?(<NoeudDouble>this.racine).comptageNil():1) +
                      ((this.pere !== undefined)?0:1)
                 );
      }

  la fonction fait une somme de résultats de la fonction comptageNil sur les sous-arbres, le résultat de la fonction comptageNil() de la racine de l'arbre et aussi 0 ou 1 en fonction du pere de l'arbre (si le père de l'arbre n'est pas définie elle est aussi nil donc 1). Donc la complexité de cette fonction est en O(n) qui vient de parcourt de tous les noeuds de l'arbre.

  • Fonction Hauteur(arbre) -> entier de la classe ArbreFactory fait simplement un appel à la fonction hauteur() de la classe TrieHybride qui est le suivant:

      public hauteur(
          verbose: boolean= false
          ): number 
          {
          /* 
              Si l'arbre est vide on retourne -1
              Si l'arbre est une feuille on retourne 0
              Sinon l'hauteur est le maximum des hauteurs de ses sous-arbres  + 1 
              */
              return (this.estArbreVide() === true)?
              -1:
              ((this.estFeuille() === true)?
              0:
              (Math.max(this.inf?this.inf.hauteur():-1,
              this.eq?this.eq.hauteur():-1,
              this.sup?this.sup.hauteur():-1,
              -1) + 1)); 
      }

  Cette fonction est appelé pour chaque sous-arbres. Donc elle parcourt tous les noeuds de l'arbre pratiquement. Donc la complexité elle vient de ce parcours qui est en O(n).

  • Fonction ProfonfeurMoyenne(arbre) -> entier de la classe ArbreFactory fait simplement un appel à la foction profondeurMoyen de la classe TrieHybride qui est le suivant:

      public profondeurMoyen(verbose?:boolean): number {
          const p = this.profondeurs();
          if (verbose) 
          {
              console.log("Le nombre des feuilles " + p.length);
              console.log("Le profondeur de chaque feuille est " + p);
          }
          return p.reduce((a,b) => a+b,0)/p.length;
      }

  LA fonction fait appel à la fonction profondeurs() qui donne la liste de profondeurs de tous les feuilles de l'arbre. Fait la somme de cette liste et divise par le nombre d'éléments de la liste. Pour calculer la moyenne. La fonction profondeurs() de la classe TrieHybride est donc le suivant:

      public profondeurs(verbose:boolean = false,index: number = 0): Array<number>{
          var res = new Array<number>();
          if (verbose) 
          {
              console.log("Initialisation de la variable res avec une liste vide des entiers");
          }
          if (this.estArbreVide())
          {
              if (verbose) 
              {
                  console.log("Si l'arbre est vide on retourne 0");
              }
              return [0];
          }
          else
          {
              if ((this.inf === undefined) && (this.sup === undefined) && (this.eq === undefined))
              {
                  if (verbose) 
                  {
                      console.log("Si l'arbre est une feuille alors on retourne index");
                  }
                  return [index];
              }
              else
              {
                  if (verbose) 
                  {
                      console.log("Si l'arbre n'est pas une feuille");
                  }
                  if (this.inf !== undefined)
                  {
                      if (verbose) 
                      {
                          console.log("Si l'arbre inf est bien définie");
                      }
                      res = res.concat(this.inf.profondeurs(verbose,index+1));
                  }
   
                  if (this.eq !== undefined)
                  {
                      if (verbose) 
                      {
                          console.log("Si l'arbre eq est bien définie");
                      }
                      res = res.concat(this.eq.profondeurs(verbose,index+1));
                  }
   
                  if (this.sup !== undefined)
                  {
                      if (verbose) 
                      {
                          console.log("Si l'arbre sup est défini");
                      }
                      res = res.concat(this.sup.profondeurs(verbose,index+1));
                  }
   
                  return res;
              }
          }
      }

  La fonction fait trouve d'abord la liste des feuilles et calcule la profondeur de chaque feuille. Donc cette fonction est en O(n²).

  • Fonction Prefixe(arbre,mot) -> entier de la classe ArbreFactory fait simplement un appel à la foction prefixe(mot) de la classe TrieHybride qui est le suivant:

      public prefixe(mot:string,verbose?:boolean): number {
          return (this.find(mot,verbose).listeMots().length) + ((this.recherche(mot)?1:0));
      }

  La fonction fait un appel à la fonction find pour trouver la sous-partie de l'arbre dont le mot passé en paramètre est un préfixe de tout l'arbre. Sur l'arbre résultant il appel la fonction listeMots() pour calculer la longueur et rajoute 1 ou 0 en fonction de si le mot passé en paramètre existe dans l'arbre. Alors la complexité de notre fonction est O(n) qui vient de parcourt de tous les noeuds de l'arbre. (On parcourt un partie des noeuds dans la fonction find et la reste dans la fonction listeMots())

  • Fonction Suppression(arbre,mot) -> TrieHybride de la classe ArbreFactory qui fait un appel à la fonction supprimer(mot) de la classe TrieHyride qui est le suivant:

      public supprimer(mot:string,verbose:boolean=false): TrieHybride
      {
          if (verbose) 
          {
              console.log("On va supprimer le mot " + mot + " de Trie Hybride.");
          }
          if (this.recherche(mot) === true)
          {
              if (verbose) 
              {
                  console.log("Si le mot existe dans l'arbre");
              }
              var partie = this.find(mot).pere;
              if (verbose) 
              {
                  console.log("La variable partie contient la sous-partie de l'arbre qui contient le mot");
              }
              partie&&partie.racine?partie.racine.valeur = undefined:console.log(Error,"La racine de la sous-partie n'est pas définie");
              if (verbose) 
              {
                  console.log("On mettre à undefined la valeur de la racine de l'arbre.");
              }
              while(partie && partie.pere !== undefined)
              {
                  partie = partie.pere
              }
              return partie?partie:new TrieHybride();
          }
          else
          {
              if (verbose) 
              {
                  console.log("Si le mot n'existe pas dans l'arbre ");
              }
              return this;
          }
      }

  La fonction a les mêmes démarches de la fonction recherche. Mais cette fois ci si le mot est trouvé dans l'arbre on met la valeur de la racine assosicé à nil (undefined pour notre cas). Donc la complexité de la fonction est en O(n).

En suite on étudie la complexité de deux fonctions fusionner(arbre) de la question 3.7 pour chacun de nos structures. Cet étude est le suivant:

• Le fonction fusionner de la classe ArbreFactory est le suivant:

    static fusionner (a1: PatriciaTrie|TrieHybride, a2: PatriciaTrie|TrieHybride): PatriciaTrie|TrieHybride|undefined {
        if ((a1 instanceof PatriciaTrie) && (a2 instanceof PatriciaTrie))
        {
            return a1.fusionner(a2);
        }
 
        if ((a1 instanceof TrieHybride) && (a2 instanceof TrieHybride))
        {
            return a1.fusionner(a2);
        }
 
        console.error("Pour pouvoir fusionner les deux arbres, les deux arbres doivent être de même type. Pour convertir entre les types, essayez la fonction convert");
        return undefined;
    }

Donc la fonction appelle la fonction fusionner de chaque structure pour chaque structure. Alors on étudie d'abord le structure Patricia Tries. La fonction fusionner(PatriciaTrie) est le suivant:

    public fusionner(pt: PatriciaTrie,verbose: boolean = false):PatriciaTrie
    {
        const ptlist = pt.listeMots();
        if (verbose) 
        {
            console.log("La liste des mots qu'on veut ajouter sont " + ptlist);
        }
        ptlist.map(w => this.add(w));
        return this;
    }

La fonction récupère d'abord la liste des mots du Patricia Trie passé en paramètres et les ajoute à la Patricia Tries courant. Donc la complexité est O(n) avec n nombre de noeuds de Patricia Tries passé en paramètres. Et puis, on étudie le structure Trie Hybride. la fonction fusionner(TrieHybride) est le suivant:

    public fusionner(a: TrieHybride,vebose:boolean = false): TrieHybride {
        a.listeMots().map(x => this.add(x,false,Math.floor(Math.random() * 1000)));
        return this;
    }

La fonction ajoute tous les mots strocké dans Trie Hybride passé en paramètres à Trie Hybride courant. Donc cette fonction est en O(n).

Puis on étudie les fonctions de conversion de la question 3.8 pour chacune des structures comme ceci:

• Les fonction conversion définis dans la classe ArbreFactory sont les suivants:

        static convertPatricia2Hybride(pt:PatriciaTrie): TrieHybride 
        {
            var res = new TrieHybride();
            const lmots = pt.listeMots();
            for (var i = 0;i<lmots.length;i++)
            {
                res.add(lmots[i],false,i);
            }
            return res;
        }

        static convertHybride2Patricia(th: TrieHybride): PatriciaTrie 
        {
            var res = new PatriciaTrie();
            const lmots = th.listeMots();
            for (var i of lmots)
            {
                res.add(i);
            }
            return res;
        }

Ces deux fonctions ont les mêmes démarches, ce qui est retrouver la liste des mots de l'arbre passé en paramètre et de les ajouter à une nouvelle arbre au fur à une mesure. Donc pour ces deux fonctions la complexité est en O(n).

Pour finir on étudie la complexité de la fonction de la question 3.9 ce qui est suivant:

    static convertPatricia2THEquilibre(pt:PatriciaTrie,verbose: boolean = false): TrieHybride 
        {
            function trieListe(liste: Array<string>) : Array<string>
            {
                if (liste.length < 3)
                {
                    return liste;
                }
                else
                {
                    var milieu = Math.round(liste.length/2);
                    var left = liste.slice(0,milieu);
                    var right = liste.slice(milieu+1);
 
                    return [liste[milieu]].concat(trieListe(left))
                                          .concat(trieListe(right));
                }
            }
 
            function shuffle(array:Array<string>):Array<string> {
              var currentIndex = array.length, temporaryValue, randomIndex;
 
              while (0 !== currentIndex) {
 
                randomIndex = Math.floor(Math.random() * currentIndex);
                currentIndex -= 1;
 
                temporaryValue = array[currentIndex];
                array[currentIndex] = array[randomIndex];
                array[randomIndex] = temporaryValue;
              }
 
              return array;
            }
 
 
            var res = new TrieHybride();
            /* 
                Par définition un arbre est dit équilibré si les hauteurs de ses braches sont plus ou moins équilibré.
                Dans le cas de Tries Hybride le structure de l'arbre est lié à l'ordre d'instertation des mots.
            */
            var lmots = pt.listeMots().sort();
            var linitiales = lmots.map(x => x[0]);
            var unitiales = [];
            for (var i of linitiales)
            {
                if (unitiales.indexOf(i) === -1)
                {
                    unitiales.push(i);
                }   
            }
            unitiales = unitiales.sort();
            unitiales = trieListe(unitiales);
 
            if (verbose) 
            {
                console.log("Les initiales des mots sont " + unitiales);
                console.log("On va ajouter les mots dans l'ordre des lettres dans unitiales")
            }
 
            for (var u of unitiales)
            {
                var aux = lmots.filter(c => c.indexOf(u) === 0)
                var thaux = this.createTrieHybride(aux.reduce((a,b) => a + " " + b, ""));
 
                var rarray = new Array();
                var ind = 0;
                while (thaux.hauteur() - thaux.profondeurMoyen() > ((ind>1000)?Math.min(...rarray):0))
                {
                    rarray.push((thaux.hauteur() - thaux.profondeurMoyen()));
                    ind++;
 
                    if (verbose) 
                    {
                        console.log("Liste aux " + aux);
                        console.log("La différence" + (thaux.hauteur() - thaux.profondeurMoyen()));
                    }
                    thaux = this.createTrieHybride(aux.reduce((a,b) => a + " " + b, ""));
                    aux = shuffle(aux);
                }
 
                for (var a of aux)
                {
                    res.add(a,false,lmots.indexOf(a));
                }       
            }
 
            return res;
        }

Dans le développement de cette fonction j'ai fais le choix d'être précis que d'être optimal. Donc la complexité de cette fonction va être trop trop grande. La fonction récupère la liste des mots de l'arbre passé en paramètres. Elle parcourt cette liste pour trouver le milieu. Elle recrée un nouvelle liste que chaque élément de cette liste est l'élément au milieu d'une des soulistes de la liste des préfixes des mots stocké dans l'arbre passé en paramètres. Pour chacun des mots préfixe, elle crée des sous listes dont les éléments de la liste sont triées aléatoirement et crée un structrue Trie Hyride avec la liste pour calculer on suite le profondeur moyen et l'hauteur. Elle crée des liste àléatoires 1000 fois afin d'avoir un meilleur estimation pour trouver le cas le plus équilibré. Puis elle cherche une combinaison des éléments de la liste des mots du préfixe mieux que les combinaisons essayés, pour ajouter en suite à la nouvelle Trie Hyrbide. Donc la complexité de cette fonction est en O(n * 1000) ce qui est gigantesque.