Structures de données IFT-2000 Abder Alikacem Semaine 10 Les algorithmes de recherche Les structures arborescentes Département d’informatique et de génie

Structures de données

IFT-2000

Abder AlikacemAbder Alikacem

Semaine 10 Les algorithmes de rechercheLes structures arborescentes

Département d’informatique et de génie logiciel

Édition septembre 2009

! +

Les algorithmes de recherche

Les algorithmes de recherche La recherche séquentielle La recherche dichotomique

Complexité des algorithmes de recherche Recherche dichotomique et arborescence

La recherche séquentielle

3 1 4 2 8 14 12 11 6 9 10

recherche(3) = 1 comparaison recherche(10) = 11 comparaisons recherche(12) = 7 comparaisons recherche(13) = 11 comparaisons meilleur cas = O(1) pire cas = O(n) en moyenne = O(n/2) absences = O(n)

Données pas triées


1 2 3 4 6 8 9 10 11 12 14

recherche(1) = 1 comparaison recherche(14) = 11 comparaisons recherche(8) = 6 comparaisons recherche(13) = 11 comparaisons meilleur cas = O(1) pire cas = O(n) en moyenne = O(n/2) absences = O(n/2)

Données triées


données non triées : données présentes : O(n/2) données absentes : O(n)

données triées : données présentes : O(n/2) données absentes : O(n/2)

coût pour trier et maintenir triées !

Modèles d’implantation

tableau :

liste chaînée :

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

La recherche binaire

implantation en tableau = accès direct à n’importe quel élément

en regardant tout de suite au milieu, on peut éliminer la moitié des données

1 2 3 4 6 8 9 10 11 12 14


1 2 3 4 6 8 9 10 11 12 14

100


1 2 3 4 6 8 9 10 11 12 14

100 5


1 2 3 4 6 8 9 10 11 12 14

100 5


1 2 3 4 6 8 9 10 11 12 14

100 5

La recherche binaire : 10 ?

1 2 3 4 6 8 9 10 11 12 14

100 5


1 2 3 4 6 8 9 10 11 12 14

100 5


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 10


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7

1 2 3 4 6 8 9 10 11 12 14

7


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7

1 2 3 4 6 8 9 10 11 12 14

7

La recherche binaire : 9.5 ?

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7

1 2 3 4 6 8 9 10 11 12 14

7

La recherche binaire : 9.5 ?

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7

1 2 3 4 6 8 9 10 11 12 14

7

11

5

2

1

n

n/2

n/4

n/8

Tableau comparatif

recherche séquentielle : (données triées)• données présentes : O(n/2)• données absentes : O(n/2)

recherche binaire : (données triées)• données présentes : O(log n)• données absentes : O(log n)

Modèles d’implantation

tableau :

liste chaînée ?

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100

Structures pointées

1 2 3 4 6 8 9 10 11 12 14

0 1 2 3 4 5 6 7 8 9 10


1 2 3 4 6 8 9 10 11 12 14

0 1 2 3 4 5 6 7 8 9 10


1 2 3 4 6 8 9 10 11 12 14

0 1 2 3 4 5 6 7 8 9 10


1 2 3 4 6

8

9 10 11 12 14

0 1 2 3 4 6 7 8 9 10


1 2 3 4 6

8

9 10 11 12 14

0 1 2 3 4 6 7 8 9 10


1 2 3 4 6

8

9 10 11 12 14

0 1 2 3 4 6 7 8 9 10


1 2

3

4 6

8

9 10

11

12 14

0 1 3 4 6 7 9 10


1 2

3

4 6

8

9 10

11

12 14

0 1 3 4 6 7 9 10


1 2

3

4 6

8

9 10

11

12 14

0 1 3 4 6 7 9 10


1

2

3

4

6

8

9

10

11

12

14


1

2

3

4

6

8

9

10

11

12

14


1

2

3

4

6

8

9

10

11

12

14


1

2

3

4

6

8

9

10

11

12

14

Arbre binaire !

1

2

3

4

6

8

9

10

11

12

14

Arbre = index

1

2

3

4

6

8

9

10

11

12

14

Les structures d’arbres

Définitions Parcours d’arbres Arbres binaires complets ou feuillus Description en terme de type abstrait et implantation

Dans un tableau Par chaînage dynamique

Définitions

Un arbre orienté (appelé parfois arbre enraciné) est un graphe acyclique orienté qui vérifie les conditions suivantes:

Il existe exactement un noeud qui n'a pas de ‘ prédécesseur ’.

Ce noeud s'appelle la racine et l'ordre d'entrée de la racine est 0.

Tous les noeuds, sauf la racine, n'ont qu'un ‘ prédécesseur ’ et ils ont tous un ordre d'entrée égal à 1.

Il existe un chemin unique de la racine à chaque noeud.

A

M

B

V

R

O

N

P Q

S T

Terminologie des arbres

Parent d’un nœudParent d’un nœud (Père)(Père) : Le nœud immédiatement prédécesseur.

A

M

B

V

R

O

N

P Q

S T

Parent(Q) = {N}

Parent(R) = { }

Parent(B) = {M}


Parent d’un nœudParent d’un nœud (Père)(Père) : Le nœud immédiatement prédécesseur. Enfant(s) d’un nœud (fils)Enfant(s) d’un nœud (fils) : Le(s) nœud(s) immédiatement successeur(s)

du nœud.

A

M

B

V

R

O

N

P Q

S T

Enfant(Q) = { }

Enfants(R) = {M,N}

Enfant(B) = {V}


Parent d’un nœudParent d’un nœud (Père) (Père) : Le nœud immédiatement prédécesseur. Enfant(s) d’un nœud (fils)Enfant(s) d’un nœud (fils) : Le ou les nœuds immédiatement successeurs

du nœud. RacineRacine : Un nœud qui n’a pas de prédécesseur.

A

M

B

V

R

O

N

P Q

S T

Racine(Arbre) = {R}


Parent d’un nœudParent d’un nœud (Père) (Père) : Le nœud immédiatement prédécesseur. Enfant(s) d’un nœud (fils)Enfant(s) d’un nœud (fils) : Le ou les nœuds immédiatement

successeurs du nœud. Racine Racine : Un nœud qui n’a pas de prédécesseur. FeuilleFeuille : Un nœud qui n’a pas d’enfants.

A

M

B

V

R

O

N

P Q

S T

Feuilles(Arbre) = {S,T,Y,O,P,Q}



successeurs du nœud. Racine Racine : Un nœud qui n’a pas de prédécesseur. FeuilleFeuille : Un nœud qui n’a pas d’enfants. Ancêtre(s) d’un nœudAncêtre(s) d’un nœud : Tous les nœuds prédécesseurs jusqu’à la racine.

A

M

B

V

R

O

N

P Q

S T

Ancêtres(Q) = {N,R}

Ancêtre(R) = { }

Ancêtres(B) = {M,R}



successeurs du nœud. Racine Racine : Un nœud qui n’a pas de prédécesseur. FeuilleFeuille : Un nœud qui n’a pas d’enfants. Ancêtre(s) d’un nœudAncêtre(s) d’un nœud : Tous les nœuds prédécesseurs jusqu’à la racine. Descendant(s) d’un nœudDescendant(s) d’un nœud : Tous les nœuds successeurs jusqu’aux

feuilles accessibles par ce nœud.

A

M

B

V

R

O

N

P Q

S T

Descendant(Q) = { }

Descendants(R) = {M,N,A,…,V}

Descendant(B) = {V}




feuilles accessibles par ce nœud. Profondeur d’un nœudProfondeur d’un nœud : L’ordre du chemin à partir de la racine.

A

M

B

V

R

O

N

P Q

S T

Profondeur(Q) = 2

Profondeur(R) = 0

Profondeur(B) = 2




feuilles accessibles par ce nœud. Profondeur d’un nœudProfondeur d’un nœud : L’ordre du chemin à partir de la racine. Hauteur d’un nœudHauteur d’un nœud : Le chemin le plus long pour atteindre une feuille.

A

M

B

V

R

O

N

P Q

S T

Hauteur(Q) = 0

Hauteur(R) = 3

Hauteur(B) = 1




feuilles accessibles par ce nœud. Profondeur d’un nœudProfondeur d’un nœud : L’ordre du chemin à partir de la racine. Hauteur d’un nœudHauteur d’un nœud : Le chemin le plus long pour atteindre une feuille. Niveau d’un nœudNiveau d’un nœud : La hauteur de l’arbre moins la profondeur du nœud.

A

M

B

V

R

O

N

P Q

S T

Niveau(Q) = 3 – 2 = 1

Niveau(R) = 3 – 0 = 3




feuilles accessibles par ce nœud. Profondeur d’un nœudProfondeur d’un nœud : L’ordre du chemin à partir de la racine. Hauteur d’un nœudHauteur d’un nœud : Le chemin le plus long pour atteindre une feuille. Niveau d’un nœudNiveau d’un nœud : La hauteur de l’arbre moins la profondeur du nœud. ForêtForêt : Un ensemble d’arbre.

A

M

B

V

O

N

P Q

S T


Un arbre est soit vide ou possède une racine à laquelle est rattaché zéro ou plusieurs sous-arbres non vides.

T1

T2

Racine

Racine de T1

Racine de T2

==> structures récursives


Le nombre de sous-arbres associés à un noeud (nombre de descendants directs) est appelé le degré du noeud. Le degré d'un arbre correspond au degré le plus élevé de ses noeuds. Une chaîne (liste linéaire) est un arbre de degré 1.

b

an

i r

e

z

Le sous-arbre de racine i est l’arbre composé des descendants de i, enraciné en i On appelle aussi ce sous-arbre : fils de b

• tableau

• liste chaînée

1 2 3 4 6 8 9 10 11 12 14

Une liste est un arbre de degré 1

1 2 3 4 6 8 9 10 11 12 14

100

Arbre binaire

racine

sous-arbre de gauchesous-arbre de droite

nœuds internes

feuilles

Un arbre de degré 2 est appelé arbre binaire.

Arbres n-aire

racine

nœuds internes

feuilles

...

Un arbre de degré n est appelé arbre n-aire.

Les arbres ordonnés

Un arbre ordonné est un arbre où la position respective des sous-arbres reflète une relation d'ordre.

Exemple: l’arbre de Huffman pour la compression de données

W

U V

X Y

Z

0

0

1

1

1

1

1

0

0

0

Arbres partiellement ordonnés: le monceau

94

67

5544

42

18

12 06

La valeur de la clé d’un parent est plus grande (ou égale) à celle de ses 2 fils L’arbre est complet: tous les nœuds sont présents sauf éventuellement dans le dernier niveau. Si c’est le cas, le remplissage des nœuds dans ce niveau doit se faire de gauche à droite.

Les arbres de tri

Un arbre binaire de tri ordonne totalement les informations qu’il stocke(par clé) :

Toutes les clés de valeur inférieure ou égale à celle de la racine sont stockées dans le descendant gauche de la racine.

Toutes les clés de valeur strictement supérieure à celle de la racine sont stockées dans le descendant droit de la racine.

Tout ajout, toute suppression de nœud doit maintenir cette propriété vraie.

49

34

3020

23 5O

45

gauche

48

droit

29

24 Ajout de la valeur 49 :

Remarque :Tout ajout se fait par une feuille.

Ajoute de la valeur 24

49

24

Les arbres de recherche

Un arbre de tri est également dit de recherche à condition d’être équilibré.

Un arbre équilibré est un arbre organisé de telle manière à ce que sa profondeur soit minimale. La recherche d'un élément dans un arbre est alors logarithmique.

Critères HB[k] (height-balanced(k) tree)

HB[1] HB[2]

Les arbres équilibrés sont dits arbres AVL (du nom de leurs inventeurs Adel'son -Vel'skii Landis en 1962).

Un arbre binaire est dit équilibré lorsque la différence entre les hauteurs des fils gauche et droit de tout noeud ne peut excéder 1 en valeur absolue (si HB[1] ):|hauteur (sous-arbre droit) - hauteur (sous-arbre gauche)| 1)

Cette différence de hauteur est appelée facteur d’équilibre.

Arbres AVL - exemples

12

8

410

16

2

14

6

Un arbre AVL

12

8

410

16

2

14

6

1

Après l’ajout de 1, ce n’est plus un arbre AVL

Ces noeuds violentla condition

Arbres de recherche et algorithmique

Les arbres binaires de recherche présentent deux avantages : tri efficace car les valeurs sont maintenues ordonnées recherche efficace par dichotomie, beaucoup plus efficace que la recherche linéaire dans une liste.

template <typename X>class Arbre{ ... bool rechercher (const X& E); // est retourné : vrai si E est dans l’arbre, faux sinon

...}

Arbres de recherche et algorithmique

bool rechercher (const X& E);// est retourné : vrai si E est dans l’arbre, faux sinon

si vide => retourner fauxsinon si (E = valeur racine) => retourner vrai sinon si (E<valeur racine) => retourner rechercher dans sous-arbre gauche sinon retourner rechercher dans sous-arbre droit fsi fsifsi Si n est le nombre de nœuds et si l ’arbre est équilibré alors

la complexité de l ’algorithme de recherche dichotomiqueest de l ’ordre de log2(n).

Exemple : n=1024 => complexité ~ 10

Visite arborescente

priorité au père (pré-ordre) Les descendants d’un nœud sont traités après lui:

1. visiter la racine r ;2. visiter récursivement les enfants : v1, v2, …, vk

priorité aux fils (post-ordre) Les descendants d’un nœud sont traités avant lui:

1. visiter récursivement les enfants : v1, v2, …, vk

2. visiter la racine r ;

ordre symétrique (en-ordre)Le descendant de gauche est traité avant le nœud, le droit est traité

après lui:1. visiter l’enfant de gauche (v1)

2. visiter la racine r ;3. visiter l’enfant de droite (v2)

Parcours par niveau

L’algorithme utilise une file.

Il s’agit d’un parcours par largeur (contagion) tel que discuté dans le cours.

Dans le parcours par niveau, tous les nœuds d’un même niveau sont traités avant de descendre au niveau suivant.

/

*

log

+

-

3

*

n

1 n

1n

- * * / log 3 n 1 n + n 1

1

1.1 1.2

1.1.1 1.1.2 1.2.1 1.2.2

Adressage hiérarchique

opérations facilitées :• comparaison rapide de nœuds

• <1 ? 1.1.2>, <1.1 ? 1.2>• trouver le parent commun

• <1.1.2 ? 1.2>, <1.1 ? 1.2>• positionne le nœud dans l’arbre

Il s’agit d’adresser chaque nœud par une chaîne de caractères. La racine a commeadresse 1 , son fils gauche 1.1, son fils droit 1.2. Tout fils gauche a commeadresse l’adresse de son parent qu’on concatène 1, on concatène 2 pour les filsdroits.

Dessiner l’arbre binaire dont le parcours symétrique et le parcours en pré-ordre sont les suivants :

symétrique : A,B,D,E,L,P,S,Opré-ordre : O,S,P,L,E,D,B,A

Exercice

Exercice

Dessiner l’arbre binaire dont le parcours symétrique et le parcours en pré-ordre sont les suivants :

symétrique : D,L,P,S,E,A,O,Bpré-ordre : P,D,L,O,A,S,E,B

Opérateurs (arbres binaires)

arbre vide ? nombre de nœuds d’un arbre nombre de feuilles d’un arbre élément de la racine d’un arbre sous-arbre de gauche d’un nœud sous-arbre de droite d’un nœud hauteur à partir d’un nœud appartenance d’un élément à un arbre ajout (insertion) dans un arbre enlèvement dans un arbre










arbre vide? nombre de nœuds d’un arbre nombre de feuilles d’un arbre élément de la racine d’un arbre sous-arbre de gauche d’un nœud sous-arbre de droite d’un nœud hauteur à partir d’un nœud appartenance d’un élément à un arbre ajout (insertion) dans un arbre enlèvement dans un arbre




arbre vide? nombre de nœuds d’un arbre nombre de feuilles d’un arbre élément de la racine d’un arbre sous-arbre de gauche d’un nœud sous-arbre de droite d’un nœud hauteur à partir d’un nœud appartenance d’un élément à un arbre ajout (insertion) dans un arbre enlèvement dans un arbre ≤

≤



+



-


minimum des éléments d’un arbre (≤) maximum des éléments d’un arbre (≤) enfants d’un nœud descendants d’un nœud père (parent) d’un nœud ancêtres d’un nœud successeur d’un nœud (≤) prédécesseur d’un nœud (≤)















Implantation en tableau

1

2

3

4

6

8

9

10

11

12

14

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


1

2

3

4

6

8

9

10

11

12

14

99

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


appariement : la racine est à l’indice 1 sous-arbre de gauche est à 2*i sous-arbre de droite est à 2*i + 1 parent de l’élément d’indice i est à i/2 frère de droite est à i+1 (si i pair et i+1 ≤ N) frère de gauche est à i-1 (si i impair et i ≠ 1)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


1

2

3

4

6

8

9

10

11

12

14

9 9

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


1

2

3

4

6

8

9

10

11

12

14

1

2 3

4 5 6 7

8

9

9 10 11 12 13 14 15

9

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


1

2

3

4

6

8

9

10

11

12

14

8 3 11

2 4 10

12

1 6 9 14

1

2 3

4 5 6 7

8

9

9 10 11 12 13 14 15

9

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


Avantages : simplicité d’implantation aucun espace perdu pour les pointeurs espace pour insérer un nœud déjà disponible parcours par niveau facilité parcours des feuilles facilité

8 3 11

2 4 10

12

1 6 9 141 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Désavantages : espace perdu pour les trous


Désavantages pire cas

8 11 12 141 2 3 4 5 6 7 8 9 10 11 12 13 14 15

8

11

12

14

1

3

7

15

Arbre dégénéré vers la droite

Arbre feuillu ou complet

Arbre complet: Un arbre de degré n est dit complet lorsque tous ses niveaux, à l’exception du dernier, possède un nombre maximal de nœuds. Le dernier niveau, quant à lui, est partiellement rempli de gauche à droite, sans trou.

Arbre de degré 3 complet

99

1

2 3

4 5 6 7

8 9 11 12 14 1510 13

Arbre de degré 2 complet

Arbre binaire feuillu ou complet

indice du premier élément du niveau k ?

nombre de feuilles maximum = (n + 1) / 2

nombre de nœuds maximum = 2p – 1, p= nombre de niveaux

hauteur = log((n + 1)/ 2).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

99

1

2 3

4 5 6 7

8 9 11 12 14 1510 13

La classe Arbre (binaire)

template <typename T>class Arbre{public:

// …

private:T * tab; // ou vector<T> vint cpt; // Nombre d'éléments dans le tableau, inutile si vector

};

Implantation par tableauou vector

Implantation en tableau (2)

compaction des niveaux en conservant explicitement l’indice des

enfants de gauche et de droite d’un nœud

8 3 11

2 4 10

12

1 6 9 141 2 3 4 5 6 7 8 9 10 11 12 13 14 15

8 3 11

2 4 10

12

1 6 9 142 4 6 8 0 1

0 0 0 0

3 5 7 0 9 0 11

0 0

0

0

0

0

élément d’informationindice du sous-arbre de gaucheindice du sous-arbre de droite

Implantation en tableau (2)

Avantages : aucun trou ! pas besoin d’une sentinelle

Désavantages : espace additionnel pour l’information de contrôle (c.-à-d.

les indices des éléments enfants d’un nœud) revient à gérer une mémoire utilisée comme le tas

(«heap») problèmes d’ajouts ? d’enlèvements ?

8 3 11

2 4 10

12

1 6 9 142 4 6 8 0 1

0 0 0 0

3 5 7 0 9 0 11

0 0

0

0

0

0

Exercice

Définissez les attributs privés (modèle d’implantation) en tenant compte de cette version dans l’implantation.

La classe Arbre (binaire)

template <typename E>class Arbre{public:

//..Les méthodes publiques (i.e. les opérateurs)private:

// classe Noeudclass Noeud{ public:

E data;Noeud *gauche;Noeud *droite;int card;int hauteur; Noeud( const E&d ): gauche(0),data( d ),droite(0),hauteur(0) { }

};// Les membres donnéesNoeud * racine; //racine de l'arbrelong cpt; // Nombre de noeuds dans l'arbre// Les membres méthodes privés//...

};

...

data

Implantation par chaînage

Implantation par chaînage

Puisque chaque nœud possède au maximum deux nœuds fils, on maintient un pointeur sur chacun d’eux.

Avantages: La taille de l’arbre est dynamique. Facile d’opérer sur des pointeurs.

Inconvénients: On doit éviter les fuites de mémoire et les doubles références. On ne peut parcourir l’arbre que de la racine vers les feuilles.

Documents

Structures de données IFT-2000 Abder Alikacem Semaine 10 Les algorithmes de recherche Les structures arborescentes Département d’informatique et de génie