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] 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 BaptisteCNRS LIX,
´Ecole Polytechnique7 octobre 2005
Philippe Baptiste: INF421-a, Bloc 7,1/ 45CNRS LIX,´Ecole PolytechniqueTasUn tas en JavaArbres binaires de recherche
Aujourd"hui
TasUn tas en Java
Arbres binaires de recherche
Philippe Baptiste: INF421-a, Bloc 7,2/ 45CNRS LIX,´Ecole PolytechniqueTasUn 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 dernierniveau 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 485 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. 230 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 PolytechniqueTasUn tas en JavaArbres binaires de recherche
L"h´er´edit´e des tas d"entiers
racine : 0p`ere dei:?(i-1)/2?fils gauche dei: 2i+ 1fils droit dei: 2i+ 2iest une feuille : 2i+ 1?nia un fils droit : 2i+ 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 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 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 ?n´el´ements `a trier?Les mettre dans le tasn×O(logn)?Et les retirer!n×O(logn)staticvoidtriParTas(int[] a) {
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
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 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 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
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