Arbres binaires de recherche

Lycée Faidherbe, Lille
MP1
Cours d’informatique
2013–2014
Arbres binaires
de recherche
I
Définitions
Parcours ordonné 2
II
...............................
Caractérisation 2
Opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Recherche 4 Insertion aux feuilles 4
: tri 8
Suppression 8
III
2
Implémentation 3
Exercices
Insertion à la racine 5
................................
3
Application
11
Parcours de recherche 11
Reconstruction 11
Fusion 11
Successeurs et prédécesseurs 11
Nombre de constructions 11
Vérification 12
Complexité moyenne d’une recherche 12
Rang et rang local 13
A.B.R.
page 1
I Définitions
I.1 Parcours ordonné
Un arbre binaire de recherche est un arbre binaire tel que tout nœud contient un
champ, noté cle ou etiquette, dont les valeurs sont entières (ou décrivent un
ensemble ordonné) et tel que le parcours infixe des clés de l’arbre donne une suite
croissante.
Exemple
22
13
28
18
11
31
16
I.2 Caractérisation
Un arbre binaire est de recherche si et seulement si pour tout
nœud x, de clé n, les clés des éléments de la branche gauche de
x sont inférieures ou égales à n et les clés des éléments de la
branche droite de x sont supérieures ou égales à n.
Sens direct
On suppose que l’arbre est un arbre binaire de recherche.
Pour tout sous–arbre les clés du fils gauche sont lues par le parcours infixe avant la
clé de la racine donc, comme le parcours est croissant, les clés du fils gauche sont
inférieures à celle de la racine.
De même les clés du fils droit sont supérieures à celle de la racine.
page 2
A.B.R.
Sens inverse
On vérifie la réciproque par récurrence sur la hauteur.
• C’est évident pour un sous–arbre de hauteur 0.
• Si c’est vrai pour tous les arbres de hauteur p au plus. Les fils droit et gauche
d’un arbre de hauteur p + 1 ont une hauteur inférieure ou égale à p. Le parcours
infixe de T se fait en parcourant le fils gauche, qui donne des clés croissantes
par hypothèse de récurrence, puis en lisant la clé de la racine, supérieure aux
précédentes, puis en parcourant le fils droit, toujours en croissant.
Le parcours infixe est croissant.
I.3 Implémentation
La déclaration du type et les fonctions de construction et déconstruction sont les
mêmes que dans le cas d’un arbre binaire classique.
Si on veut les employer il faut vérifier soi–même que les clés sont dans le bon ordre.
Dans toute la suite on va supposer que les clés sont distinctes.
type ’n abr =
Vide
|Noeud of (’n abr*’n *’n abr);;
let filsG = function
|Vide -> raise(Failure "Arbre vide")
|Noeud (g,_,_) -> g;;
let filsD = function
|Vide -> raise(Failure "Arbre vide")
|Noeud (_,_,d) -> d;;
let racine = function
|Vide -> raise(Failure "Arbre vide")
|Noeud (_,n,_) -> n;;
II Opérations
A.B.R.
page 3
II.1 Recherche
La recherche est simple : on “descend” dans l’arbre en choisissant le fils gauche ou
le fils droit selon que la valeur à chercher est inférieure ou supérieure à la clé du
nœud.
C’est le principe de la recherche par dichotomie
On parcourt ainsi (partiellement) une branche de l’arbre.
Programme
let rec chercher x = function
|Vide -> raise(Failure "Arbre vide")
|Noeud(g,n,d) as arbre -> if (n = x)
then arbre
else if (x < n)
then chercher x g
else chercher x d;;
Complexité
La complexité maximale est la hauteur de l’arbre.
Dans le cas des arbres équilibrés on sait que la longueur des branches est de l’ordre
de ln(n) où n est la taille de l’arbre.
Le nombre
de comparaisons pour trouver le sous–arbre recherché est alors un
O ln(n) .
II.2 Insertion aux feuilles
On peut ajouter un nouvel enregistrement à une feuille de l’arbre : on recherche
l’élément et une recherche infructueuse arrive à un sous–arbre Vide. On peut alors
y placer l’élément.
Si la recherche donne un résultat on ne change rien car on s’interdit les clés multiples.
Exemple
On ajoute 25 à l’exemple initial :
page 4
A.B.R.
22
13
28
18
11
25
31
16
Programme
let rec ajouter x = function
|Vide -> Noeud(Vide,x,Vide)
|Noeud(g,n,d) as arbre -> if (n = x)
then arbre
else if (x < n)
then Noeud((ajouter x g),n,d)
else Noeud(g,n,(ajouter x d));;
La complexité est
proportionnelle au nombre d’appels reccursifs effectués donc est
de la forme O h où h est la hauteur de l’arbre.
II.3 Insertion à la racine
On peut aussi choisir d’insérer un nouveau nœud à la racine.
Pour cela il faut couper l’arbre en deux parties regroupant les nœuds inférieurs à la
nouvelle clé et ceux qui sont supérieurs.
De plus on va essayer de le faire avec un coût minimum c’est–à–dire fonction de la
hauteur et non de la taille.
Le dernier arbre construit :
A.B.R.
page 5
22
13
28
18
11
31
25
16
est coupé par 17 en
22
13
28
18
11
31
25
16
on reconstruit deux arbres :
22
13
11
page 6
18
16
28
25
31
A.B.R.
puis on ajoute 17
17
13
11
22
16
18
28
25
31
Algorithme de coupure
On obtient les parties gauche et droite récursivement
• Si la clé de coupure est inférieure à la clé de la racine alors la partie gauche est
la partie gauche du découpage du fils gauche (il n’y a aucune clé inférieure dans
le fils droit).
• Sinon la partie gauche est l’arbre obtenu en remplaçant le fils droit de l’arbre
initial par la partie gauche du découpage du fils droit.
• De même pour la partie droite
let rec decouper x = function
|Vide -> (Vide,Vide)
|Noeud(g,n,d) -> if (n = x)
then (g,d)
else if (x < n)
then let (gg,gd) = decouper x g in
(gg,Noeud(gd,n,d))
else let (dg,dd) = decouper x d in
(Noeud(g,n,dg),dd);;
Reconstruction
let ajouter_racine x a =
let (g,d)= decouper x a in Noeud(g,x,d);;
On a conservé la possibilité d’ajouter une clé déjà existante, elle est alors éliminée
des arbres gauche et droite. Cela aura comme effet de déplacer cette clé à la racine.
A.B.R.
page 7
II.4 Application : tri
On peut utiliser les arbres binaires pour effectuer un tri.
• On insère (dans le désordre) les éléments à trier dans un arbre à partir de l’arbre
vide.
• On lit l’arbre dans un parcours infixe : la liste est triée.
Complexité
Sion admet
que la hauteur moyenne d’un arbre binaire de taille n est un
O ln(n) alors le temps moyen d’insertion de la k–ième valeur dans l’arbre bi
naire est O ln(k) donc la complexité moyenne de la création du tableau est
n
P
O ln(k) = O n ln(n) .
k=1
Comme le parcours infixe se fait en temps linéaire, O n , le tri sera fait, en
moyenne, avec une complexité de O n ln(n) .
II.5 Suppression
La suppression d’un nœud demande de conserver la structure ordonnée.
Il est relativement facile d’imaginer comment supprimer une feuille : on la remplace par l’arbre vide.
Le cas d’un nœud interne n est plus délicat. On se ramène au cas de la racine car il
suffira de remplacer le sous–arbre dont n est la racine par l’arbre diminué.
Choix d’une racine
Si on ôte la racine d’un sous–arbre il faut choisir un nœud à placer à la racine. Pour
le faire sans trop de modification on va choisir un nœud du fils gauche et la placer
à la racine. La valeur de sa clé sera inférieure à toutes les clés du fils droit et pour
majorer les clés du fils gauche il faut choisir le maximum dans le fils gauche.
On peut aussi choisir le minimum du fils droit.
On va donc opérer en 3 étapes
calculer la clé maximale du fils gauche,
on cherche récursivement le fils droit sans fils droit
enlever le nœud correspondant
si T 0 est le sous–arbre du fils gauche dont la clé est maximale alors il n’a pas de
fils droit (qui, sinon, aurait des clés supérieures) ; le fils gauche de T 0 remplace
T0
reconstuire l’arbre.
Si la racine n’avait pas de fils gauche le nouvel arbre serait simplement le fils droit.
page 8
A.B.R.
17
9
22
6
16
18
28
12
11
14
9
22
6
16
12
11
A.B.R.
31
25
18
28
25
31
14
page 9
16
9
22
6
18
12
11
14
28
25
31
let rec max = function
|Vide -> raise(Failure "Arbre vide")
|Noeud(_,n,Vide) -> n
|Noeud(_,_,d) -> max d;;
let rec supprMax = function
|Vide -> raise(Failure "Arbre vide")
|Noeud(g,n,Vide) -> g
|Noeud(g,n,d) -> Noeud(g,n,supprMax d);;
let enleverRacine = function
|Vide -> Vide
|Noeud(g,n,Vide) -> g
|Noeud(g,n,d) ->
let r = max g in
Noeud(supprimerMax g,r,d);;
On peut donc maintenant écrire la suppression d’un nœud.
let rec enlever x = function
|Vide -> Vide
|Noeud(g,n,d) as arbre ->
if (n = x)
then enleverRacine arbre
else if (x < n)
then Noeud((enlever x g),n,d)
else Noeud(g,n,(enlever x d));;
page 10
A.B.R.
III Exercices
III.1 Parcours de recherche
On suppose que tous les nombres de 1 à 800 sont les clés d’un arbre binaire de recherche.
Parmi le suites suivantes lesquelles ne peuvent pas être les clés d’un parcours de
recherche de 417 ?
• 222, 457, 122, 217, 417
• 545, 215, 333, 401, 422, 417
• 601, 403, 555, 408, 523, 411, 466, 417
• 601, 403, 555, 408, 563, 411, 466, 417
• 901, 403, 555, 411, 466, 417
III.2 Reconstruction
Prouver que la liste des éléments d’un arbre binaire de recherche lu en parcours
préfixe permet de reconstruire l’arbre.
III.3 Fusion
Écrire une fonction Fusion a b qui joint deux arbres binaires de recherche ; on
pourra utiliser les fonctions de coupure d’un arbre binaire de recherche.
III.4 Successeurs et prédécesseurs
Le successeur (resp. prédécesseur) d’un nœud de clé k est le nœud de l’arbre dont la
clé suit (resp. précéde) k dans le parcours infixe.
Montrer que si un nœud d’un arbre binaire de recherche a deux fils alors son prédécesseur n’a pas de fils droit et son successeur n’a pas de fils gauche.
Montrer que si n est le successeur de p dans le parcours croissant d’un ABR alors
soit n est le plus petit élément du fils droit de p soit p est le plus grand élément du
fils gauche de n.
III.5 Nombre de constructions
Déterminer tous les ordres possibles d’insertion de clés à partir de l’arbre vide qui
donnent l’arbre suivant par adjonction aux feuilles
A.B.R.
page 11
6
8
4
7
2
3
Plus généralement montrer que le nombre de permutations des clés d’un arbre T , de
taille n, qui engendrent l’arbre par adjonctions successives aux feuilles est n! divisé
par le produit des tailles de tous les sous–arbres (y compris T ) de T .
III.6 Vérification
Écrire une fonction qui teste si l’arbre binaire passé en paramètre est un arbre binaire de recherche.
III.7 Complexité moyenne d’une recherche
On considère les arbres binaires de recherche construits en ajoutant à l’arbre vide
les nœuds de clé 1 à n dans le desordre.
On suppose que les n! ordres d’insertion sont équiprobables.
On cherche la complexité moyenne, en nombre de comparaisons, de la recherche
d’une clé dans l’arbre : an .
•
•
•
•
Montrer que la probabilité que la clé de la racine soit i est n1 . On note ai,n la
complexité moyenne, en nombre de comparaisons, de la recherche d’une clé
dans un arbre dont la racine a la clé i.
i−1 1
n−i
Prouver que ai,n = (ai−1 + 1)
+ + (an−i + 1)
.
n
n
n
n−1
2 X
En déduire que an = 1 + 2
iai
n i=1
1
puis que an = 2 (n2 − 1)an−1 + 2n − 1
n
(On pourra calculer n2 an − (n − 1)2 an−1 ).
Prouver que an = O ln(n)
n
(On pourra poser un = n+1
an ).
page 12
A.B.R.
III.8 Rang et rang local
Les arbres binaires de recherche considérés sont étiquetés par des entiers distincts.
On appelle rang d’un nœud de clé k, le nombre de nœuds de clé inférieure ou égale
à k, et rang local d’un nœud son rang dans le sous-arbre dont il est racine.
On définit les arbres binaires en Caml par:
type ab = Vide
|N of int * int * ab * ab;;
Dans N(e, r, g, d), e est l’étiquette, r est son rang local et g et d sont les deux sousarbres gauche et droit.
i. On suppose qu’un arbre binaire est construit, mais que les champs r de chaque
nœud contiennent 0.
Écrire une fonction Caml qui prend l’arbre en paramètre et renvoie le même
arbre mais avec les champs r remplis correctement.
ii. On suppose maintenant que r est bien le rang local. Donner un algorithme qui, à
un entier k contenu dans l’arbre associe le rang du nœud de clé k. L’algorithme
doit être en O(h) où h est la hauteur de l’arbre.
iii. Soit n la taille de l’arbre, et m un entier compris entre 1 et n. Donner un algorithme qui renvoie la clé du nœud de rang m.
A.B.R.
page 13

Download Report