[PDF] [PDF] INF421-a Bases de la programmation et de lalgorithmique Tas

7 oct 2005 · Tas Un tas en Java Arbres binaires de recherche Définition des tas Un arbre binaire est tassé quand tous ses niveaux sont enti`erement



Previous PDF Next PDF





[PDF] Arbres binaires, ensembles - Inria

Un contre-exemple d'arbre binaire de recherche 1 2 6 4 8 9 7 Java fournit les ensembles d'objets réalisés par des arbres équilibrés : la classe TreeSeta 



[PDF] 1 Les arbres binaires en Java

Arbres binaires Buts : – structuration des arbres binaires en Java donc mettre à distance la racine de l'arbre et disposer de deux classes, une classe Node 



[PDF] Algorithmique avancée - Arbres binaires de recherche

Un arbre binaire de recherche (ABR) est un type de données abstrait constitué d' un couple Java • Mais utilisés pour l'implémentation de Map (TreeMap) ou



[PDF] TD 8 A propos darbres binaires

Cet exercice est une suite de réflexions sur la réalisation en Java de la structure de données d'arbre binaire, une notion supposée connue Pour fixer les idées 



[PDF] Arbres - IGM

15 sept 2015 · Un arbre binaire de T est un ensemble de nœuds qui est soit vide soit composé d 'une racine Java en poss`ede une dans Swing Programme 



[PDF] Cours 2: Arbres - IGM - Université Paris-Est Marne-la-Vallée

2 Définitions 3 Parcours d'un arbre binaire Un arbre binaire est un arbre tels que tout nœud a au plus un fils gauche et Parcours d'arbres planaires en Java



[PDF] INF421-a Bases de la programmation et de lalgorithmique Tas

7 oct 2005 · Tas Un tas en Java Arbres binaires de recherche Définition des tas Un arbre binaire est tassé quand tous ses niveaux sont enti`erement



[PDF] Compter les arbres binaires - IRIF

(2) Dans un arbre binaire complet (tout nœud est d'arité 0 ou 2), En Java static int compter(Arbre a, int min, int max) { int total = 0; if (a == null) return total;

[PDF] retour ? l'unité proportionnalité

[PDF] le timbre d'un son

[PDF] le passage ? l’acte criminel

[PDF] psychologie criminelle cours pdf

[PDF] passage ? l'acte psychologie

[PDF] cours de criminologie générale pdf

[PDF] livre criminologie pdf

[PDF] tétraèdre régulier propriétés

[PDF] passage ? l'acte

[PDF] tétraèdre propriétés

[PDF] grille d'estimation de la dangerosité d'un passage ? l'acte suicidaire pondération

[PDF] intervenir auprès de la personne suicidaire ? l'aide de bonnes pratiques

[PDF] grille estimation dangerosité suicidaire

[PDF] grille d'évaluation de l'urgence suicidaire

[PDF] rapport d'intervention auprès de la personne suicidaire

TasUn tas en JavaArbres binaires de recherche

INF421-a

Bases de la programmation et de l"algorithmique

Tas & Arbres binaires de recherche

(Bloc 7 / 9)Philippe Baptiste

CNRS LIX,

´Ecole Polytechnique7 octobre 2005

Philippe Baptiste: INF421-a, Bloc 7,1/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Aujourd"hui

Tas

Un tas en Java

Arbres binaires de recherche

Philippe Baptiste: INF421-a, Bloc 7,2/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

D´efinition des tas

Un arbre binaire esttass´equand tous ses niveaux sont enti`erement remplis `a l"exception peut-ˆetre du dernier niveau, et ce dernier

niveau est rempli `a gauche.La hauteur d"un arbre tass´e `annoeuds est?log2n?.Philippe Baptiste: INF421-a, Bloc 7,3/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

D´efinition des tas d"entiers

Un tas est un arbre binaire tass´e dans lequel le contenu de chaque noeud est sup´erieur ou ´egal `a celui de ses fils23 15 12 48
5 2 7

61Philippe Baptiste: INF421-a, Bloc 7,4/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

D´efinition des tas d"entiers

?Les noeuds d"un arbre tass´e sont num´erot´es en largeur, de gauche `a droite?Ces num´eros sont des indices dans un tableau?L"´el´ement d"indicei= le contenu du noeud de num´eroi. 23
0 15 1 12 3 4 7 8 8 5 4 2 9 7 2 6 5 1

6i0123456789

a i2315712561482 Philippe Baptiste: INF421-a, Bloc 7,5/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

L"h´er´edit´e des tas d"entiers

racine : 0

p`ere dei:?(i-1)/2?fils gauche dei: 2i+ 1fils droit dei: 2i+ 2iest une feuille : 2i+ 1?nia un fils droit : 2i+ 2 23
0 15 1 12 3 4 7 8 8 5 4 2 9 7 2 6 5 1

6Philippe Baptiste: INF421-a, Bloc 7,6/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

L"h´er´edit´e des tas d"entiers

?Entre le niveau 1 eth, nous avons?h-1 i=02i= 2h-1 ´el´ements?Les indices des ´el´ements de niveauhsont compris entre 2 h-1-1 et 2h-2?Soitjune ´el´ement de niveauh,i.e.,j= 2h-1-2 +λavec

λ? {1,...,2h-2-2h-1+ 1}?Son fils droit : 2

h-2 + 2?λ= 2h-2 + 2j-2h+ 4 = 2j+ 2?Son fils gauche : 2j+ 2-1 = 2j+ 1Philippe Baptiste: INF421-a, Bloc 7,7/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Ins´erer dans un tas

Ins´ererv?L"´el´ement est ajout´e

comme contenu d"un nouveau noeud `a la fin du dernier niveau de l"arbre?Tant que le contenu du p`ere est plus petit quev, le contenu du p`ere est descendu vers le fils.?Remplacer parvle dernier contenu abaiss´e. 23
0 15 1 12 3 4 7 8 8 5 4 2 9 21
10 7 2 6 5 1

6Philippe Baptiste: INF421-a, Bloc 7,8/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Supprimer dans un tas (la racine)

On enl`evela racinedu tas

?Retasser :le contenu du noeud le plus `a droite du dernier niveau est transf´er´e vers la racine?Comparer :la racine est compar´ee au + grand des fils ?Si fils≥p`ere remonter et remplacer le contenu du p`ere?it´erer Philippe Baptiste: INF421-a, Bloc 7,9/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Supprimer dans un tas (la racine).

16 0 15 1 8 3 2 7 4 8 14 4 7 9 10 10 11 2 9 5 3

6Philippe Baptiste: INF421-a, Bloc 7,10/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Supprimer dans un tas (la racine).

10 0 15 1 8 3 2 7 4 8 14 4 7 9 11 2 9 5 3

6Philippe Baptiste: INF421-a, Bloc 7,11/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Supprimer dans un tas (la racine).

15 0 14 1 8 3 2 7 4 8 10 4 7 9 11 2 9 5 3

6Philippe Baptiste: INF421-a, Bloc 7,12/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Insertion / suppression : complexit´e

La complexit´e des op´erations de suppression et d"insertion est

major´ee par la hauteur de l"arbreLa hauteur d"un arbre tass´e `annoeuds est?log2n?Insertion et suppression enO(logn)Philippe Baptiste: INF421-a, Bloc 7,13/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Aujourd"hui

Tas

Un tas en Java

Arbres binaires de recherche

Philippe Baptiste: INF421-a, Bloc 7,14/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Un tas en Java

?Un tableau pour repr´esenter l"arbre. Rappel : ?Les noeuds d"un arbre tass´e sont num´erot´es en largeur, de

gauche `a droite?Ces num´eros sont des indices dans un tableaua?L"´el´ement d"indicei= le noeud de num´eroi?Trois m´ethodesmaximum(),inserer(),supprimer()Philippe Baptiste: INF421-a, Bloc 7,15/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Un tas en Java

classTas { int[] a; intnTas = 0;

Tas(intn) {

nTas = 0; a =newint[n]; }intmaximum() { returna[0]; }intpere(inti) { return(i - 1) / 2 }intgauche(inti) { return2 * i + 1; }intdroite(inti) { return2 * i + 2; }booleanestUneFeuille(inti) { return(2 * i + 1≥nTas); }booleanaUnFilsDroit(inti) { return(2 * i + 2 < nTas); Philippe Baptiste: INF421-a, Bloc 7,16/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Un tas en Java

voidajouter(intv) { inti = nTas; a[i] = a[pere(i)]; i = pere(i); a[i] = v; Philippe Baptiste: INF421-a, Bloc 7,17/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Un tas en Java

voidsupprimer() { nTas = nTas - 1; a[0] = a[nTas];intv = a[0]; inti = 0; while(!estUneFeuille(i)) { intj = gauche(i); if(aUnFilsDroit(i) && a[droite(i)] > a[gauche(i)]) j = droite(i);if(v≥a[j])break; a[i] = a[j]; i = j; a[i] = v; Philippe Baptiste: INF421-a, Bloc 7,18/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Trier avec des tas

?n´el´ements `a trier?Les mettre dans le tasn×O(logn)?Et les retirer!n×O(logn)staticvoidtriParTas(int[] a) {

intn = a.length;

Tas t =newTas(n);

for(inti = 0; i < n; i++) t.ajouter(a[i]);for(inti = n - 1; i≥0; --i) {intv = t.maximum(); t.supprimer(); a[i] = v; }return; Philippe Baptiste: INF421-a, Bloc 7,19/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Un tas en Java 0

100
200
300
400
500
600

0 10000 20000 30000 40000 50000 60000 70000

cpu (ms) tailleComparaison exprimentale de 3 tris (moyenne sur 10 tirages aleatoires) TAS

FUSION

SYSTEMPhilippe Baptiste: INF421-a, Bloc 7,20/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

R´esum´e sur les Tas

Structure de donn´ees utile pour

?trier des donn´ees ?g´erer un ensemble de donn´ees en ne faisant ?qu"ajouter des donn´ees ?que retirer de l"ensemble des donn´ees la plus grande Toutes les op´erations enO(logn)Attention : Un tas n"est pas une "bonne" structure de donn´ee pour rechercher un ´el´ement quelconque Philippe Baptiste: INF421-a, Bloc 7,21/ 45CNRS LIX,´Ecole Polytechnique

TasUn tas en JavaArbres binaires de recherche

Aujourd"hui

quotesdbs_dbs44.pdfusesText_44