19 - Recherche dans un AB

⏪

⏬

⏩

1 - Log Exp

2 - Parf.Fili.

3 - Quelconques

4 - Sans hasard

5 - Localisation

6 - FAQ

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.

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

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

Choix de la convention

On considère le cas p_R = 1.

La profondeur de la racine d'un arbre est 1.
La hauteur d'un AB comportant qu'un unique Noeud est donc 1.
La hauteur d'un ABV est donc 0.

MODE COURS (cacher les questions)

1 - Fonctions réciproques : logarithme et exponentielle

⇩ ⇧ ⤊

01° Calculer ceci avec Python.


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

Que vaut log₂(2^x) visiblement ?

Correction ?

...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 log₂(2^x) = x.

02° Calculer ceci avec Python.


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

Que vaut 2^log₂(x) à priori ?

Correction ?

...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 2^log₂(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.

2 - Arbres parfaits et arbres filiformes

⇩ ⇧ ⤊

2.1 Arbre Binaire Parfait : caractéristiques

Voir

Un Arbre Binaire Parfait est un Arbre Binaire où le dernier niveau est entièrement composés de Feuilles.

Exemple avec un Arbre Binaire Parfait de hauteur 2 :

L'Arbre Binaire Parfait est la meilleure configuration en terme de réduction de la hauteur.

Pour un Arbre Binaire Parfait, la hauteur h est liée au log₂ de la taille n quelque que soit la convention. Avec la convention choisie ici, cela donne :

h = log₂(n+1) ( Formule 1)

Sur l'exemple : h = log₂(7+1)= log₂(8) = log₂(2³) = 3

Pour un Arbre Binaire Parfait, la taille n est liée à une puissance de 2 de la hauteur h quelque que soit la convention. Avec la convention choisie ici, cela donne :

n = 2^h - 1 ( Formule 2)

Sur l'exemple : n = 2^h - 1 = 2³ - 1= 8 - 1 = 7

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

h = log₂(n+1) ( Formule 1)

n = 2^h - 1 ( Formule 2)

Correction ?

...CORRECTION...

On part de cela la formule 1.

Formule (1)

h = log₂(n+1)

2^h = 2^log₂(n+1)

On sait que 2^log₂(x) = x car ces deux fonctions sont reciproques.

2^h = n + 1

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

2^h - 1 = n

On obtient bien la formule (2) :

n = 2^h - 1

04° Quelle est la taille d'un Arbre Binaire Parfait de hauteur 11 (avec la convention p_R = 1) ?

Correction ?

...CORRECTION...


>>> 2**(11) - 1
2047

Un Arbre Binaire Parfait de 11 étages possède donc 2047 Noeuds.

05° Un Arbre Binaire de 500 Noeuds peut-il être parfait ?

Correction ?

...CORRECTION...

On peut faire un raisonnement par l'absurde :

Hypothèse : on considère qu'il l'est. On peut donc utiliser la formule permettant de trouver sa hauteur :

h = log₂(n+1) ( Formule 1)


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

On tombe sur un résultat qui n'est pas un entier. C'est donc que l'hypothèse est fausse.

Conclusion : un Arbre Binaire de 500 noeuds ne peut pas être un Arbre Binaire Parfait.

Le jour de BAC ?

Pas de calculatrice !

Par contre, vous savez que :

log2(2) = 1

log2(4) = 2

log2(8) = 3

log2(16) = 4

log2(32) = 5

log2(64) = 6

log2(128) = 7

log2(256) = 8

log2(512) = 9

On voit que 501 ne fait pas partie des cas possibles.

2 Arbre Binaire Filiforme : caractéristiques

Voir

L'Arbre Binaire Filiforme est la pire configuration en terme de réduction de la hauteur.

h = n ( racine de profondeur 1)

3 - Arbres Binaires quelconques

⇩ ⇧ ⤊

3 Encadrement des caractéristiques

Voir

Ordre de grandeur de la hauteur d'un arbre (à connaître par coeur)

L'ordre de grandeur de la hauteur d'un Arbre Binaire est compris entre log₂(n) et n.

Avec la convention profondeur 1 pour la racine

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

⌈log₂(n+1)⌉ ≤ h ≤ n

h ≤ n ≤ 2^h - 1

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

Correction ?

...CORRECTION...

Encadrement avec une profondeur 1 pour la racine

⌈log₂(n+1)⌉ ≤ h ≤ n

⌈log₂(60+1)⌉ ≤ h ≤ 60

⌈log₂(61)⌉ ≤ h ≤ 60

Reste à trouver la valeur du terme de gauche, sans calculatrice...

log2(2) = 1

log2(4) = 2

log2(8) = 3

log2(16) = 4

log2(32) = 5

log2(64) = 6

On voit donc que log2(61) est compris entre 5 et 6.

En arrondissant au supérieur, on obtient 6.

6 ≤ h ≤ 60

Notons que si nous avions pris la convention profondeur 0 pour la racine, nous aurions eu :

5 ≤ h ≤ 59

07° Encadrer la taille d'un Arbre Binaire possédant une hauteur de 5 (toujours avec la convention profondeur 1 pour la racine).

Correction ?

...CORRECTION...

h ≤ n ≤ 2^h - 1

On obtient :

5 ≤ n ≤ 2⁵ - 1

5 ≤ n ≤ 32 - 1

5 ≤ n ≤ 31

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) ?

Constant
Logarithmique
Linéaire
Quadratique
Exponentiel
Factoriel

Correction ?

...CORRECTION...

On doit fouiller l'Arbre Binaire noeud par noeud.

Le coût est donc linéaire.

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

09° Répondre à ces questions :

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 ?

Combien de choix de destination à faire dans le pire des cas si on a un Arbre de hauteur 12 ?
Quel est le coût d'une recherche CIBLEE par rapport à la hauteur h d'un Arbre Binaire quelconque ?

Correction ?

...CORRECTION...

Lorsqu'on sait de quel côté descendre, on divise globalement le nombre de noeuds par deux.

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

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

Avec cet arbre de hauteur 3 (ou 2 selon la convention), on a donc fait 2 choix de direction.

Avec un arbre de hauteur 12 (ou 11 selon la convention), on a donc fait 11 choix de direction.
On a un coût linéaire par rapport à la hauteur : O(h).

10° En déduire le coût de la recherche CIBLEE dans un Arbre Binaire Filiforme puis Parfait par rapport à la taille n de l'arbre. Choisir parmi :

Constant
Logarithmique
Linéaire
Quadratique
Exponentiel
Factoriel

Correction ?

...CORRECTION...

La complexité de la recherche est O(h).

Dans le cas filiforme, h est de l'ordre de n quelque soit la convention.

La complexité de la recherche est donc O(n) et donc linéaire par rapport à n.

Dans le cas parfait, h est de l'ordre de log2(n) quelque soit la convention.

La complexité de la recherche est donc O(log₂(n)), logarithmique par rapport à n.

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

4 Coût d'une recherche dans un Arbre Binaire

Voir

Recherche classique : 𝞞(n)

Une recherche utilisant un parcours classique (en profondeur d'abord ou en largeur d'abord) est à coût linéaire en fonction de la taille n de l'arbre. Plus précisément, 𝞞(n) puisqu'on peut tomber par hasard sur la valeur lors de ce parcours.

Recherche ciblée : 𝞞(h)

Si la recherche permet de choisir entre direction gauche ou droite, la recherche est à coût linéaire en fonction de la hauteur h de l'arbre. Plus précisement, 𝞞(h) puisqu'on peut tomber sur la valeur avant d'atteindre le bas de l'arbre.

Puisque cette hauteur est fonction de la taille n de l'arbre et de la forme de l'arbre, on peut en déduire ceci :

Une recherche ciblée est en 𝞞(log₂(n)) dans un Arbre Binaire Parfait ou presque complet;
Une recherche ciblée est en 𝞞(n) dans un Arbre Binaire Filiforme ou Dégénérée.
Une recherche ciblée dans un arbre quelconque est entre les deux cas précédents mais cela donne encore 𝞞(n).

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 en créant un arbre fait pour cela : l'Arbre Binaire de Recherche.

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

5.1 Numérotation binaire des noeuds

Voir

Principe

On peut donner le numéro 1 à la Racine de l'AB.

Le Noeud-Racine d'un sous-arbre gauche porte le numéro de sa mère suivie d'un 0.

Le Noeud-Racine d'un sous-arbre droite porte le numéro de sa mère suivie d'un 1.

Exemple :

La racine est 1 (1 en décimal).
Le Noeud-Racine du sous-arbre gauche porte le numéro 10 (2 en décimal).
Le Noeud-Racine du sous-arbre droite porte le numéro 11 (3 en décimal).

Nombre de bits et nombre d'étages

Quelque soit la convention pour profondeur et hauteur, on voit que le nombre d'étages donne le nombre de bits des noeuds les plus profonds.

Ici, trois étages : trois bits au maximum.

Dans les questions ci-dessous, on prendra la convention d'une profondeur 0 pour la racine.

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

Correction ?

...CORRECTION...

Hauteur 2 avec cette convention veut dire qu'on a 3 étages (0, 1 et 2).

3 étages donc les noeuds les plus bas ont un numéro à 3 bits xxx .

On a donc 2³ - 1 = 7 noeuds différents (de 1 à 7).

12° Combien peut-on avoir de noeuds, au maximum, dans un AB de hauteur 7 ?

Correction ?

...CORRECTION...

Hauteur 7, étages de 0 à 7, donc 8 étages.

8 étages donc les noeuds les plus bas ont un numéro à 8 bits xxxx xxxx .

On a donc 2⁸ - 1 = 255 noeuds différents (de 1 à 255).

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

Correction ?

...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₁₀ ou 1110 ₂ ?

Correction ?

...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.

Les enfants du noeud 14 sont donc les noeuds 28 et 29.

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

Correction ?

...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.

On a donc simplement trouver le père du père en divisant deux fois par deux (en division euclidienne).

5.2 Implémentation d'un Arbre via un tableau

Voir

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.

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

Correction ?

...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 ?

...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 ?

...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 :

Correction ?

...CORRECTION...

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

Correction ?

...CORRECTION...

Le noeud D possède l'indice 14.

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

5.3 Localisation des parents et enfants

Voir

Pour trouver le fils-gauche du fils-droite du fils-gauche du nombre 101 ou 5 en décimal

Méthode 1 : on travaille en binaire

on part de 101,
on atteint le fils-gauche 1010 ,
puis le fils-droite 10101
puis le fils-gauche 101010 .

Méthode 2 : on travaille en décimal

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, on peut atteindre un noeud connu à temps constant.

Par contre, la recherche d'un élément de position inconnu reste à coût linéaire par rapport à la taille de l'arbre...

6 - FAQ

⇩ ⇧ ⤊

Pourquoi une complexité en log₂(n) et pas en log₂(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 log₂(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 log₂(100) et 10 log₂(100 000). Lorsqu'on va faire la division [10 log₂(100 000)] / [10 log₂(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 θ(log₂(n+1) pour un Arbre Complet à simplement 𝞗(log₂(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 = 2^h+1 - 1

En effet :

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

Taille d'un arbre complet : n = 2⁰ + 2¹ + 2² + ... 2^h

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

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

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

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

n = 2^h+1 - 1

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

⏪

⏫

⏩

19 - Recherche dans un AB

Choix de la convention

1 - Fonctions réciproques : logarithme et exponentielle

2 - Arbres parfaits et arbres filiformes

2.1 Arbre Binaire Parfait : caractéristiques

2 Arbre Binaire Filiforme : caractéristiques

3 - Arbres Binaires quelconques

3 Encadrement des caractéristiques

Ordre de grandeur de la hauteur d'un arbre (à connaître par coeur)

Avec la convention profondeur 1 pour la racine

4 - Exploration en sachant où aller

4 Coût d'une recherche dans un Arbre Binaire

Recherche classique : 𝞞(n)

Recherche ciblée : 𝞞(h)

5 - Système de localisation des Noeuds

5.1 Numérotation binaire des noeuds

Principe

Nombre de bits et nombre d'étages

5.2 Implémentation d'un Arbre via un tableau

5.3 Localisation des parents et enfants

6 - FAQ

Pourquoi une complexité en log2(n) et pas en log2(n+1) ?

Démonstration de la formule

Pourquoi une complexité en log₂(n) et pas en log₂(n+1) ?