[PDF] Les arbres et la neige
[PDF] les arbres rouges de maurice vlaminck
[PDF] les arenes de nimes
[PDF] les arguments de créon pour convaincre antigone
[PDF] les arguments de la dérive des continents
[PDF] lES ARGUMENTS DE WEGENER
[PDF] Les arguments envers les Incas-Espagnols
[PDF] les arguments et les exemples
[PDF] Les arméniens pendant la 1ere Guerre Mondiale
[PDF] Les Armes sont-elles nécessaire
[PDF] Les arrondis au centième et millimètre près
[PDF] les articles en espagnol pdf
[PDF] Les articles indefinis
[PDF] Les artificiers DM
[PDF] les artificiers sont cachés du public par un mur d
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 denquotesdbs_dbs10.pdfusesText_16
Algorithmique Les arbres