[PDF] Structures de données et algorithmes

View - Download Structures de données et algorithmes

Previous PDF

Next PDF

Structures de données et

algorithmes

Chapitre 4

Les arbres

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.24 Les arbres lNous introduisons dans ce chapitre le TDA : arbres binaires lCe TDA est intéressant pour plusieurs raisons : -Les arbres de recherche binaire permettent d'insérer, de retrouver ou de supprimer les éléments O(log N) au lieu de O(N). -L'algorithme de tri " Treesort » est le plus rapide des algorithmes de tri conventionnel et il est basé sur un arbre de recherche binaire. -Pour représenter des files de priorité ou des files d'attente, l'arbre en épi est très bien adapté. Ce type d'arbre est aussi à la base d'un autre algorithme de tri efficace, le " Heapsort ». -Un autre aspect important est l'efficacité des arbres d'expression pour les constructions mathématiques. Ils permettent d'évaluer sans ambiguïté les expressions algébriques et de faire du calcul symbolique. GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.34 Les arbres4.1 Terminologie des arbres lTous les arbres sont hiérarchiques de nature. Intuitivement, lahiérarchie signifie que dans un arbre existe une relation " père-fils» entre les noeuds. S'il existe un arc orienté de nvers m, alors nest le père de met mest le fils de n. Par exemple : B et C sont des fils de A et B est le père de D, Eet FA BC DFE GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.44 Les arbres4.1 Terminologie des arbres lLes enfants du même parent sont dits frères. lDans un arbre, chaque noeud possède au plus un parent et il y a exactement un noeud, nommé racine de l'arbre, qui n'a pas de père. Ici A est la racine. lLes noeuds qui ne possèdent pas de fils sont appelés feuille de l'arbre. Les feuilles de l'arbre montré ici sont C, D, E et F.

lLa relation " père-fils» entre les noeuds d'un arbre peut être généralisée à la

relation ancêtre et descendant. Dans cet exemple, A est un ancêtre de D et D est un descendant de A. Attention, ce ne sont pas tous les noeuds qui sont liés par cette relation, par exemple, les noeuds B et C ne sont pas reliés par cette relation. Par contre, la racine de n'importe quel arbre est l'ancêtre de tous les autres noeuds.A BC DFE GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.54 Les arbres4.1 Terminologie des arbres lUn sous-arbresd'un arbre est l'ensemble de n'importe quel noeud de l'arbre et tous ses descendants. Le sous-arbredu noeud nest le sous-arbredont la racine est un fils de n. Par exemple : le sous-arbrepossédant B comme racine est un sous-arbre du noeud AA BC DFEB DFE GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.64 Les arbres4.1 Terminologie des arbres lPuisque les arbres sont hiérarchique de nature, on peut alors les utiliser pour représenter l'information qui, elle-même est hiérarchique. Par exemple, une carte d'organisation ou un arbre généalogique.Président VP

ManufacturingVP

PersonnelVP

MarketingDirector

SalesDirector

Media relationCaroline

RoseJosephJohnJacqueline

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.74 Les arbres4.1 Terminologie des arbres lUn arbre binaire est un arbre dans lequel chaque noeud possède auplus deux fils. L'arbre généalogique présenté plus tôt en est un bonexemple contrairement à la carte d'organisation (qu'on nomme arbre n-aire). lVoici la définition formelle d'un arbre binaire : -Un ensemble T d'éléments, appelés noeuds, est un arbre binaire si, soit: lT est vide lT est partitionné en trois ensembles disjoints : -Un élément singulier r(sa racine) -Deux ensembles sont des arbres binaires, nommés sous-arbresgauche et droit de r -Ceci peut être schématisé par : T est un arbre binaire si, soit : lT ne possède aucun noeud lT est de la forme :r

TgaucheTdroit

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.84 Les arbres4.1 Terminologie des arbres lConsidérer les exemples ci-dessous d'évaluations des expressions arithmétiques, pour voir comment sont utilisés les arbres binaires pour représenter les données dans une forme hiérarchique. a - b- ab a - b / c- a/ bc(a - b) * c* c ab- GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.94 Les arbres4.1 Terminologie des arbres lUn arbre de recherche binaire est un arbre binaire ordonné suivant les valeurs associées à ses noeuds. Pour chaque noeud n, un arbre de recherche binaire satisfait les trois propriétés suivantes : -La valeur du noeud nest plus grande que toutes les valeurs de son sous-arbre gauche (Tgauche). -La valeur du noeud nest plus petite que toutes les valeurs de son sous-arbredroit (Tdroit). -Tgaucheet Tdroitsont tous les deux des arbres de recherche binaires. lComme on le remarque, ce type d'arbre organise les données de telle façon que la recherche d'un élément particulier devienne facile.Jane

EllenNancyWendyAlanTomBob

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.104 Les arbres4.1 Terminologie des arbres lLes arbres apparaissent sous plusieurs formes. Dans l'exemple suivant, malgré qu'ils aient le même nombre de sommet (7), leurs structures sont complètement différentes. lLa hauteur d'un arbre est la distance entre la racine et la feuille la plus lointaine. Dans les exemples suivants, les hauteurs des arbres sont respectivement 3, 5 et 7.a defgbca e f gdbca e f gc db GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.114 Les arbres4.1 Terminologie des arbres lLa hauteur d'un arbre général T, en terme de niveau de noeuds, est maintenant définie comme suit : -Si Test vide alors sa hauteur est 0 -Si Tn'est pas vide, alors sa hauteur est égale au niveau maximum de ses noeuds lIl est convenable d'utiliser une définition récursive pour calculer la hauteur d'un arbre binaire : -Si Test vide, alors sa hauteur est 0 -Si Tn'est pas vide alors la hauteur de Tpeut être définie comme un plus la hauteur du plus grand sous-arbre Hauteur(T) = 1 + max( Hauteur(Tgauche), Hauteur(Tdroit) ) GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.124 Les arbres4.1 Terminologie des arbres lUn arbre binaire plein de hauteur hpossède toutes ses feuilles au niveau h, et tous les noeuds qui sont au niveau inférieur à h possèdent deux enfants. L'arbre suivant est un arbre plein de hauteur 3. lVoici une définition convenable d'un arbre binaire plein : -Si Test vide, alors Test un arbre binaire plein de hauteur 0 -Si Tn'est pas vide et possède une hauteur h > 0, alors Test un arbre binaire plein si les deux sous-arbresde la racine sont des arbres binaires pleins de hauteur h -1 GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.134 Les arbres4.1 Terminologie des arbres lUn arbre binaire complet de hauteur hest un arbre binaire qui est plein jusqu'au niveau h -1, avec le niveau hrempli de gauche à droite. lPlus formellement, un arbre binaire Tde hauteur hest complet :

1.Si tous les noeuds du niveau h -2 et moins possèdent deux enfants

2.Si un noeud possède un descendant droit et au niveau h, toutes les feuilles de son

sous-arbregauche sont de niveau h. lNoter que si un arbre binaire est plein, il est forcément completA CompletBPas complet : propriété 1CPas complet : propriété 2 GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.144 Les arbres4.1 Terminologie des arbres lUn arbre binaire est équilibré si la hauteur du sous-arbredroit de n'importe quel noeud diffère de la hauteur du sous-arbregauche d'au plus 1 lUn arbre binaire est parfaitement équilibré si le sous-arbredroit et le sous-arbre gauche de chaque noeud possèdent la même hauteur lNoter qu'un arbre binaire complet est équilibré et qu'un arbre binaire plein est parfaitement équilibré. Inversement, les arbres équilibrés ne sont pas forcément

complets.Arbre binaire équilibréArbre binaire parfaitement équilibréArbre binaire non équilibré

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.154 Les arbres4.2 Responsabilités du TDA arbres binaires

lResponsabilités globales -Rendre un arbre vide -Vérifier si un arbre est vide -Calculer la taille courante d'un arbre binaire -Calculer la hauteur courante d'un arbre binaire -Copier un arbre binaire dans un autre arbre binaire -Copier le sous-arbregauche dans un autre arbre binaire -Copier le sous-arbredroit dans un autre arbre binaire -Appliquer les différents parcours d'un arbre

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.164 Les arbres4.2 Responsabilités du TDA arbres binaires

lResponsabilités locales -Retrouver, insérer et supprimer un noeud d'un arbre binaire lUn problème intéressant, comment peut-on placer des

éléments dans un arbre binaire?

-Une possibilité est de stocker les éléments de l'arbre selon l'ordre de leurs valeurs -Une deuxième possibilité pour stocker un élément est de spécifier sa position dans l'arbre

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.174 Les arbres4.2 Responsabilités du TDA arbres binaires

lÀ partir de l'arbre de gauche suivant on désire insérer un noeud de valeur Rà la position 13, qui donne l'arbre de droite lPour que l'insertion ait un sens, il faut que le parent de la position en question existe. Par exemple on ne peut insérer un élément dansla position 10 parce qu'il n'y a pas de noeud à la position 5S 8H 12D 14L 15I 4O 6N 7T 2A 3E 1S 8H 12R 13D 14L 15I 4O 6N 7T 2A 3E 1

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.184 Les arbres4.2 Responsabilités du TDA arbres binaires

lUne autre complication apparaît quand à la suppression d'un élément. Si un élément non feuille de l'arbre est supprimé, comment doit-on restructurer l'arbre? Imaginons que nous désirons enlever l'élément à la position 1 de l'arbre suivant. lOn ne sait pas si c'est B ou C qui sera la nouvelle racine, à moins qu'on connaisse la relation entre les élémentsD 4E 5F 6G 7B 2C 3A 1

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.194 Les arbres4.3 Caractéristiques du TDA arbre binaire

lDans un cadre général, les opérations d'insertion, de suppression et de consultation constituent le sujet de l'organisation des données. lLes TDA tels que les piles et les files sont tous orientés suivant le critère position. Ainsi, les différentes opérations sont de la forme : -Actionà la i-èmeposition dans la structure de données Où l'action peut être l'insertion, la suppression et la consultation lDans ce chapitre, nous avons introduit un TDA orienté vers les valeurs et dont les opérations sont de la forme : -Actiond'une donnée de valeur xdans la structure de données où, encore une fois, l'action peut être une insertion, suppression ou consultation

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.204 Les arbres4.4 Implantation d'un arbre binaire

lIl y a deux façon possibles d'implanter les arbre binaires. Une possibilité qui utilise les pointeurs ou l'autre qui utilise les tableaux. lImplantation basée sur les pointeurs#definemaxlength20 /* longueur max d'un nom */ typedefstruct_node { char Name[maxlength]; _node *LChild; /* Pointeurversfilsgauche */ _node *RChild; /* Pointeurversfilsdroit*/ }Node;

Node*T; /* Pointeur vers la racine de l'arbre */

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.214 Les arbres4.4 Implantation d'un arbre binaireLChildRChildNameT

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.224 Les arbres4.4 Implantation d'un arbre binaire

lImplantation basée sur les tableaux. On utilise les indices du tableau pour indiquer les noeuds fils de l'arbre comme le spécifie la définition suivante : #definemaxnode100 /* nombre max de noeuds */ #definemaxlength20 /* longueur max d'un nom */ struct{ char Name[maxlength]; intLChild; /* Indicedufilsgauche */ intRChild; /* Indicedufilsdroit*/ }BinTree[maxnode]; intT, Free; /*Indice de la racine et de la liste libre*/

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.234 Les arbres4.4 Implantation d'un arbre binaire

lL'indice T indique la racine de l'arbre. lComme l'arbre change à cause des insertions et suppressions, les noeuds peuvent ne pas être dans un ordre consécutif dans l'arbre. C'est pourquoi il faut établir une liste de noeuds disponibles. À chaque insertion et suppression il est important de consulter et mettre à jour cette liste. lL'indice Freeindique le début de la liste vide.LChildRChildNameArbre

23Jane

145Bob

267Tom

300Alan

400Ellen

500Nancy

600Wendy

7098
0109
1018
TFree GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.244 Les arbres4.5 Parcours des arbres binaires lLa définition d'un arbre binaire met en évidence sa nature récursive. lAinsi, en tenant compte de cette définition, on peut construire un algorithme de parcours récursif comme suit :

Traverse(T)

/* Parcours de l'arbre binaire T */ if (T n'estpas vide)

Traverse(sous-arbregauche de T);

Traverse(sous-arbredroitde T);

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.254 Les arbres4.5 Parcours des arbres binaires lPour afficher le contenu de l'arbre pendant son parcours, il existe trois possibilités d'ordre d'affichage : -Avant de parcourir les deux sous-arbresde T -Après avoir parcouru le sous-arbregauche de T, mais avant de parcourir le sous-arbredroit de T -Après avoir parcouru les deux sous-arbresde T lCes algorithmes de parcours sont nommés par conséquent -preorder -inorder -postorder GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.264 Les arbres4.5 Parcours des arbres binaires lL'algorithme de parcours preorder:Preorder(T) /* Parcours de l'arbre binaire T */ if (T n'est pas vide) {

Imprime la donnée de la racine de T;

Preorder(sous-arbregauche de T);

Preorder(sous-arbredroitde T);

lLe parcours preorderde l'arbre suivant donne

60 -20 -10 -40 -30 -50 -70

lCorrespond à la notation préfixée305010 34020

564270

760
1 GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.274 Les arbres4.5 Parcours des arbres binaires lL'algorithme de parcours inorder:Inorder(T) /* Parcours de l'arbre binaire T */ if (T n'est pas vide) {

Inorder(sous-arbregauche de T);

Imprimela donnéede la racinede T;

Inorder(sous-arbredroitde T);

lLe parcours inorderde l'arbre suivant donne

10 -20 -30 -40 -50 -60 -70

lCorrespond à l'ordre des valeurs305010 14020

354270

760
6 GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.284 Les arbres4.5 Parcours des arbres binaires lL'algorithme de parcours postorder:Postorder(T) /* Parcours de l'arbre binaire T */ if (T n'est pas vide) {

Postorder(sous-arbregauche de T);

Postorder(sous-arbredroitde T);

Imprimela donnéede la racinede T;

lLe parcours postorderde l'arbre suivant donne

10 -30 -50 -40 -20 -70 -60

lCorrespond à la notation postfixée305010 14020

234570

660
7 GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.294 Les arbres4.5 Parcours des arbres binaires

lOn peut facilement implanter les trois algorithmes de parcours en langage C. L'implantation basée sur les pointeurs de l'algorithme de la fonction inorderapparaîtra comme suit :voidInorder(Node*T)

/* Parcours de l'arbre binaire T */ if (T) {

Inorder(T->LChild);

printf("%s\n", T->Name);

Inorder(T->RChild);

lOn peut aussi envisager une fonction non récursive en se basant sur les piles (voir p.132, Notes de cours, M. Cheriet)

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.304 Les arbres4.6 Les descendants du TDA arbres binaires

lNous étudions dans cette section trois descendants du TDA arbresbinaires :

-Les arbres de recherche binaire. Ils sont ordonnés de telle façon que le temps moyen d'une insertion, suppression ou de recherche soit seulement O(log N). Ils sont notamment utilisés dans les situations où les insertions et les suppressions sont aléatoires.

-Les arbres organisés en épi sont ordonnés d'une manière assez spéciale, de telle façon qu'ils soient commode pour :

lLes pires cas de tri lLes files de priorité lLes files d'attente

-Les arbres d'expression offrent une bonne façon de représenter une expression arithmétique dont les opérateurs sont binaires, c'est-à-dire qu'ils possèdent deux opérandes. Cependant, on peut facilement appliquer des opérations arithmétiques sur les expressions, telles que les dérivées symboliques ou les intégrales.

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.314 Les arbres4.6 Les descendants du TDA arbres binaires

lLes arbres de recherche binaire. lOn commence par une définition récursive de ces derniers : -Un arbre de recherche binaire T est une arbre binaire tel que T est vide ou : lTout élément dans le sous-arbregauche de Test inférieur à l'élément racine de T lTout élément dans le sous-arbredroit de Test supérieur à l'élément racine de T lLes sous-arbresgauche et droit sont des arbres de recherche binaire lRemarque : les éléments dupliqués ne sont pas permis dans les arbre de recherche binaire

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.324 Les arbres4.6 Les descendants du TDA arbres binaires

lVoici un exemple d'arbre de recherche binaire

lUn parcours inorderd'un arbre de recherche binaire accède aux éléments dans un ordre croissant. Nous avons, pour l'affichage de cet exemple :

15 -25 -28 -30 -32 -36 -37 -58 -61 -68 -7558

3775
61
6825
3015
3228
36

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.334 Les arbres4.6 Les descendants du TDA arbres binaires

lUn arbre de recherche binaire est appelé ainsi parce que la recherche d'un élément se fait comme dans une recherche dichotomique lorsque l'arbre est dans une situation parfaitementéquilibrée,.

lLes arbres de recherche binaires servent le même but que les listes (tableaux) ordonnées, ils donnent une structure permettant de trier les éléments dans l'ordre.

lComme on va le voir, un arbre de recherche binaire est généralement plus efficace qu'une liste ordonnée pour l'insertion et la suppression d'éléments58

152180

229872

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.344 Les arbres4.6 Les descendants du TDA arbres binaires

lLes responsabilités locales d'un arbre de recherche binaire sont: -Insérer un élément -Supprimer un élément -Retrouver un élément

lCes opérations sont basées sur l'ordre des éléments et non sur leurs positions dans l'arbre

lLes définitions des fonctions qui suivent sont basées sur l'implantation des arbres sous forme de pointeur

GPA665 -Automne 2002© Mohamed Cheriet, ing., Ph. D.354 Les arbres4.6 Les descendants du TDA arbres binaires

lLa procédure de l'insertion -Si un arbre est vide, alors Itemest inséré à la racine.

-Sinon Itemest inséré soit dans le sous-arbregauche ou le sous-arbredroit, suivant que Itemest inférieur ou supérieur à la racine

InsertItem(Root, Item)

if (!Root) {

InsertAtRoot(Root, Item);

}else{ if (Item < Root->Item) {

InsertItem(Root->LChild);

}else{

InsertItem(Root->RChild);

}InsertAtRoot(Root, Item)quotesdbs_dbs28.pdfusesText_34

[PDF] calculer la hauteur d'une pyramide sans le volume

[PDF] hauteur pyramide egypte

[PDF] calculer la hauteur de la pyramide du louvre

[PDF] comment calculer la hauteur d'une pyramide 4eme

[PDF] calculer la hauteur d'une pyramide avec thales

[PDF] comment calculer le perimetre d un rectangle sur scratch

[PDF] comment calculer l'air d'un rectangle sur scratch

[PDF] quelle est l'aire d'un carré

[PDF] limite suite géométrique terminale es

[PDF] trigonométrie calculer une longueur avec un angle

[PDF] soh cah toa calculator

[PDF] norme de u+v

[PDF] comment calculer la hauteur relative d'un triangle

[PDF] hauteur relative d'un triangle isocèle

[PDF] hauteur relative d'un parallélogramme