[PDF] Arbres binaires de recherche [br] Algorithmique

View - Download Arbres binaires de recherche [br] Algorithmique

Previous PDF

Next PDF

Arbres binaires de recherche [br]

Algorithmique

Karine Zampieri, Stephane Riviere

UniscielalgoprogVersion 21 mai 2018

Table des matieres

1 Denition, Parcours, Representation

2

2 Recherches

4

2.1 Recherche d'un element

4

2.2 Minimum et maximum

5

2.3 Successeur et predecesseur

5

3 Insertion d'un element

8

4 Suppression d'un element

9

5 Conclusion

1 2 Arbres binaires de rechercheMots-ClesArbres binaires de recherche RequisAxiomatique imperative, Recursivite des actions, Complexite des algorithmes,

Arbres enracines

Diculte• • ◦Introduction

Unarbre binaire de rechercheest une structure de donnee qui permet de represen- ter un ensemble de valeurs si l'on dispose d'une relation d'ordre sur ces valeurs. Les operations caracteristiques sont l'insertion, la suppression et la recherche d'une valeur. Ces operations sont peu co^uteuses si l'arbre n'est pas trop desequilibre. En pratique, les valeurs sont des cles permettant d'acceder a des enregistrements. Ce module les decrit puis denit les operations caracteristiques (recherche, insertion, suppression). 1 Unisciel algoprog { br00cours-texte, May 21, 20182

1 Denition, Parcours, RepresentationDenition d'un ABR

Unarbre binaire de recherche(abrege ABR) est un arbre binaire veriant la propriete suivante : soientxetydeux noeuds de l'arbre : •Siyest un noeud du sous-arbre droit dexalorscle(y)≥cle(x)Exemple L'arbre suivant est un ABR : pour tout noeudpdeA, la valeur depest strictement plus grande que les valeurs gurant dans son sous-arbre gauche et strictement plus petite que les valeurs gurant dans son sous-arbre droit.Remarque La denition suppose donc qu'une valeur n'appara^t au plus qu'une seule fois dans un arbre de recherche.Attention Bien que dierents, ces deux arbres ABRcontiennentexactementles m^emes valeurs.6 3 247
13 915
18 17206
3 247
13 915
17 18 20 Unisciel algoprog { br00cours-texte, May 21, 20183Parcours d'un ABR Le parcours inxe fournit la suite ordonnee des cles :Representation d'un ABR Un noeud sera representee par les champs :étiquette,filsdroit,filsgauche,père.Champ pere Il permet de traverseriterativementun ABR. Il permet egalement la recherche du successeuretpredecesseurd'un noeud. Unisciel algoprog { br00cours-texte, May 21, 20184

2 Recherches

2.1 Recherche d'un elementPrincipe

La recherche d'une valeur dans un ABR consiste, en partant de la racine, a parcourir une branche en descendant chaque fois sur le ls gauche ou sur le ls droit selon que la cle portee par le noeud est plus grande ou plus petite que la valeur cherchee. La recherche s'arr^ete des que la valeur est rencontree ou que l'on a atteint l'extremite d'une branche (le ls sur lequel il aurait fallu descendre n'existe pas).Algorithme de recherche Recherche d'une valeurka partir d'un noeudxd'un ABR :ABRRecherche(x,k)

DébutSix= Nil AlorsRetournerFaux

Sinon

Si k= cle (x)AlorsRetournerVrai

Sinon Si k< cle (x)AlorsRetournerABRRecherche(gauche(x),k)Sinon

RetournerABRRecherche(droit(x),k)FinSi

Fin Unisciel algoprog { br00cours-texte, May 21, 20185

2.2 Minimum et maximumPrincipe

Pour acceder a la cle la plus petite (resp. la plus grande) dans un ABR, il sut de descendre sur le ls gauche (resp. le ls droit) autant que possible. Le dernier noeud visite qui n'a pas de ls gauche (resp. ls droit), porte la valeur la plus petite (resp. la plus grande) de l'arbre.Algorithme Minimum Recherche du minimum a partir d'un noeudxd'un ABR :ABRMinimum(x) DébutTantQuegauche(x) <>Nil Fairex<- gauche (x)

FinTantQue

Retourner(x)Fin

Algorithme Maximum

Par symetrie :ABRMaximum(x)

DébutTantQuedroit(x) <>Nil Fairex<- droit (x)

FinTantQue

Retourner(x)Fin

2.3 Successeur et predecesseurPrincipe

Si toutes les cles dans l'arbre ABR sont distinctes, le successeur d'un noeudkest le noeud contenant la plus petite cle superieure ak. Considerons le fragment d'arbre presente sur la gure :k A B y x

De par la propriete des ABR :

Unisciel algoprog { br00cours-texte, May 21, 20186 1. L eso us-arbreAne contient que des cles inferieures ak: il ne peut pas contenir le successeur dek. 2. L eso us-arbreBne contient que des cles superieures ak: il peut contenir le suc- cesseur dekque s'il n'est pas vide.

3.ydesigne le plus proche anc^etre dekqui soit le ls gauche de son pere (y=ksi

kest ls gauche de son pere). Tous les anc^etres dekjusqu'aysont inferieurs ou egaux aket leurs sous-arbres gauches ne contiennent que des valeurs inferieures a k.

4.xest le pere dey. Sa valeur est superieure a toutes celles contenues dans son sous-

arbre gauche (de raciney) et donc aket a celles deB. Toutes les valeurs de son sous-arbre droit sont superieures ax. En resume : siBest non vide, son minimum est le successeur dek, sinon le successeur dekest le premier anc^etre (ascendant) dekdont le ls gauche est aussi anc^etre dek. Si cet ascendant n'existe pas c'est quekportait la valeur la plus grande dans l'arbre. Unisciel algoprog { br00cours-texte, May 21, 20187Exemple Remarquez qu'il est necessaire d'avoir pour chaque noeud un lien vers son pere pour mener a bien cette operation.Algorithme Successeur

ABRSuccesseur

x DébutSidroit(x) <>Nil AlorsRetournerABRMinimum(droit(x))Sinon y p re x

TantQuey<> Nil etx= droit (y)Fairex<- y

y p re x

FinTantQue

Retourner(y)FinSi

Fin Unisciel algoprog { br00cours-texte, May 21, 20188

3 Insertion d'un elementPrincipe

L'element a ajouter est insere la ou on l'aurait trouve s'il avait ete present dans l'arbre. L'algorithme d'insertion recherche donc l'element dans l'arbre et, quand il aboutit a la conclusion que l'element n'appartient pas a l'arbre (l'algorithme aboutit surNil), il insere l'element comme ls du dernier noeud visite.Algorithme d'insertion

ABRInsertion

T z

Débutx<- racine (T)

p re_de_x Nil

TantQuex<> Nil Fairepère_de_x<- x

Sicle(z) Sinon x droit x FinSi

FinTantQue

p re z p re_de_x

Sipère_de_x= Nil Alorsracine(T) <-z

Sinon si cle(z) Ecrivez une version recursive de l'operation.

Unisciel algoprog { br00cours-texte, May 21, 20189

4 Suppression d'un element

L'operation de suppression depend du nombre de ls du noeud a supprimer dans l'ABR. Les dierents cas de gure possibles sont les suivants (les noeuds a supprimer sont en gris fonce) :Cas 1 : Cas d'une feuille Le noeud a supprimer n'a pas de ls : on l'elimine simplement de l'arbre en modiant le lien de son pere. Si le pere n'existe pas, l'arbre devient l'arbre vide.Exemple

Cas 2 : Cas d'un unique ls

Le noeud a supprimer a un unique ls : on detache le noeud et on relie directement son pere et son ls. Si ce pere n'existe pas, l'arbre est reduit au ls unique du noeud supprime.Exemple Unisciel algoprog { br00cours-texte, May 21, 201810Cas 3 : Cas de deux ls Le noeud a supprimer a deux ls : on le remplace par son predecesseurqqui, dans ce cas, est toujours le maximum de son sous-arbre gauche (on peut prendre indieremment son successeur qui est alors le minimum de son sous-arbre droit). Puisque le noeudq a la valeur la plus grande dans le ls gauche, il n'a donc pas de ls droit, et peut ^etre decroche comme on l'a fait dans les cas 1 et 2.Exemple

Algorithme de suppression

Il tient compte des conditions aux limites (changement de racine).ABRSuppression(T,x) DébutSigauche(x) =Nil etdroit(x) =Nil AlorsSipère(x) =Nil Alorsracine(T) <-Nil Sinon Six= gauche (père(x))Alorsgauche(père(x)) <-Nil Unisciel algoprog { br00cours-texte, May 21, 201811Sinon droit p re x Nil FinSi FinSi Sinon Si gauche(x) =Nil Oudroit(x) =Nil AlorsSigauche(x) <>Nil Alorsfilsde_x<- gauche (x) Sinon filsde_x droit x FinSi p re filsde_x p re x

Sipère(x) =Nil Alorsracine(T) <-filsde_x

Sinon Sigauche(père(x)) =x Alorsgauche(père(x)) <-filsde_x Sinon droit p re x filsde_x FinSi FinSi Sinon xmin

ABRMinimum

droit x cle y cle xmin

ABRSuppression

T xmin FinSi

RetournerTFin

Unisciel algoprog { br00cours-texte, May 21, 201812

5 Conclusion

Sihest la hauteur de l'arbre, on peut aisement montrer que tous les algorithmes prece- dents ont une complexite enO(h). Malheureusement, un arbre binaire quelconque den noeuds a une hauteur comprise, en ordre de grandeur, entrelgnetn. Pour eviter les cas les plus pathologiques, on s'interesse a des arbres de recherchesequilibres.quotesdbs_dbs10.pdfusesText_16

[PDF] parcours en profondeur arbre

[PDF] arbre binaire complet

[PDF] dénombrement cours

[PDF] arbre de probabilité pile ou face

[PDF] arbre de probabilité seconde

[PDF] arbre probabilité conditionnelle

[PDF] arbre de décision exercices corrigés

[PDF] arbre de décision data mining

[PDF] cours arbre de décision

[PDF] classification par arbre de décision

[PDF] arbre de décision exemple

[PDF] arbre de décision cart

[PDF] construire un arbre de décision

[PDF] arbre de décision définition

[PDF] dénombrement cours 1ere s