Algo AB Recherche

Identification

Infoforall

17 - Recherche dans un AB


Pour l'instant, nous avons vu des méthodes permettant de parcourir les noeuds un par un de différentes façons.

Puisqu'on visite tous les noeuds, ces explorations sont toutes à coût linéaire dans le meilleur des cas.

Regardons ce qui pourrait changer si on savait où aller plutôt que d'explorer l'Arbre finalement un peu au hasard.

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

Choix de la hauteur

On prendra dans toute cette activité une hauteur de 0 pour un Arbre ne comportant que sa racine.

1 - Arbres Binaires Complets

Nous avons vu qu'un Arbre Binaire Complet était un Arbre Binaire où les Feuilles sont toutes sur le dernier niveau, à la plus grande profondeur disponible.

Exemple avec un Arbre Binaire Complet de hauteur 2 :

Arbre Binaire Complet
Les caractéristiques d'un Arbre Binaire Complet (version profondeur 0 pour la racine)

Nous avons vu que l'Arbre Binaire Complet est la meilleure configuration en terme de réduction de la hauteur.

Pour un Arbre Binaire Complet, la hauteur est liée au log2 de la taille :

h = log2(n+1) - 1 ou encore h = ⌊log2(n)⌋ ( Formule 1)

On peut également faire l'inverse : connaissant la hauteur d'un Arbre Binaire Complet, on peut prévoir la taille de l'Arbre :

n = 2h+1 - 1 ( Formule 2)

01° Quelle est la taille d'un Arbre Binaire Complet de hauteur 11 (on prendra la racine à 0) ?

...CORRECTION...

>>> 2**(11+1) - 1 4095

Un Arbre Binaire Complet de 12 étages possède donc 4095 Noeuds.

02° Un Arbre Binaire de 500 Noeuds peut-il être complet ?

...CORRECTION...

On peut faire une sorte de raisonnement par l'absurde : on considère qu'il l'est. Dans ce cas, l'utilisation de la formule devrait donner un nombre entier.

>>> from math import log2 >>> log2(500+1) 8.968666793195208

On obtient un résultat qui n'est pas interprétable comme un entier : un Arbre Binaire de 500 Noeuds ne peut donc pas être considéré comme Complet.

03° Calculer ceci avec Python.

>>> from math import log2 >>> log2(2**3) >>> log2(2**8) >>> log2(2**27)

Que vaut log2(2x) à priori ?

...CORRECTION...

>>> from math import log2 >>> log2(2**3) 3.0 >>> log2(2**8) 8.0 >>> log2(2**27) 27.0

Ce n'est pas une démonstration, mais on constate qu'on peut certainement écrire log2(2x) = x.

04° Calculer ceci avec Python.

>>> from math import log2 >>> 2**(log2(3)) >>> 2**(log2(13)) >>> 2**(log2(23))

Que vaut 2log2(x) à priori ?

...CORRECTION...

>>> from math import log2 >>> 2**(log2(3)) 3.0 >>> 2**(log2(13)) 13.0 >>> 2**(log2(26)) 25.999999999999993

Ce n'est pas une démonstration, mais on constate qu'on peut certainement écrire 2log2(x) = x.

Le dernier cas pourrait être interprété comme le fait que la formule n'est pas totalement exacte, mais il s'agit bien entendu d'un exemple de l'inexactitude des calculs sur les flottants par un ordinateur.

05° Montrer qu'on peut passer de la formule (1) à la formule (2).

...CORRECTION...

On part de cela la formule 1.

Formule (1)

h = log2(n+1) - 1

h + 1 = log2(n+1)

2h+1 = 2log2(n+1)

On note que 2log2(x) = x.

2h+1 = n + 1

Il suffit de passer +1 dans le membre de gauche :

2h+1 - 1 = n

On obtient bien la formule (2) :

n = 2h+1 - 1

2 - Arbres Filiformes

Les caractéristiques d'un Arbre Binaire Filiforme (version profondeur 0 ou 1 pour la racine)

Nous avons vu que l'Arbre Binaire Filiforme est la pire configuration en terme de réduction de la hauteur.

h = n - 1 ( racine de profondeur 0)

Arbre question 17

3 - Arbres Binaires quelconques

Encadrements des caractéristiques d'un Arbre Binaire quelconque

Un arbre binaire quelconque va donc avoir des caractéristiques situées entre l'Arbre Complet et l'Arbre Filiforme.

Encadrement avec une profondeur 0 pour la racine

h + 1 ≤ n ≤ 2h+1 - 1

log2(n)≤ h ≤ n - 1

Les signes ⌊ ⌋ veulent dire d'arrondir à l'inférieur.

06° Encadrer la hauteur d'un Arbre Binaire possédant 60 noeuds.

...CORRECTION...

Encadrement avec une profondeur 0 pour la racine

log2(n)≤ h ≤ n - 1

log2(60)≤ h ≤ 60 - 1

On sait que log2(32) = log2(25) = 5 et que log2(64) = log2(26) = 6.

On peut donc dire que log2(60) vaut 5 virgule quelque chose.

En arrondissant log2(60) à la valeur entière inférieure, on obtient donc :

5 ≤ h ≤ 59

07° Encadrer la taille d'un Arbre Binaire possédant une hauteur de 5.

...CORRECTION...

On part de cela la formule suivante :

h + 1 ≤ n ≤ 2h+1 - 1

5 + 1 ≤ n ≤ 25+1 - 1

6 ≤ n ≤ 26 - 1

6 ≤ n ≤ 64 - 1

6 ≤ n ≤ 63

4 - Exploration en sachant où aller

08° Si on ne sait pas où chercher exactement, quel est le coût (dans le pire des cas) d'un algorithme qui doit trouver un noeud (en fonction de la taille n de l'arbre) ?

  1. Constant
  2. Logarithmique
  3. Linéaire
  4. Quadratique
  5. Exponentiel
  6. Factoriel

...CORRECTION...

Linéaire : on doit fouiller l'Arbre Binaire noeud par noeud.

Dans un Arbre Binaire, la recherche est donc linéaire si on ne sait pas où chercher, qu'on ai un Arbre Complet ou Filiforme : il faut chercher un peu au hasard.C'est un peu dommage.

09° Si on sait où cibler la recherche, en combien d'étapes parvient-on à atteindre le noeud du père de la mère d'Alice ?

Parcours en largeur

Combien de choix de destination à faire dans le pire des cas si on a un Arbre de hauteur 12 ? (on prendra une profondeur de 0 pour la racine)

...CORRECTION...

A chaque choix conscients, on réduit le nombre de noeuds à explorer. Dans le cas d'un Arbre Complet, on divise ce nombre par deux globalement.

En partant de la racine Alice, on a trois choses à faire :

  1. Partir à droite pour trouver la mère d'Alice
  2. Partir à gauche pour trouver le père de la mère
  3. Renvoyer le Noeud s'il existe.

Avec un arbre de hauteur 2, on a donc fait 2 choix de direction.

Puisqu'on fait un choix conscient à chaque étage, le coût de la recherche dépends de la hauteur de l'Arbre Binaire.

Si on a une hauteur de 12, on aurait donc 12 choix à faire.

10° Si on sait où cibler cette recherche, dans le pire des cas, quel est le coût (par rapport à la taille) d'une recherche dans un Arbre Binaire Complet ? Dans un Arbre Binaire Filiforme ? Dans un Arbre Binaire quelconque ?

  1. Constant
  2. Logarithmique
  3. Linéaire
  4. Quadratique
  5. Exponentiel
  6. Factoriel

...CORRECTION...

Pour un Arbre Binaire Complet, on a un coût logarithmique puisque la hauteur de l'Arbre Binaire est de l'ordre de log2(n).

Pour un Arbre Binaire Filiforme, on a un coût linéaire puisque la hauteur est de l'ordre de la taille n.

Le coût de la recherche sur un arbre quelconque est donc compris entre le coût logarithmique et le coût linéaire.

Conclusion

Si on recherche un Noeud sans savoir où chercher, cette recherche est à coût linéaire en fonction de la taille n de l'arbre (dans le pire des cas): θ(n)

Si on recherche un Noeud en ciblant cette cherche, cette recherche est à coût linéaire en fonction de la hauteur h de l'arbre (dans le pire des cas): θ(h)

Et ça change tout car la hauteur h dépend du log2 de la taille dans un arbre binaire complet. On peut donc écrire :

  1. Qu'une recherche ciblée est en θ(log2(n)) dans un Arbre Binaire Complet
  2. Qu'une recherche ciblée est en θ(n) dans un Arbre Binaire Filiforme
  3. Que le coût d'une recherche ciblée dans un arbre quelconque est entre les deux cas précédents

Et du coup, la recherche dans un Arbre Binaire est fonction de sa hauteur, plutôt que de sa taille. On pourra ainsi facilement cibler la recherche et retrouver une recherche à coup logarithmique si l'Arbre est complet ou presque.

Avant cela, nous allons découvrir un système permettant de localiser facilement les noeuds, et pas leur contenu.

5 - Système de localisation des Noeuds

Comment faire pour trouver facilement le fils gauche du fils gauche ? Le père du père d'un noeud ?

Dans l'activité suivante, nous allons voir un moyen assez simple de localiser le noeud qui nous intéresse dans l'Arbre Binaire.

Mais il existe également un moyen permettant d'identifier les Noeuds d'un Arbre Binaire : leur associer un nombre ... binaire.

On peut ainsi donner le nombre  1  à la Racine de l'AB.

Le Noeud-Racine du sous-arbre gauche porte le numéro de la racine suivi d'un 0 : si la racine est  1  alors le noeud-fils-gauche est  10 .

Le Noeud-Racine du sous-arbre droite porte le numéro de la racine suivi d'un 1 : si la racine est  1  alors le noeud-fils-droite est  11 .

Numérotation Binaire

11° En utilisant cette notation, combien peut-on avoir de noeuds dans un AB de hauteur 2 ?

...CORRECTION...

On commence la numérotation à  1  et on pourra faire deux choix de direction et donc rajouter deux autres chiffres binaires.

On peut donc numéroter de  1  à  111 .

En décimal, on a donc des numéros de 1 à 7.

12° Combien peut-on avoir de noeud dans un AB de hauteur 7 ?

...CORRECTION...

Hauteur 7, 7 choix à faire donc 7 chiffres binaires à rajouter.

On peut numéroter de  1  à  1 1111111 .

En décimal, on a donc des numéros de 1 à 255.

Cela revient à calculer 27+1 - 1

13° Sur l'arbre proposé, rajouter les deux prochains noeuds en utilisant le système de numérotation proposé.

Numérotation Binaire

...CORRECTION...

Numérotation Binaire avec deux noeuds supplémentaires

14° Avec ce système binaire, comment trouver facilement les numéros des deux fils du noeud 14 10 ou  1110  2 ?

...CORRECTION...

En binaire, 14 se note 8+4+2 soit  1110 .

Le fils gauche est donc  1110 0 , soit 16+8+4 = 28.

Le fils droite est donc  1110 1 , soit 16+8+4+1 = 29.

15° Avec ce système binaire, par quel numéro est identifié le père du père du noeud 65 ?

...CORRECTION...

En binaire, 65 se note 64+1 soit  1000001 .

Pour trouver le père, il suffit de supprimer le 1 de droite :  100000 .

Pour trouver le père du père, il suffit de supprimer encore le chiffre 0 de droite :  10000 .

Le père du père du noeud numéro 65 est donc le numéro 16.

Implémentation d'un Arbre dans un tableau

On peut utiliser ce système pour stocker notre Arbre Binaire dans un tableau.

La Racine possède l'indice 1.

Le fils-gauche d'un noeud d'indice i possède l'indice 2*i.

Le fils-droite d'un noeud d'indice i possède l'indice 2*i+1.

Le père d'un noeud d'indice i possède l'indice i//2.

Numérotation des noeuds d'un AB

16° Avec ce système décimal, par quel numéro est identifié le père du père du noeud 40 ?

...CORRECTION...

Il suffit de diviser deux fois par 2.

Le père du noeud 40 est le noeud 20.

Le père du noeud 20 est le noeud numéroté 10.

17° Avec ce système décimal, par quel numéro est identifié le fils-droite du fils-gauche du noeud d'indice 5 ?

...CORRECTION...

On multiplie par 2 pour trouver le fils-gauche ! 2*5 = 10.

On multiplie par 2 et on rajoute 1 pour trouver le fils-droite : 10*2+1

Le noeud numéro 21 est donc le fils-droite du fils-gauche du noeud 5.

18° Avec ce système décimal, par quel numéro est identifié le fils-gauche du fils-droite du noeud d'indice 5 ?

...CORRECTION...

On multiplie par 2 et on rajoute 1 pour trouver le fils droite ! 2*5+1 = 11.

On multiplie par 2 pour trouver le fils gauche : 11*2

Le noeud numéro 22 est donc le fils-droite du fils-gauche du noeud 5.

19° Fournir l'implémentation de cet Arbre Binaire sous forme d'un tableau :

Arbre question 18

...CORRECTION...

Question 19

20° Quel est l'indice de la case qui stockera le fils-droite du noeud D :

Arbre question 18

...CORRECTION...

Le noeud D possède l'indice 14.

On calcule donc 14*2+1, soit 29.

Nous savons maintenant assez facilement trouver le fils-gauche du fils-droite du fils-gauche du nombre  101  ou 5 en décimal

  • Méthode 1 : on part de  101 , on atteint le fils-gauche  1010  puis le fils-droite  10101  puis le fils-gauche  101010 .
  • Méthode 2 : on part de 5, on atteint le fils-gauche 10 puis le fils-droite 21 puis le fils-gauche 42.

Avec une telle implémentation, vous savez maintenant localiser à temps constant un noeud par rapport à ses descendants ou ses ancêtres. Par contre, la recherche d'un élément de position inconnu reste à coût linéaire par rapport à la taille de l'arbre...

Vous allez justement découvrir dans l'activité suivante un type particulier d'Arbre Binaire (AB) : un Arbre Binaire de Recherche, un Arbre dans lequel les éléments sont positionnés en respectant une organisation qui permet de savoir ... où chercher le bon contenu.

6 - FAQ

Pourquoi pas un coût en log2(n+1) ?

Il faut se souvenir que le coût n'est pas une estimation exacte de la complexité réel d'un algorithme mais uniquement d'une estimation de la façon dont croit le nombre d'opérations lorsque le nombre de données augmente.

Ainsi si on a un nombre d'opérations égal à 10 log2(n+50), nous allons simplifier tout cela.

On commence par supprimer le facteur constant 50 : si n croît de façon importante, on pourra négliger 50 devant n.

On obtient ainsi 10 log2(n).

Ensuite, on supprime également le facteur multiplicatif : si les données augmentent de 1000 fois leur taille, passant par exemple de 100 à 100 000, on devrait comparer 10 log2(100) et 10 log2(100 000). Lorsqu'on va faire la division [10 log2(100 000)] / [10 log2(100)], le facteur 10 va disparaître de toute manière.

Au final, on écrit donc θ(log2(n)).

C'est donc pour cela qu'on passe d'un coût en θ(h) qui vaut effectivement θ(log2(n+1) pour un Arbre Complet à simplement θ(log2(n)).

Démonstration de la formule

La démonstration de la formule (2) fait référence au cours de mathématiques sur les séries.

Formule (2) : n = 2h+1 - 1

Arbre Binaire Complet

En effet :

Taille d'un arbre complet : n = 1 + 2 + 4 + ...

Taille d'un arbre complet : n = 20 + 21 + 22 + ... 2h

Or, on connaît la série suivante :

Formule de la série géométrique de l'exemple
Formule de la série des cubes

Du coup, si on remplace x par 2 et n par h, on obtient bien

n = (2h+1 - 1) / (2 - 1), soit

n = 2h+1 - 1

Prochaine étape : l'Arbre Binaire de Recherche.

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