Algo ABR

Identification

Infoforall

18 - Arbre Binaire de Recherche


Nous allons voir un Arbre Binaire conçu spécifiquement pour pouvoir savoir où chercher facilement la clé qui nous intéresse.

Logiciel nécessaire pour l'activité : -

Prérequis :

  • Données : Arbre et Arbre Binaire
  • Algos : Parcours d'Arbres
  • Algos : Algorithmes des Arbres Binaires

Evaluation ✎ :

Documents de cours : open document ou pdf

Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)

1 - Arbre Binaire de Recherche (ABR)

1.1 Arbre Binaire de Recherche (ABR)

Un Arbre Binaire de Recherche est un Arbre Binaire qui respecte une organisation ordonnée particulière.

Les clés des Noeuds doivent toutes pouvoir être comparées entre elles (c'est à dire disposer d'un opérateur < ou > ...).

La définition de l'Arbre Binaire de Recherche (ABR) impose que :

  1. toutes les clés du sous-arbre gauche soient plus petites* que la clé de la racine de l'Arbre étudié
  2. toutes les clés du sous-arbre de droite soient plus grandes* que la clé de la racine de l'Arbre étudié

La présence du * indique que l'égalité peut être traitée comme vous le voulez : à vous de choisir si vous voulez placer le cas EGAL à droite ou à gauche. Dans un premier temps, nous nous limiterons au cas des arbres pour lequel les clés sont toutes différentes.

On notera qu'on peut également faire l'inverse : mettre les plus grandes à gauche et les plus petites à droite.

Exemples

Un Arbre Binaire de Recherche parfait :

ABR complet

Les mêmes noeuds avec les mêmes clés dans une configuration moins optimale pour la recherche :

ABR quelconque

L'intérêt ?

Comme pour la liste-tableau trié qui permet une recherche dichotomique à coût logarithmique plutôt que linéaire, l'ABR permet une recherche à coût logarithmique (sur un Arbre proche d'un Arbre Complet) plutôt que linéaire.

En Anglais

En anglais, on dit Binary Search Tree ou BST.

01° Vérifier que

  • toutes les clés à gauche du Noeud de clé 20 sont inférieures à 20 et
  • toutes les clés à droite du Noeud de clé 20 sont supérieures à 20
ABR complet

02° Créer un nouvel Arbre Binaire de Recherche (ABR) un peu moins optimisé pour la recherche mais comportant les mêmes clés : la racine 20 mène à gauche à 17 et à droite à 26.

Trouver deux versions du sous-arbre gauche possibles.

Pourquoi cet Arbre est-il moins optimisé pour la recherche ?

...CORRECTION...

ABR question 2

Ou encore

ABR question 2 version 2

Il est moins optimisé que l'Arbre Binaire Complet puisqu'il possède un étage en plus : la recherche du noeud de clé 9 sera plus longue d'une étape.

1.2 Création d'un arbre binaire de recherche (version naïve sans contrôle de la forme)

La première valeur reçue (50 ici) devient la clé de la racine puis on positionne progressivement les autres éléments de cette façon :

  1. Partir de la racine
  2. Si la clé à placer est inférieure à celle du noeud actuel, on part à gauche.
    • Si le sous-arbre gauche est vide, on lui attribue la clé ;
    • Sinon on répète l'opération récursivement en partant de la racine du sous-arbre gauche.
  3. Si la clé à placer est supérieure ou égale à celle du noeud actuel, on part à droite.
    • Si le sous-arbre droite est vide, on place la clé à droite;
    • Sinon on répète l'opération en partant de la racine du sous-arbre droite.

Exemple

On part de 50 et on rajoute 30.

ABR 50-30

On rajoute ensuite 45.

ABR 50-30-45

Puis 65.

ABR 50-30

Puis éventuellement à nouveau 65.

ABR 50-30

On notera donc qu'il faut faire très attention au cas des ABR lorsque des noeuds peuvent porter la même clé. Il existe des algorithmes d'insertion plus performants qui permettent de limiter la hauteur des AB si on rajoute plusieurs fois des clés identiques. On ne s'en préoccupera pas cette année.

04° Créer un nouvel Arbre Binaire de Recherche (ABR) dont les clés suivantes sont insérées progressivement : 32-16-8-35-33.

...CORRECTION...

ABR question 4

05° Même question en modifiant la place du 35 : 35-32-16-8-33.

L'ordre d'apparition des clés est-elle importante avec ce principe d'insertion ?

...CORRECTION...

ABR question 5

L'ordre des clés est effectivement à surveiller : on n'obtiendra pas le même arbre avec une séquence différente.

06° Utiliser le site proposé pour visualiser l'insertion de 33-35-16-8-32.

https://www.cs.usfca.edu/~galles/visualization/BST.html

Visualisation du site usfca.edu

07° En utilisant ces différents arbres binaires de recherche, déterminer les nombres de tests à faire avant de découvrir que 15 n'est pas présent.

Arbre binaire A :

Arbre binaire B :

...CORRECTION...

Pour A : il faut commencer par 20, puis 16, puis 9 puis partir à droite de 9 : vide On le sait donc en 4 étapes.

Pour B : il faut commencer par 20, puis 17, puis 16, puis 9 puis partir à droite de 9 : vide On le sait donc en 5 étapes.

08° En utilisant cet arbre qui n'est pas binaire (aucune raison de placer un élément à gauche ou à droite), déterminer les nombres de test à faire avant de découvrir que 15 n'est pas présent (on utilisera une exploration préfixe par exemple).

Arbre non binaire C :

...CORRECTION...

Puisque les noeuds ne sont pas triés, il va falloir les explorer un par un. Il faudra donc 7 explorations de noeuds et encore plus de tests sur les arbres vides : on monte à 15 tests.

Nous venons de voir que la forme de l'ABR avait une forte influence sur le coût de la recherche.

C'est pour cela qu'il existe des algorithmes d'insertion particulier qui cherche à constamment obtenir une forme idéale, quitte à transformer en partie l'arbre si nécessaire.

1.3 Coût d'une recherche dans un Arbre binaire
Résumé à connaître par coeur

Recherche non ciblée est linéaire en n : 𝓞(n)

Recherche ciblée est linéaire en h :

  • Sur un arbre binaire parfait : 𝓞(h) donc 𝓞(log2(n))
  • Sur un arbre binaire filiforme : 𝓞(h) donc 𝓞(n)
  • Sur un arbre binaire quelconque : 𝓞(h) donc 𝓞(n)

Il faut différencier la recherche non ciblée et ciblée.

Recherche non ciblée

La recherche non ciblée est linéaire en n, aucun avantage par rapport à une Liste.

On peut noter 𝓞(n) puisqu'on peut tomber par hasard sur le bon résultat avant la fin de l'exploration.

Recherche ciblée

La recherche ciblée est linéaire en h, cela veut dire que son efficacité va dépendre de la forme réelle de l'arbre.

On peut noter 𝓞(h) puisqu'on peut tomber par hasard sur le bon résultat avant la fin de l'exploration.

Mais attention, cette fois la valeur de h va dépendre de la forme de l'arbre :

  1. Si l'AB est parfait, h dépend de log2(n) et le coût de la recherche est donc logarithmique en n.
  2. On peut noter 𝓞(log2(n))

  3. Si l'AB est filiforme, h dépend de n et le coût de la recherche est donc linéaire en n.

    On peut noter 𝓞(n)

  4. Si l'AB est quelconque, on est entre les deux et la recherche est donc linéaire en n.
  5. On peut noter 𝓞(n)

2 - Algorithme d'insertion

Nous allons formaliser l'algorithme d'insertion en utilisant les primitives vues précédemment mais une nouvelle primitive liée à l'insertion.

Voici les 7 + 1 primitives que nous aurons le droit d'utiliser :

(Rappel) 2.1 Les primitives (2e partie de la définition de l'arbre binaire)

Voici la liste des primitives :

  1. nvABV() -> Arbre Binaire VIDE
  2. nvAB(v:Element, g:Arbre Binaire, d:Arbre Binaire) -> Arbre Binaire NON VIDE
  3. estABV(arbre:Arbre Binaire) -> bool
  4. racine(arbre:Arbre Binaire NON VIDE) -> Noeud
  5. contenu(noeud:Noeud) -> Element
  6. gauche(arbre:Arbre Binaire NON VIDE) -> Arbre Binaire
  7. droite(arbre:Arbre Binaire NON VIDE) -> Arbre Binaire
2.2 Primitive supplémentaire pour l'insertion dans un ABR

  1. initialiser(arbre:AB VIDE, cle:"Elément") -> None
  2. Transforme un AB VIDE en AB NON VIDE en lui attribuant une clé et deux sous-arbres vides.

    Attention à la PRECONDITON : l'arbre doit être VIDE.

2.3 Algorithme d'insertion d'une valeur

Principe général

L'algorithme consiste à se déplacer dans l'ABR jusqu'à trouver un sous_arbre VIDE, capable de recevoir notre nouvelle valeur.

Si on veut insérer 15 sur l'arbre ci-dessous, cela revient à vouloir localiser le sous_arbre noté .

Description des entrées / sortie

ENTREE 1 : un ABR.

ENTREE 2 : un Element qui est la clé qu'on veut insérer dans l'arbre.

SORTIE : Vide, modification en place.

Description de l'algorithme

On considère ici que la variable arbre est une variable locale à notre fonction : on peut réaliser des affectations sans modifier l'arbre reçu au départ.

inserer_cle_dans_ABR(arbre:ABR, cle:Element) -> Vide

    étape 1 : on explore l'arbre jusqu'à trouver un sous-arbre de destination vide

    TANT QUE NON estABV(arbre)

      SI cle < contenu(racine(arbre))

        arbregauche(arbre)

      SINON

        arbredroite(arbre)

      Fin SI

    Fin Tant Que


    étape 2 : on transforme cet ABR VIDE en NON VIDE

    initialiser(arbre, cle)


    Renvoyer VIDE

09° Exécuter mentalement l'algorithme pour insérer 31 dans cet Arbre :

  1. Combien de tours de boucle avez-vous fait ?
  2. Qui est le sous-arbre qu'on récupère ? Répondre en expliquant qui est son parent et s'il s'agit d'un sous-arbre gauche ou droite.
Visualisation du site usfca.edu

...CORRECTION...

On fait un tour de boucle avec l'arbre de racine 33, de racine et de racine 32. On a donc fait trois tours de boucle.

A la fin des boucles, on récupère le sous-arbre gauche de l'arbre qui porte la clé 32.

10-A° Enregistrer le module suivant sous le nom abr_ifa.py dans un répertoire qu'on nommera algoABR.

Il implémente l'ABR en utilisant un modèle objet à l'interne.

Il propose les 7+1 fonctions d'interface en cachant entiérement à l'utilisateur le fait que les données soient stockées dans des objets.

Compléter le programme pour qu'il implémente correctement l'insertion de nouvelles clés.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
"""Module implémentant un Arbre Binaire de Recherche (ABR) avec un modèle objets """ # Déclaration de la classe AB class AB: """Implémentation d'un Arbre Binaire de Recherche""" def __init__(self, valeur, gauche, droite): self.v = valeur self.g = gauche self.d = droite # Fonctions d'interface (accessibles de l'extérieur) def contenu(noeud:'Noeud') -> 'Element': """Renvoie le contenu associé au noeud fourni""" return noeud.v def nv_ABV() -> 'AB VIDE': """Renvoie un nouvel Arbre Binaire Vide""" return AB(None, None, None) def nv_AB(valeur:'Element', g:'AB', d:'AB') -> 'AB NON VIDE': """Renvoie un nouvel Arbre Binaire dont la racine porte valeur et qui mène aux sous-arbres g et d""" return AB(valeur, g, d) def est_ABV(arbre:'AB') -> bool: """Prédicat qui renvoie True si l'arbre est vide""" return arbre.v is None and arbre.g is None and arbre.d is None def racine(arbre:'AB NON VIDE') -> 'Noeud': """Renvoie le noeud-racine de l'Arbre Binaire NON VIDE""" return arbre # ici arbre et racine sont des alias def gauche(arbre:'AB NON VIDE') -> 'AB': """Renvoie le sous-arbre gauche de l'Arbre Binaire NON VIDE""" return arbre.g def droite(arbre:'AB NON VIDE') -> 'AB': """Renvoie le sous-arbre droite de l'Arbre Binaire NON VIDE""" return arbre.d def initialiser(arbre:'AB VIDE', cle:'Elément') -> None: """Transforme l'AB VIDE en AB NON VIDE en lui attribuant une clé et deux sous-arbres vides.""" arbre.v = cle arbre.g = nv_ABV() arbre.d = nv_ABV() def inserer_cle_dans_ABR(arbre:'ABR', cle:'Elément') -> None: """Place la clé au bon endroit dans l'ABR""" while ... if ... ... else: ... ... # Programme de test du module if __name__ == "__main__": a1 = nv_ABV() inserer_cle_dans_ABR(a1, 33) inserer_cle_dans_ABR(a1, 35) inserer_cle_dans_ABR(a1, 16) inserer_cle_dans_ABR(a1, 32) inserer_cle_dans_ABR(a1, 8)

...CORRECTION...

53 54 55 56 57 58 59 60 61
def inserer_cle_dans_ABR(arbre:'ABR', cle:'Elément') -> None: """Place la clé au bon endroit dans l'ABR""" while not est_ABV(arbre): if cle < contenu(racine(arbre)): arbre = gauche(arbre) else: arbre = droite(arbre) initialiser(arbre, cle)

10-B° Lancer le module compléter et tracer l'arbre binaire de recherche obtenu en lisant le code puis en analysant l'exploration directe qu'on en fait dans la console :

>>> a1.g.v 16 >>> a1.v 33 >>> a1.g.v 16 ...

11° Quel est le coût de l'étape 1 (le tant que) après implémentation ? Quel est le coût de l'étape 2 (l'initialisation d'un AB VIDE en NON VIDE) après implémentation ? En déduire le coût de l'insertion d'un nouveau noeud dans un ABR ?

...CORRECTION...

53 54 55 56 57 58 59 60 61
def inserer_cle_dans_ABR(arbre:'ABR', cle:'Elément') -> None: """Place la clé au bon endroit dans l'ABR""" while not est_ABV(arbre): if cle < contenu(racine(arbre)): arbre = gauche(arbre) else: arbre = droite(arbre) initialiser(arbre, cle)

Etape 1 : Dans le pire des cas, on réalise la boucle TANT QUE un nombre de fois égal au maximum à la hauteur h pour atteindre l'étage le plus bas de l'arbre.

L'analyse du code de la boucle TANT QUE montre qu'il n'y a pas de boucle interne, ni d'appel récursif et qu'on utilise uniquement des primitives qu'on a pu concevoir à coôt constant.

On en déduit que le coût du TANT QUE est linéaire par rapport à la hauteur h de l'arbre : 𝓞(h*1) = 𝓞(h)

Etape 2 : En allant lire le code de la nouvelle primitive initialiser(), on peut voir qu'elle a un coût CONSTANT puisqu'elle ne fait qu'aller en mémoire pour modifier 3 attributs : 𝓞(1)

Au total, si on additionne les deux coûts, l'analyse asymptotique nous amène à écrire 𝓞(h + 1) = 𝓞(h) à la hauteur h de l'ABR : l'algorithme est LINEAIRE en h.

12° Le coût est donc linéaire en h. Quel encadrement peut-on donner à ce coût en fonction de la taille n de l'arbre ?

...CORRECTION...

Allez voir le bout de cours juste en dessous.

2.4 Coût de l'algorithme d'insertion d'un noeud dans un ABR (sans optimisation)

C'est comme pour la recherche ciblée.

Le coût est linéaire par rapport à la hauteur h l'ABR : 𝓞(h).

  1. Si l'AB est parfait, on obtient un coût logarithmique sur la taille de l'Arbre : 𝓞(log2(n))
  2. Si l'AB est filiforme, on obtient un coût linéaire par rapport à la taille : 𝓞(n)
  3. Si l'AB est quelconque, on est entre les deux et donc 𝓞(n)

13° Trouver la version récursive de notre fonction inserer_cle_dans_ABR(). Commencez par réflechir au cas de base, celui où on sait qu'on peut insérer car l'arbre où on se trouve ne contient rien : l'arbre vide.

Voici la fonction à compléter :

1 2 3 4 5 6 7 8 9
def inserer_cle_dans_ABR(arbre:'ABR', cle:'Elément') -> None: """Place la clé au bon endroit dans l'ABR""" if est_ABV(arbre): ... else: if cle < contenu(racine(arbre)): ... else: ...

...CORRECTION...

1 2 3 4 5 6 7 8 9
def inserer_cle_dans_ABR(arbre:'ABR', cle:'Elément') -> None: """Place la clé au bon endroit dans l'ABR""" if est_ABV(arbre): initialiser(arbre, cle) else: if cle < contenu(racine(arbre)): inserer_cle_dans_ABR(gauche(arbre), cle) else: inserer_cle_dans_ABR(droite(arbre), cle)

14° Effacer la version récursive et retrouver tenter de retrouver seul la fonction itérative inserer_cle_dans_ABR().

15° Effacer la version itérative et retrouver tenter de retrouver seul la fonction récursive inserer_cle_dans_ABR().

3 - Algorithme de recherche

L'Arbre Binaire de Recherche permet de faire des recherches ciblées et donc de permettre des recherches à coût logarithmique pourvu que sa forme soit proche de celle d'un arbre parfait.

3.1 Algorithme (itératif, 2 sorties) de recherche dans un ABR

Principe

La recherche d'une clé cr est ciblée :

  1. Si l'arbre actuel est un arbre vide, on renvoie cet arbre VIDE.
  2. Si c'est la bonne clé (cr == c), on a trouvé. On renvoie l'ABR dont la racine porte cette clé.
  3. Si la clé cherchée est plus petite que la clé du noeud actuel, on va à gauche.
  4. Si la clé cherchée est plus grande que la clé du noeud actuel, on va à droite.
Description des entrées

ENTREE 1 : un ABR arbre

ENTREE 2 : une clé cr

SORTIE : la référence d'un ABR portant cette clé, potentiellement un ABV.

Description de l'algorithme

recherche(arbre:ABR, cr:Cle) -> ABR

    TANT QUE NON estABV(arbre)

      SI cr == contenu(racine(arbre))

        Renvoyer arbre

      SINON SI cr < contenu(racine(arbre))

        arbregauche(arbre)

      SINON SI cr > contenu(racine(arbre))

        arbredroite(arbre)

      Fin SI

    Fin Tant Que

    Renvoyer arbre # C'est un ABV si on arrive ici

16-A° Appliquer cet algorithme sur cet arbre en cherchant 22. Donner les noeuds rencontrés lors de la recherche et son résultat.

ABR complet

16-B° Appliquer cet algorithme sur cet arbre en cherchant 18. Donner les noeuds rencontrés lors de la recherche et son résultat.

ABR complet

17° Dans le pire des cas, quel est le coût de cet algortihme en fonction de la hauteur de l'arbre ? En fonction de la taille pour un arbre complet ?

ABR complet

...CORRECTION...

On retrouve un coût linéaire par rapport à la hauteur.

Pour un arbre complet, le coût est donc logarithmique base 2 par rapport à la taille puisqu'à chaque étape, on réduit approximativement par deux le nombre de noeuds à supprimer de la recherche.

3.2 Coût d'une recherche dans un ABR

Le coût est toujours linéaire par rapport à la hauteur h l'arbre binaire de recherche : 𝓞(h).

  1. Si l'AB est parfait, on obtient un coût logarithmique sur la taille de l'Arbre : 𝓞(log2(n))
  2. Si l'AB est filiforme, on obtient un coût linéaire par rapport à la taille : 𝓞(n)
  3. Si l'AB est quelconque, on est entre les deux et donc 𝓞(n)

18° Réaliser (en Python, dans votre module ABR) la fonction recherche() permettant de rechercher un noeud dans un ABR. Attention, la fonction doit renvoyer le sous-arbre portant cette clé en tant que racine.

def recherche(arbre:ABR, cr:Cle) -> ABR

19° Proposer une version de la fonction de recherche possédant un unique return. Cela permet notamment de surveiller plus facilement le comportement de la fonction : une seule sortie à vérifier avec des asserts par exemple.

recherche(arbre:ABR, cr:Cle) -> ABR

Voici la correction sous d'algoritmhe :

3.3 Algorithme (itératif, 1 sortie) de recherche dans un ABR

Description des entrées

ENTREE 1 : un ABR arbre

ENTREE 2 : une clé cr

SORTIE : la référence d'un ABR portant la clé, potentiellement un ABV.

Description de l'algorithme

recherche(arbre:ABR, cr:Cle) -> ABR

    reponse ← ABV

    TANT QUE NON estABV(arbre)

      SI cr == cle(racine(arbre))

        reponsearbre

        arbre ← ABV

      SINON SI cr < cle(racine(arbre))

        arbregauche(arbre)

      SINON SI cr > cle(racine(arbre))

        arbredroite(arbre)

      Fin SI

    Fin Tant Que

    Renvoyer reponse

20° Proposer une version utilisant la récursivité. Pour cela, demandez-vous quels sont les cas de base, et ce qu'il faut faire sur les cas récursifs.

Dans cette version, arbre pourra être un arbre vide.

3.4 Algorithme (récursif) de recherche dans un ABR

Description des entrées

ENTREE 1 : un ABR arbre

ENTREE 2 : une clé cr

SORTIE : la référence d'un ABR portant la clé, potentiellement un ABV.

Description de l'algorithme

recherche(arbre:ABR, cr:Cle) -> ABR

      SI estABV(arbre)

        Renvoyer arbre

      SINON SI cr == cle(racine(arbre))

        Renvoyer arbre

      SINON SI cr < cle(racine(arbre))

        Renvoyer recherche(gauche(arbre), cr)

      SINON SI cr > cle(racine(arbre))

        Renvoyer recherche(droite(arbre), cr)

      Fin SI

21-A° Observer cet arbre binaire de recherche. Où se trouvera toujours le minimum ?

Réaliser alors la fonction récursive minimum() qui devra renvoyer la clé la plus petite de l'arbre reçu.

ABR complet

21-B° Réaliser la fonction itérative de minimum().

22-A° Observer cet arbre binaire de recherche. Où se trouvera toujours le maximum ?

Réaliser alors la fonction récursive maximum() qui devra renvoyer la clé la plus grande de l'arbre reçu.

ABR complet

22-B° Réaliser la fonction itérative de maximum().

Cette dernière partie de cours définit un cas moins extrêmes que l'arbre parfait mais sur lequel on pourra néanmoins appliquer les formules découvertes sur le cas parfait. Pratique.

3.5 AB équilibré

ABR Parfait, ABR Complet : coût logarithmique en recherche

Vous savez qu'un ABR est parfait si le dernier étage est entièrement rempli par les feuilles de l'arbre.

ABR complet

Dans un ABR parfait, le coût de l'insertion et de la recherche est alors 𝓞(log2(n)).

Or, ce cas est assez rare : il faut déjà que le nombre de noeuds soit exactement n = 2x - 1.

Si l'ABR est complet, il manque uniquement quelques feuille sur le dernier étage mais l'arbre est sinon rempli. Le coût asymptotique des algorithmes reste donc équivalent à celui de l'arbre parfait : 𝓞(log2(n)).

ABR équilibré ou AVL : coût logarithmique également

Nous allons rajouter une nouvelle variante d'ABR beaucoup plus courant mais dont le coût est globalement comparable à celui d'un AB parfait ou d'un AB complet : l'AB équilibré.

La notion d'arbre équilibré possède plusieurs variantes. Nous allons en voir une qui date de 1962. Deux mathématiciens, Adel'son-Vel'skii et Landis, introduisent des critères définissant un équilibre. Les arbres vérifiant ces critères sont connus sous le nom d'arbres AVL. Avec ce critère AVL, un arbre équilibré est un arbre pour lequel, pour tout nœud de l'arbre, la différence entre les hauteurs de ses deux sous-arbres ne peut excéder 1.

Exemples

Pour les exemples ci-dessous, le choix de la convention n'a aucune importance. J'ai choisi d'utiliser pR = 0, mais pR = 1 aurait donner les mêmes résultats.

Exemple 1 : Cet Arbre n'est pas un Arbre Binaire équilibré AVL : le noeud 17 possède à gauche un sous-arbre de hauteur 1 et à droite un sous-arbre de hauteur -1 (un arbre vide)

ABR pas équilibré

Exemple 2 : Par contre, cet Arbre est un Arbre Binaire équilibré :

ABR équilibré
Intérêt de la notion d'arbre équilibré ?

Cette définition va permettre d'étendre formellement le coût logarithmique d'une recherche ou d'une insertion (𝓞(log2(n))) à une gamme d'ABR non réellement parfaits.

4 - FAQ

Rien pour le moment

La dernière activité liée aux arbres traitera de l'implémentation d'un Arbre des Pokmeons, permettant de retrouver rapidement celui qui a les meilleurs caractéristiques cherchées.

Activité publiée le 02 01 2021
Dernière modification : 30 01 2025
Auteur : ows. h.