Cours sur les arbres binaires

Description

-1-INF 421 — 07 Luc MarangetArbres binaires,[e-mail]://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-2-Ensembles◮ Avec des listes,⊲ Non-tri´ees, tri´ees.◮ Avec des arbres,⊲ Quelconques, ´equilibr´es.◮ Un cas particulier, le tas.-3-R´ealisation des ensembles avec les listesOn peut repr´esenter le ensembles par des listes.Il suffit de maintenir la condition :Les ´el´ements d’un ensemble sont deux a` deux distincts.Il faut donc pouvoir d´eterminer l’´egalit´e de deux ´el´ements.Dans la suite, nos ´el´ements sont des int, mais cela pourraitfacilement ˆetre des objets quelconques (par red´efinition de lam´ethode equals des Object).-4-La classe des listes (d’entiers)Air connu...class List {int val ;List next ;List (int val, List next) {this.val = val ; this.next = next ;}}-5-Op´erations ´el´ementaires◮ Test d’appartenance.static boolean mem(int x, List p) {for ( ; p != null ; p = p.next) {if (x == p.val) return true ;}return false ;}◮ Ajoutstatic List add(int a, List p) {if (mem(a, p)) {return p ;} else {return new List (a, p) ;}}-6-Op´eration ensembliste : union◮ R´ecursif.static List union(List p, List q) {if (p == null) {return q ;} else {return add(p.val, union(p.next, q)) ;}}◮ It´eratif.static List union(List p, List q) {List r = q ;for ( ; p != null ; p = p.next) {r = add(p.val, r) ;}return r ;}-7-Bilan des couˆtQuel est alors le couˆt asymptotique dans ...

Informations

• Publié par: Vawyor
• Nombre de lectures: 54
• Langue: Français

Extrait

-1-

INF 421 — 07

Luc Maranget

Arbres binaires, ensembles

[e-mail] http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/

-2-

◮

◮

◮

Ensembles

Avec des listes,

⊲.seeirtees,tri´Non-´

Avec des arbres,

⊲nqcoelQ´uibilesr´ ues, equ .

Un cas particulier,le tas.

-3-

Re´alisationdesensemblesavecleslistes

Onpeutrepre´senterleensemblespar des listes.

Il suffit de maintenir la condition :

Lese´le´mentsd’unensemblesontdeux`adeuxdistincts.

Ilfautdoncpouvoird´eterminerl’e´galit´ededeux´el´ements.

Danslasuite,nos´ele´mentssontdesint, mais cela pourrait facilementeˆtredesobjetsquelconques(parrede´finitiondela m´ethodeequalsdesObject).

-4-

Air connu. . .

La classe des listes (d’entiers)

classList{ intval; List next;

List(intval,List next) { this.val=val;this.next } }

=

next

;

-5-

Operations´ele´mentaires ´

◮Test d’appartenance. static booleanmem(intx,List p) { for( ;p!=null;p=p.next) { i f(x==p.val)return true; } return false; }

◮Ajout staticList add(inta,List p) { i f(mem(a,p)) { returnp; }else{ return newList(a,p) ; } }

-6-

Op´erationensembliste:union

◮sif.ceru´R staticList union(List p,List q) { i f(p==null) { returnq; }else{ returnadd(p.val,union(p.next,q)) ; } }

◮.I´tretafi staticList union(List p,List q) { List r=q; for( ;p!=null;p=p.next) { r=add(p.val,r) ; } returnr; }

-7-

Bilandescoˆut

Quelestalorslecoˆutasymptotiquedanslecaslepire:

◮Du test d’appartenance ?O(nepsnrea`’le´hcce)(om,cerptsle appels de fonction).

◮De l’ajout ?O(n) (comme

mem).

◮De l’union (de deux ensembles de cardinauxnetm) ? O(n×(n+m)) (nfoisadd).

-8-

Uneide´e

Normaliserleslistes:repre´senterunensembleparlalistetrie´es (ordrecroissant)desese´l´ements. Appartenance

`nem´ethodeunpeu memou u

Onpeututiliserl’ancienneme´thodemem`ou me´li´ a oree. static booleanmem(intx,List p) { i f(p==null||x<p.val) { return false; }else{ returnp.val==x||mem(x,p.next) ; } }

-9-

Ajout et union

◮nsercf.isorttion.)seInt?ouanndiorttsilenus(ee´irteAj

◮.innoUoidnF?sueuedisxlstte´eric(seem.fsegr)tro

Bilandescoˆuts

mem add union

ListeO(n)O(n)O(n 2 ) Listetri´eeO(n)O(n)O(n)

Remarquer’Lminatiomentpl´e✭eeletsi´irt✮ovafra´eontiseriopl’ ensembliste,maisn’am´eliorepaslesautresop´erations.

-10-

Repr´esenterlesensemblesaveclesarbres

Ond´efinitlesarbres binaires de recherche:

◮L’arbre vide est un ABR, ses clefs sont∅.

◮SiT 0 etT 1 sont des ABR, de clefs respectivesC 0 etC 1 et :

⊲ xmajore (strictement) toutes les clefs deC 0 ;

⊲ xminore (strictement) toutes les clefs deC 1 ;

alors (T 0  x T 1 ) est un ABR et ses clefs sontC 0 ∪ {x} ∪C 1 .

-11-

Un

exemple

1

d’arbre

4

5

binaire

6

7

de

8

recherche

9