INF6

ALGORITHMIQUE
AVANCÉE
Manuele Kirsch Pinheiro
Carine Souveyet
 05/03/16 2

Contenu prévisionnel
• Piles et files
• Listes
• Récursivité
• Récursivité dans le calcul
• Récursivité structurelle
• Arbres binaires
• Parcours en profondeur et en largeur
• Généralisation de la notion d’arbre
• Insertion et suppression de nœuds
• Arbre de recherche
• Recherche & manipulation
• Rééquilibrage
ARBRES DE RECHERCHE
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 4

Arbres binaires de recherche

( Binary Search Trees)
• Un arbre de recherche est un arbre binaire où les
nœuds sont organisés suivant une relation d’ordre
Soit a un arbre de recherche
∀a ∈ ArbreRecherche,
∀e ∈ SousArbreGauche(a) et ∀e’ ∈ SousArbreDroit(a)
alors
clé (e) ≤ clé ( racine (a) ) < clé (e’)

Toutes les valeurs de clé à 7

gauche de la racine sont Toutes les valeurs de clé à
inférieures à celle-ci droite de la racine sont
5 8 supérieures à celle-ci
clé (e) ≤ clé (racine)
clé (e’) > clé (racine)
2 6 9
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 5

Définitions
• Dans un arbre binaire de recherche :
• Toutes les clés du sous arbre gauche sont inférieurs ou égales
à la clé du nœud
• Toutes les clés du sous arbre droit sont strictement supérieurs
à la clé du nœud

Un parcours infixe dans l’arbre

permet d’obtenir l’ensemble de
valeurs ordonnées :
256789 n1 Le nœud n3 est à droite
de n1, il est donc
7 supérieur à celui-ci
n2 n3
5 8
n6 Le nœud n5 est à droite
Le nœud n4 est à 2 6 9 de n2 et à gauche de n1,
gauche de n2, il est il est donc supérieur n2 et
n4 n5
donc inférieur à celui-ci inférieur à n1
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 6

Définitions
• Un même ensemble de valeurs peut être
représenté par différents arbres, aux
profondeurs (height) distinctes

7 5
height

2 7

height
5 8
=2

=3
2 6 9 6 8

+ profondeur ⇒ - recherche efficace

 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 7

Opérations
• Différentes opérations peuvent être réalisées dans un
Arbre Binaire de Recherche (ABR)
• Opérations de recherche
• Search à recherche une valeur dans l’arbre
• Minimum à trouver la plus petite valeur contenue dans l’arbre
• Maximum à trouver la valeur maximale contenue dans l’arbre
• Successeur à trouver le prochain nœud (ou la prochaine valeur)
d’un nœud / valeur
• Prédécesseur à trouver le nœud (ou valeur) précédent un autre
• Opérations de manipulation
• Insertion à insérer une nouvelle valeur dans l’arbre
• Suppression à supprimer une valeur de l’arbre
• Rééquilibrage à rééquilibre l’arbre de manière à contrôler sa
profondeur
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 8

Opérations
Successeur
racine
de 13
15

6 18

maximum
3 7 17 20

minimum 2 4 13 Successeur
de 15
9
Prédécesseur
Prédécesseur de 15
de 13
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 9

Implémentations
• Différentes implémentations sont possibles
• avec ou sans la notion de nœud
• avec ou sans le parent
Visual Paradigm Professional Edition(Université Paris 1 Panthéon Sorbonne)

K
! Attention : l’absence d’un 0..1 -parent V

lien vers le parent a un fort -key : K

ABR

impact sur certaines opérations -value : V

sual Paradigm Professional Edition(Université Paris 1 Panthéon Sorbonne) -parent : ABR<K, V>
-left : ABR<K, V>
K
V 0..1 K extends Comparable -right : ABR<K, V>
-right +search(k : K) : ABR<K, V>
ABR
ê +min() : ABR<K, V>
-left afin de pouvoir comparer +max() : ABR<K, V>
0..1 les éléments (< ou >) +successor() : ABR<K, V>
+successor(key : K) : ABR<K, V>
+predecessor() : ABR<K, V>
K +predecessor(key : K) : ABR<K, V>
V +add(key : K, value : V)
Noeud +remove(key : K)
0..1 +reequilibrage()
-key : K
-value : V - l e f t 0..1 - r i g h t 0..1
-racine
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 10

Implémentations
• Avec parent et sans la notion de nœud

/
15 val

15

6 18

6 val 18 val
17
/ / /

17 val
/ /
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 11

Implémentations
• Sans parent et avec la notion de nœud

15 15 val

6 18

17

ABR
racine 6 val
18 val
/ /
Nœud /
key val
left right 17 val
/ /
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 12

Recherche dans un ABR

• Search
• Objectif : retrouver le nœud (sous-arbre) contenant
une certaine valeur K
• On dit que chaque nœud contient une valeur de clé qui
détermine son ordre dans l’arbre
• On cherche alors le nœud contenant la clé K
Search : Arbre x Key à Nœud
• Algorithme :
• On vérifie, pour chaque nœud x, s’il ne contient pas la valeur
de clé k recherchée. Si ce n’est pas le cas, on étend la
recherche aux sous arbres
• Si k < clé ( x ) alors le nœud recherché est à la sous arbre gauche
• Si k > clé ( x ) alors le nœud se trouve à la sous arbre droite
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 13

Recherche
• On recherche à partir d’un nœud x (this)
Search
Entrée :
ABR x Search ( n15, 13 )
Key k x n15
Sortie :
ABR y Search ( n6, 13 ) 15
n6 6 18
Si x == null OU k == x.key
Search ( n7, 13 )
alors n7
y=x 3 7 17 20
Sinon
Si k < x.key
alors y = Search ( x.left, k ) 2 4 13 y
sinon y = Search ( x.right, k) n13
fin si 9
fin si
retourner y Search ( n13, 13 )
fin
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 14

Recherche
• Ou de manière non récursive…

Search
Entrée : Search ( n15, 13 )
ABR x n15
Key k x
Sortie : 15
ABR y
n6 6 18
Tant que x ≠ null ET k ≠ x.key n7
faire 3 7 17 20
Si k < x.key
alors x = x.left
sinon x = x.right 2 4 13 y
fin si n13
fin tant 9
y=x
retourner y
fin
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 15

Min / Max
• Minimum
• La valeur minimale d’un ABR se trouve toujours à la
feuille à l’extrémité gauche de l’arbre.
• Pour la trouver, il suffit d’explorer le sous arbre gauche
à partir de la racine
• Maximum 15

• La valeur maximale se retrouve à 6 18

l’extrémité droite de l’arbre.
• Elle est donc accessible en 3 7 17 20

explorant le sous arbre droit

2 4 13
min max
9
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 16

Min / Max
• On recherche le min à partir de la racine (this)
Min n15.Min ()
Entrée : ≈
ABR racine Min ( n15 )
Sortie :
racine n15
ABR x
15
ABR x = racine
n6 6 18
Tant que x ≠ null ET x.left ≠ null
faire
n3
x = x.left 3 7 17 20
fin tant
n2
retourner x 2 4 13
fin
9
Exercice : on peut aussi le faire extrémité la
de manière récursive… plus à gauche
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 17

Min / Max
• On recherche le max à partir de la racine (this)
Max n15.Max ()
Entrée : ≈
ABR racine Max ( n15 )
Sortie :
racine n15
ABR x
15
ABR x = racine n18
Tant que x ≠ null ET x.right ≠ null 6 18
faire n20
x = x.right 3 7 17 20
fin tant

retourner x 2 4 13
fin
9 extrémité la
plus à droite
Exercice : on peut aussi le faire
de manière récursive…
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 18

Successeur / Prédécesseur
• Le successeur d’un nœud x est le nœud y
contenant la plus petite valeur supérieur à x
• Le prédécesseur d’un nœud x est le nœud y
contenant la plus grand valeur inférieur à x
Successeur de 13
15
Prédécesseur 6 18
de 7

… 7 17 …

13
Prédécesseur Le successeur de 15
de 15 …
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 19

Successeur / Prédécesseur
• Successeur : deux cas possibles
• x contient un sous arbre droit
• son successeur est le min de son sous arbre droit
(feuille à l’extrémité gauche de ce sous arbre)
• x ne contient pas de sous arbre droit
Le successeur de 15
• le successeur est un ascendant
est le min de son
• le + petit ancestral de x sous arbre droit
15

6 18

… 7 17 …

+ petit ascendant è le 1er ascendant Successeur de 13

13
dont la branche est à gauche (dans le est son + petit
sous arbre gauche de son parent) … ascendant
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 20

Successeur / Prédécesseur
• On recherche le successeur à partir d’un nœud x (this)
Successeur
Entrée :
ABR x Successeur ( n15 )
Sortie : x n15
ABR y
15
Si x ≠ null ET x.right ≠ null n6 6 18
alors
y = Min (x.right)
sinon 3 7 17 20
y = x.parent
Tant que y ≠ null ET x = y.right n13 13
2 4
faire
x=y min(n15.right)
y = y.parent x
fin tant Successeur ( n13 )
retourner y
fin
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 21

Successeur / Prédécesseur
• Prédécesseur : idem successeur, en inversant
droit et gauche
• x contient un sous arbre gauche
• son prédécesseur est le max de son sous arbre gauche
(feuille à l’extrémité droit de ce sous arbre)
• x ne contient pas de sous arbre gauche
• le prédécesseur est
15
un ascendant
• le 1er ancestral de x 6 18
appartenant au sous arbre
droit de son parent … 7 17 …

Prédécesseur de 17 est
13 son + grand ascendant
Le prédécesseur de 15 est le (celui à la sous arbre
max de son sous arbre gauche …
droit de son père)
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 22

Successeur / Prédécesseur
• On recherche le successeur à partir d’un nœud x (this)
Prédécesseur
Entrée :
ABR x Prédécesseur ( n15 )
Sortie : x n15
ABR y
15
Si x ≠ null ET x.left ≠ null n6 6 18
alors
y = Max (x.left)
sinon 3 7 17 20
y = x.parent
Tant que y ≠ null ET x = y.leftt n13 13
2 4 x
faire
x=y Prédécesseur
y = y.parent max(n15.left)
( n17 )
fin tant
retourner y
fin
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 23

Successeur / Prédécesseur
• On peut également demander le successeur ou
prédécesseur d’une valeur de clé
(et pas d’un nœud) Visual Paradigm Professional Edition(Université Paris 1 Panthéon Sorbonne)

• successor() à successeur d’un nœud

K
0..1 -parent V

(au vu de sa clé)
ABR
-key : K
-value : V

• successor(key: K) à successeur -parent : ABR<K, V>

-left : ABR<K, V>

d’une valeur de clé à partir de la racine -right : ABR<K, V>

+search(k : K) : ABR<K, V>
+min() : ABR<K, V>
+max() : ABR<K, V>
+successor() : ABR<K, V>

• Attention : +successor(key : K) : ABR<K, V>

+predecessor() : ABR<K, V>
+predecessor(key : K) : ABR<K, V>
• lors qu’on n’a pas le parent, +add(key : K, value : V)
+remove(key : K)
successor () considère le nœud +reequilibrage()
- l e f t 0..1 - r i g h t 0..1

comme racine (impossible de

remonter l’arbre au-delà de ce nœud)
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 24

Successeur
Entrée :
il faut d’abord trouver
le nœud contenant la
Successeur
Key k valeur recherchée • On recherche le
ABR racine (ou la plus proche
Sortie : successeur à partir d’un
dans l’arbre)
ABR a nœud racine (this)
Si racine.key ≠ null Alors Successeur ( n15 , 13 )
Si k < racine.key Alors Successeur ( n15 , 19 )
Si racine.left ≠ null Alors
a = successeur (k, racine.left) racine n15 Successeur
sinon a = racine 15 ( n18 , 19 )
fin Si Successeur
Sinon Si k > racile.key Alors ( n6 , 13 ) 6 n6 n18 18
Si racine.right ≠ null Alors
n7
a = successeur (k, racine.right) … … n20 20
Sinon a = successeur (racine) 7
Successeur
Fin si ( n7 , 13 ) Successeur
Sinon a = successeur (racine) n13 13
( n20 , 19 )
fin Si Successeur
Sinon a = null (ou exception car arbre vide) ( n13 , 13 )
retourner a Successeur ( n13 )
fin
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 25

Successeur / Prédécesseur
• Si on simplifie la structure de données en supprimant le
pointeur vers le parent :
• On ne peut plus remonter l’arbre à appel à partir de la racine
• On aura besoin de garder une « trace » des appels pour retrouver
les parents
• Structure auxiliaire : une pile
Méthode public
ê
public ABR successeur (K key ) créer la pile et lancer la méthode
interne (protected)
Si this.key == null Alors
retourner null (ou lancer exception) Méthode protected
ê
Pile p = nouvelle Pile ABR successeur ( K key , Pile p )
retourner this.successeur ( key, p ) parcours l’arbre de manière
récursive à la recherche du
fin successeur
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 26

Successeur / Prédécesseur
• Successeur ( clé ) sans parent
protected ABR successeur ( K key , Pile p )

Si key < this.key Alors Sinon

Si this.left ≠ null Alors Si this.right ≠ null Alors
p.empile ( this ) retourner this.right.min ()
retourner left.successeur ( key, p ) Sinon
sinon ABR x = this
retourner this Tant que ! p.estVide() Faire
fin Si ABR pere = p.depiler ()
Sinon Si key > this.key Alors Si x ≠ pere.right Alors
Si this.right ≠ null Alors retourner pere
p.empile ( this ) Sinon
retourner right.successeur ( k, p ) x = pere
Sinon fin Tant
retourner successeur ( this.key , p ) retourner null
Fin si fin Si
… fin Si on ne l’a pas trouvé
fin dans l’arbre…
 05/03/16 Manuele Kirsch Pinheiro - CRI/UP1 - [email protected] 27

Successeur / Prédécesseur
• Successeur ( clé ) sans parent racine
n15.successeur (13 ) 15
n15
6 18
n15.successeur (13 , [ ]) n6
this = n15 p = [ n15 ]
8 17
n8
n6.Successeur ( 13 , [ n15 ] )
this = n6 p = [ n6 , n15 ] 7 13
n13

n8.Successeur ( 13 , [n6 , n15 ] )

this = n8 p = [ n8 , n6 , n15 ] x = n13 p = [ n8 , n6 , n15 ]
pere = n8
x = n8 p = [ n8 , n6 , n15 ]
pere = n6
n13.Successeur ( 13 , [ n8 , n6 , n15 ] ) x = n6 p = [ n8 , n6 , n15 ]
this = n13 p = [ n8 , n6 , n15 ] pere = n15