Structures de données avancées

●
Objectif
– Maîtriser l’utilisation des structures de
données en arbre dans la conception des
algorithmes

●
Volume horaire
– 36h
Plan
[Link]
2.Généralités sur les arbres
[Link] d’un arbre
[Link] binaires
[Link] binaires de recherche (ABR)
[Link] binaires
1-Introduction

La structure d'arbre est une structure de données

primordiale en informatique. Diverses variantes sont
utilisées : arbres binaires, B-arbres, arbres AVL, forêts
d'arbres ...
Un arbre est une structure homogène dont chaque
élément, appelé nœud, contient de l'information et
plusieurs liens (pointeurs) vers des élément s du même
type appelés nœuds fils ou successeurs.
1-Introduction
Exemples:
• Représenter les distances de Ouaga à toutes
les autres villes du Burkina.
• Représenter votre arbre généalogique à partir
de vos grand-parents.
1-Introduction
Exemple: Expressions arithmétiques
• La structure de l’arbre rend compte de la priorité des
opérateurs et rend inutile les parenthèses.
2- Généralités sur les arbres

Définitions:
Un graphe est connexe si tout couple de
nœuds est relié par une chaîne
Un graphe sans cycle est dit acyclique.

Exercice :
dessiner un graphe connexe et un graphe
acyclique
2- Généralités sur les arbres
Propriétés
Soit G(S, A) un graphe non orienté:
S: ensemble des nœuds; A: ensemble des liens
• G est arbre.
• Deux nœuds quelconques de G sont reliés par un
chemin élémentaire (formé de nœuds distincts)
• G est connexe et |A|=|S|-1
• G est acyclique et |A|=|S|-1
• Si un lien quelconque est ajoutée à A, G n’est plus un
arbre et, le graphe résultant contient un cycle.
2- Généralités sur les arbres

Exercice
Dessin d’arbre, forêt, graphe avec cycle
2- Généralités sur les arbres
Arbre enraciné
Un arbre (orienté ou enraciné) est un ensemble de
nœuds muni d’une relation de « parenté » qui
vérifie les conditions suivantes :
1. Il y a un seul nœud qui n'a pas de
prédécesseur (père). Ce nœud s'appelle racine.
2. Tous les nœuds, sauf la racine, n'ont qu'un seul
père (prédécesseur).
3. Il existe un chemin unique de la racine à chaque
nœud.
2- Généralités sur les arbres

Racine

Nœuds
internes

père(O) = {N} Feuilles

père(R) = {} ou
fils(M) = {A,B} nœuds externes
fils(B) = {}
2- Généralités sur les arbres
Arbre enraciné
Les nœuds terminaux, qui n’ont pas de fils, sont
appelés feuilles ou nœuds externes.
Les nœuds qui ne sont pas des feuilles ou
racine sont appelés nœuds internes.
Le prédécesseur d'un nœud s'appelle le père ou
l’ancêtre direct du nœud.
Le successeur est appelé le fils ou le
descendant direct du nœud.
Un nœud peut avoir plusieurs fils.
2- Généralités sur les arbres
Degré d’un nœud
Le nombre de fils d’un nœud n dans un arbre
est appelé le degré de n.

Arbre ordonné
Un arbre ordonné est un arbre dont dans
lequel les fils de chaque nœuds sont
ordonnées. En d’autres termes: si nœuds à k
fils, il y a un 1er fils, 2e fils … Kième fils.
2- Généralités sur les arbres
Chemin et branche
●
Un chemin de longueur k entre nœuds u et v
d’un arbre est la suite de nœuds {n0, n1, ..., nk}
telle que n0=u, nk=v et pour tout i appartenant
à l’intervalle [1..p], ni-1 = père(ni)

●
Une branche de l’arbre est un chemin de la
racine à l’une de ses feuilles.
2- Généralités sur les arbres

Bord d’un arbre

●
Le bord gauche de l’arbre est le plus long
chemin depuis la racine en ne suivant que les
fils gauches

●
Le bord droit de l’arbre est le plus long chemin
depuis la racine en ne suivant que les fils droits
2- Généralités sur les arbres

Sous-arbre
Soit A arbre et n nœud de A.
Un sous-arbre de A ayant pour racine n est la
partie de l’arbre constitué des descendant de n.
Le(s) sous-arbres d’un nœud x sont le(s) sous-
arbres dont les racines sont des fils de x.
2- Généralités sur les arbres

Sous-arbre
A arbre, n nœud de A
SA(x) = sous-arbre de A qui a racine x
1
A = SA( racine(A) )

2 3 4

SA (2) 5 6 7 8
SA (3)
SA (4) 9 10

A(2), SA(3) et S( 8) sont de sous-arbre de 1

2- Généralités sur les arbres
Hauteur
• La hauteur d'un nœud est le nombre maximum de
liens qu'il faut parcourir pour aller à une feuille.
• La hauteur d’un arbre est la hauteur de sa racine.

Définition récursive

hA(n) = 
Soit A arbre et n nœud de A
0 si n est feuille
1 + max { hA(e), où e est fils de n }
 2- Généralités sur les arbres

Hauteur
Soit A un arbre de 10 nœuds

Hauteur 3 1

hA (8) = 0 2 3 4
hA (7) = 1
hA (3) = 2 5 6 7 8
h(A) = hA (1) = 3
9 10
2- Généralités sur les arbres
Niveau ou profondeur
• Le niveau d'un nœud est le nombre d'arcs
qu'il faut parcourir à partir de la racine pour
arriver à ce nœud.
• La racine est de niveau 0.
Définition récursive
Soit A arbre, n nœud de A et NA(n) le niveau de
n dans A
NA(n) = 0 si n est racine de A
 1 + NA (père(n) ) sinon
 2- Généralités sur les arbres
Niveau ou profondeur
A arbre de 10 nœuds.

niveau
0 1
niveau
1 2 3 4
niveau 2 5 6 7 8
niveau
3 9 10
NA(1) = 0
NA(2) = NA(3)= NA(4)=1
NA(9)=3
2- Généralités sur les arbres
Arbre équilibré
Un arbre est dit équilibré si, à chaque niveau, la
hauteur des différents sous-arbres ne varie pas de
plus d'un niveau.

Le nombre maximum de nœuds qu'un arbre de

profondeur "p" et de degré "d" peut contenir, si tous
les nœuds internes ont "d" descendants, est :
,
A la racine on a d0 = 1 nœud au niveau suivant, on a d1 = d
nœuds.
3- Parcours d’un arbre

Il y a deux catégorie de parcours :

parcours en profondeur (branche après branche)
– préfixe,
– suffixe,
– symétrique
parcours en largeur (niveau après niveau)
3- Parcours d’un arbre
Parcours préfixe 1

Soit A Arbre non vide 2 3 4

A = (r, SA1, SA2, …, SAk)
SAi = sous-arbre de r 5 6 7 8

9 10
Le parcours préfixe donne la priorité au père
Cette visite se fait dans ce sens
• Visiter la racine r;
• Visite les sous arbres SA1, SA2, …, SAk

P(A) = (r).P(SA1). ... .P(SAk) : (1, 2, 5, 6, 3, 7, 9, 10, 4, 8)

 3- Parcours d’un arbre
Parcours suffixe 1
Soit A, un arbre non vide 3 4
2
A = (r, SA1, SA2, …, SAk)
SAi = sous-arbre de r 5 6 7 8

Parcours suffixe donne la priorité aux fils 9 10

• Visite les sous arbres SA1, SA2, …, SAk
• Visiter la racine r;

S(A) = S(SA1). ... .S(SAk).(r) (5, 6, 2, 9, 10, 7, 3, 8, 4, 1)

3- Parcours d’un arbre
Parcours symétrique 1
Soit A un arbre non vide
A = (r, SA1, SA2, …, SAk) 2 3 4
SAi = sous-arbre de r
5 6 7 8

Parcours symétrique (ou interne ) 9 10

• Visite le sous arbres SA1
• Visiter la racine r;
• , SA2, …, SAk
I(A) = I(A1).(r).I(A2). ... .I(Ak) (5, 2, 6, 1, 9, 7, 10, 3, 8, 4)
 3- Parcours d’un arbre
Parcours en largeur
1
Soit un Arbre non vide
A = (r, SA1, SA2, …, SAk) 2 3 4
SAi = sous-arbre de r
5 6 7 8

Parcours en largeur ou hiérarchique 9 10

H(A) = (r, x1, …, xi, xi+1, ... xj, xj+1, ..., xn)
nœuds de niveau 0, 1, 2, ...
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
4-Arbres binaires
Définition
Un arbre de degré 2 est appelé arbre binaire.
Un arbre de degré n supérieur à 2 est appelé arbre n-
aire

Un arbre binaire est un arbre orienté où chaque fils

d'un nœud est soit fils gauche, soit fils droit. Aucun
nœud n'a plus d'un fils gauche ni plus d'un fils droit.
 4-Arbres binaires
Définition récursive
Un arbre binaire non vide A=<r,A1, A2>
– r = nœud racine,
– A1 = arbre binaire, sous-arbre gauche de r,
– A2 = arbre binaire, sous-arbre droit de r,

• Un arbre binaire qui ne contient aucun nœud est appelé arbre

vide
• Si A1 n’est pas vide sa racine est fils gauche de r, de même si A2
n’est pas vide sa racine est fils droit de r.
• Si un sous-arbre est vide on dit que le fils est absent ou
manquant
 4-Arbres binaires

Exemple:
Racine

SAG SAD

Fils g. de r

Fils d. de r
4-Arbres binaires
Arbre complet
Un arbre binaire complet est un arbre
binaire dont chaque nœud est soit une
feuille soit de degré égal à 2. Autrement dit
tous les nœuds n’ont pas de fils manquants
sauf la feuille.
Exercice
calculer le nombre maximal de nœuds
dans un arbre binaire de hauteur p.
4-Arbres binaires

Exercice
Dessiner tous les arbres binaires ayant les
nœuds a, b, et c avec a pour racine.
4-Arbres binaires
Parcours ou visite
Accéder à l'information contenue dans les
nœuds d'un arbre pour
• faire une recherche,
• compter des éléments,
• faire une insertion,
• faire une suppression,
• …
Parcourir ou visiter les nœuds
4-Arbres binaires
Parcours ou visites
Dans le cas d'une structure linéaire, le choix est
facile : on y passe en ligne droite, du début à la
fin.
Cependant, dans les arbres comme dans les
graphes, la ligne droite n'existe pas. Alors,
comment peut-on passer par tous les nœuds ?0
 4-Arbres binaires
Parcours ou visite
Deux types de parcours
– En largeur d’abord
– En profondeur d’abord
– Préfixe (ordre de priorité au père)
– Postfixe (ordre de priorité aux fils)
– Infixe (l'ordre de priorité symétrique)
4-Arbres binaires
Parcours en profondeur
• Ces trois ordres viennent de la définition
récursive d’un arbre : un arbre est vide ou
est une racine avec un arbre à gauche et un
arbre à droite.
• Il y a donc trois arbres et c’est l’ordre de
visite de ces trois arbres qui change.
4-Arbres binaires
Parcours Préfixe
Cet parcours se fait dans ce sens :
– Visiter la racine r;
– Visiter selon la priorité au père les sous arbres SAG, SAD de r;
Parcprefixe(Racine)
Début
SI Racine ≠ Nil ALORS FAIRE
debut
Traiter Racine
Parcprefixe (filsGauche)
Parcprefixe(filsDroit)
fin
Fin
4-Arbres binaires
Parcours Postfixe
Cet parcours se fait dans ce sens :
– Visiter les sous arbres SAG, SAD de r selon la priorité au fils ;
– Visiter la racine r;
Parcpostfixe(Racine)
Début
SI Racine ≠ Nil ALORS FAIRE
debut
Parcpostfixe (filsGauche)
Parcpostfixe(filsDroit)
Traiter Racine
fin
Fin
4-Arbres binaires
Parcours infixe
Cet parcours se fait dans ce sens :
• Visiter selon la priorité symétrique le fils gauche de r;
• Visiter la racine r;
• Visiter selon la priorité symétrique le fils droit de r.
Parcinfixe(Racine)
Début
SI Racine ≠ Nil ALORS FAIRE
debut
Parcinfixe (filsGauche)
Traiter Racine
Parcinfixe(filsDroit)
fin
Fin
4-Arbres binaires
Exercices d’application.
Simuler tous les parcours sur cette arbre
binaire.
4-Arbres binaires
Exercice
Traduire les 3 parcours et écrire un
programme qui utilise l’exemple donné pour
tester les fonctions. Vérifiez que le
programme affiche le même résultat que
celui obtenu par simulation.
4-Arbres binaires
Parcours en largeur Marquez les sommets à 1
Principe Marquer un sommet à 2 (racine)
Tant qu’il existe un sommet x marqué 2:
• Regarder le prochain sommet x
marqué 2
• S'il existe un voisin v marqué 1, le
marquer 2
• Sinon marquer le sommet à 3
4-Arbres binaires
Parcours en largeur Marquez les sommets à 1
Marquer un sommet à 2 (racine)
Principe Tant qu’il existe un sommet x marqué 2:
• Regarder le prochain sommet x
marqué 2
• S'il existe un voisin v marqué 1, le
marquer 2
• Sinon marquer le sommet à 3
4-Arbres binaires
Parcours en largeur Marquez les sommets à 1
Marquer un sommet à 2 (racine)
Principe Tant qu’il existe un sommet x marqué 2:
• Regarder le prochain sommet x
marqué 2
• S'il existe un voisin v marqué 1, le
marquer 2
• Sinon marquer le sommet à 3
4-Arbres binaires
Parcours en largeur
Marquez les sommets à 1
Principe Marquer un sommet à 2 (racine)
Tant qu’il existe un sommet x marqué 2:
• Regarder le prochain sommet x
marqué 2
• S'il existe un voisin v marqué 1, le
marquer 2
• Sinon marquer le sommet à 3
4-Arbres binaires
Parcours en largeur
Marquez les sommets à 1
Principe Marquer un sommet à 2 (racine)
Tant qu’il existe un sommet x marqué 2:
• Regarder le prochain sommet x
marqué 2
• S'il existe un voisin v marqué 1, le
marquer 2
• Sinon marquer le sommet à 3
4-Arbres binaires
Parcours en largeur
Marquez les sommets à 1
Principe Marquer un sommet à 2 (racine)
Tant qu’il existe un sommet x marqué 2:
• Regarder le prochain sommet x
marqué 2
• S'il existe un voisin v marqué 1, le
marquer 2
• Sinon marquer le sommet à 3
4-Arbres binaires
Parcours en largeur
Marquez les sommets à 1
Principe Marquer un sommet à 2 (racine)
Tant qu’il existe un sommet x marqué 2:
• Regarder le prochain sommet x
marqué 2
• S'il existe un voisin v marqué 1, le
marquer 2
• Sinon marquer le sommet à 3
4-Arbres binaires
Parcours en largeur
Principe Marquez les sommets à 1
Marquer un sommet à 2 (racine)
Tant qu’il existe un sommet x marqué 2:
• Regarder le prochain sommet x
marqué 2
• S'il existe un voisin v marqué 1, le
marquer 2
• Sinon marquer le sommet à 3
 4-Arbres binaires
Parcours en largeur
Marquez les sommets à 1
Principe Marquer un sommet à 2 (racine)
Tant qu’il existe un sommet x marqué 2:
• Regarder le prochain sommet x
marqué 2
• S'il existe un voisin v marqué 1, le
marquer 2
• Sinon marquer le sommet à 3
4-Arbres binaires
Parcours en largeur
Exercice d’application.
Appliquer le principe du parcours à l’arbre
suivant.
4-Arbres binaires
Parcours en largeur
Exercice:
Proposer un algorithme du parcours en largeur
qui traduit le principe présenté.
4-Arbres binaires
Ramener un arbre n-aire à un arbre binaire.
• premier fils à gauche
• tous les frères à droite du premier fils.
 4-Arbres binaires
Implantation Par tableau
On crée une tableau de N éléments, un élément par
nœud, et ensuite on fait une correspondance des nœuds
de l'arbre sur les éléments du tableau.
Pour ce faire, on identifie chaque nœud de l'arbre :
– La racine a comme identificateur 1;
– Un fils gauche a comme identificateur 2D;
– Un fils droit a comme identificateur 2D + 1;
où D est l'identificateur du père.
4-Arbres binaires

Implantation Par tableau

Si on ne connaît pas exactement la taille de
l’arbre, on ajouter une marge de sécurité dans
l'allocation de la mémoire.

Exemple
Exemple d'un arbre de 15 nœuds :
4-Arbres binaires
Implantation Par tableau

L’arbre par excellence à implanter dans un

tableau est l’arbre binaire complet. Un arbre binaire
complet remplit tout le tableau.
4-Arbres binaires
Implantation Par tableau
Les avantages de ce modèle d’implantation sont surtout
au niveau de la manipulation de
l’arbre : il s’agit de la manipulation des indices.
• Pour trouver le père est simple. Il suffit de prendre la
partie entière de l’indice diviser par 2 et nous avons
son indice dans le tableau.
• Avec le modèle d’implantation dynamique, retrouver
le père est un peu plus compliqué que cette
opération:
indiceDuPereDe(i) = [i/2]
4-Arbres binaires
Implantation dynamique
La méthode dynamique utilise des nœuds et
contient trois composantes : la donnée (qui peut
être un élément composé) et de deux pointeurs.

NOUVEAU TYPE Noeud

DEBUT
TypeEl info {L’information a garder}
Noeud *filsGauche {pointeur vers SAG}
Noeud *filsDroit{pointeur vers SAD}
FIN
4-Arbres binaires
Implantation dynamique
La structure de l’arbre sera directement un
pointeur sur l’arbre (ce qui facilite l’implantation
des fonctions récursives)

NOUVEAU TYPE Arbre

DEBUT
Noeud *racine {La racine de l’arbre}
FIN
5-Arbres binaires de recherche (ABR)
Parmi les différentes structures d'arbres
possibles, une des plus utilisées est la structure
d'arbre binaire de recherche.
Motivation
Maintenir un ensemble ordonné S permet de
réduire la complexité de certaines opérations.
Exemple :

Solution -> utiliser les arbres binaires

5-Arbres binaires de recherche (ABR)
Définition
Un arbre binaire de recherche est un arbre
binaire tel que pour tout nœud, sa clé est
supérieure à toutes celles de ses descendants de
gauche et inférieure à toutes celles de ses
descendants de droite.
Exemple:
5-Arbres binaires de recherche (ABR)

Exemple:
Dessiner des arbres binaire de recherche
de hauteur 2,3,4,5 et 6 pour le même
ensemble {1,4,5,10,16,17,21}
5-Arbres binaires de recherche (ABR)
Le rôle d'une structure binaire de recherche est
de stocker des informations en conservant,
en plus, une hiérarchie entre ces informations.
Cette hiérarchie reflète des liens de dépendance
entre les données.
5-Arbres binaires de recherche (ABR)
Quel est le nombre de noeuds d’un arbre?
nbNoeuds
{Compte le nombre total de noeuds dans unArbre}
DEBUT
SI arbreVide(arb, err) = VRAI ALORS FAIRE
DEBUT
RETOURNER 0
FIN
SINON
DEBUT
RETOURNER nbNoeud(unArbre->filsGauche,
err)+ nbNoeud(unArbre->filsDroit, err)+ 1
FIN
FIN
5-Arbres binaires de recherche (ABR)
Opérations sur les ABR
• Arbre vide ?
• nombre de nœuds d’un arbre?
• nombre de feuilles d’un arbre?
• Avoir accès à la racine d’un arbre.
• Avoir accès au sous-arbre de gauche d’un
nœud (le fils gauche).
• Avoir accès au sous-arbre de droite d’un
nœud (le fils droit)
5-Arbres binaires de recherche
Opérations sur les ABR
• Quelle est la hauteur d’un nœud ?
• Rechercher un élément dans un arbre.
• Ajouter un élément (insertion) dans un arbre.
• Enlever un élément dans un arbre.
• Quel est l’élément le plus petit de l’arbre
(minimum) ?
• Quel est l’élément le plus grand de l’arbre
(maximum)
5-Arbres binaires de recherche (ABR)

Opérations sur les ABR

• Quels sont les enfants d’un nœud ?
• Quels sont les descendants d’un nœud ?
• Quel est le père (parent) d’un nœud ?
• Quels sont les ancêtres d’un nœud ?
• Etc
5-Arbres binaires de recherche (ABR)
arbreVide
{Indique si unArbre est vide}
DEBUT
SI unArbre = Nil ALORS FAIRE
DEBUT
RETOURNER VRAI

FIN
SINON
DEBUT
RETOURNER FAUX
FIN
FIN
5-Arbres binaires de recherche (ABR)
Quel est la hauteur d’un nœud ?
hauteur
{Donne la hauteur d’unArbre, retourne –1 si l’arbre est
vide}
DEBUT
{A : l’arbre n’est pas vide, sinon AV et RETOURNER -1}
SI unArbre->fileGauche = Nil ET unArbre->filsDroit = Nil
DEBUT
RETOURNER 0
FIN
SI unArbre->fileGauche = Nil ET unArbre->filsDroit != Nil
DEBUT
RETOURNER 1 + hauteur(unArbre->filsDroit)
FIN
5-Arbres binaires de recherche (ABR)
SI unArbre->fileGauche != Nil ET unArbre->filsDroit = Nil
DEBUT
RETOURNER 1 + hauteur(unArbre->filsGauche)
FIN
SINON
DEBUT
RETOURNER 1 + maximum(hauteur(unArbre->filsGauche),
hauteur(unArbre->filsDroit) )
{maximum retourne le max entre les deux}
FIN
 5-Arbres binaires de recherche (ABR)
Rechercher un élément dans un arbre.
appartenance
{Dit si un element elem appartient a l’arbre unArbre}
DEBUT
SI arbreVide(unArbre) ALORS FAIRE
RETOURNER FAUX
SINON
SI elem = unArbre->info ALORS FAIRE
RETOURNER VRAI
SINON
SI elem < unArbre->info ALORS FAIRE
RETOURNER
appartenance(unArbre->filsGauche,elem)
SINON
RETOURNER
appartenance(unArbre->filsDroit,elem)
FIN
5-Arbres binaires de recherche (ABR)
Ajouter un élément
L’insertion des nouveaux nœuds est faite au niveau
des feuilles.
Il suffit de descendre récursivement jusqu’à l’endroit
où l’on doit insérer la feuille en respectant la propriété
d’un arbre binaire ordonné.
Il faut donc comparer l’élément à ajouter avec
l’information contenue dans la racine : s’il est plus
grand, on appelle la fonction d’insertion avec le sous-
arbre droit, sinon on appelle la fonction d’insertion
avec le sous-arbre gauche.
 5-Arbres binaires de recherche (ABR)
Ajouter un élément
Exemple d’ajout du nœud 7 d’ABR suivant
 5-Arbres binaires de recherche (ABR)
Ajouter un élément
Exemple d’ajout du nœud 7 d’ABR suivant
 5-Arbres binaires de recherche (ABR)
Ajouter un élément
Exemple d’ajout du nœud 7 d’ABR suivant
 5-Arbres binaires de recherche (ABR)
Ajouter un élément
Exemple d’ajout du nœud 7 d’ABR suivant
5-Arbres binaires de recherche (ABR)
Ajouter un élément
Exemple d’ajout du nœud 7 d’ABR suivant
 5-Arbres binaires de recherche (ABR)
Ajouter un élément
inserer
{Fait l’ajout d’un noeud contenant elem dans l’arbre unArbre}
DEBUT
{A : elem n’appartient pas deja a l’arbre}
SI arbreVide(unArbre) = VRAI ALORS FAIRE
UnArbre ← ALLOUER sizeof(Noeud)
unArbre->info ← elem
unArbre->filsGauche ← NULL
unArbre->filsDroit ← NULL
SINON
SI elem < unArbre->info ALORS FAIRE
inserer(unArbre->filsGauche, elem)
SINON
inserer(unArbre->filsDroit, elem)
FIN
5-Arbres binaires de recherche (ABR)
Exercice
Proposer un algorithme qui retourne le
minimum d’un ABR. De même que le
maximum
5-Arbres binaires de recherche (ABR)
Supprimer un élément
On distingue 3 cas:
• le nœud x n’a pas de fils
gauche(pere(x)) ← null si x est l’enfant gauche
ou
droit(pere(x))← null si x est l’enfant droit

puis libérer la mémoire du nœud .

5-Arbres binaires de recherche (ABR)
Supprimer un élément
• le nœud x a un fils manquant
gauche(pere(x)) ← droit(x) si x a un droit et il
est l’enfant gauche. (voir les 3 autres cas de la
position de x et de son fils)
 5-Arbres binaires de recherche (ABR)
Supprimer un élément
• le nœud x deux fils:
trouver S le nœud successeur de x, et copier s dans x
puis enlever s
x

Successeur de x
Arbre supprimer(arbre T, nœud x);
{l’algo détermine un nœud y a enlever}
si (gauche[x] = Nil) ou (droit[x] = NIL) alors
y← x
sinon
y ← successeur(x)
si (gauche[y]  Nil) alors
n ← gauche[y]
sinon
n ← droite[y]
si (n NIL) alors
pere[n] ← pere[y]
si (pere [y] = Nil) alors
racine [T] ← n
sinon
si (y = gauche [pere[y]]) alors
gauche [pere[y]] ← n
Sinon
droit [pere[y]] ← n
si (y x) alors
cle[x] ← clé[y]
Supprimer (ou retourner) y
6-Tas binaires
Motivation
Comment obtenir le plus grand (ou le plus petit
élément) d’une liste?
6-Tas binaires
Motivation
Comment obtenir à le plus grand (ou le plus
petit élément) d’une liste?
6-Tas binaires
Motivation
Comment obtenir à le plus grand (ou le plus
petit élément) d’une liste?
6-Tas binaires
Motivation
Comment obtenir à le plus grand (ou le plus
petit élément) d’une liste?
6-Tas binaires
Motivation
Comment obtenir à le plus grand (ou le plus
petit élément) d’une liste?
6-Tas binaires
Motivation
Comment obtenir à le plus grand (ou le plus
petit élément) d’une liste?
6-Tas binaires
Motivation
Comment obtenir à le plus grand (ou le plus
petit élément) d’une liste?
• 1er solution: utiliser une pile ou file:
– ajout = temps constant (O(1))
– enlever+grand = temps linéaire O(n)
• 2e Solution : utiliser tableau maintenu trié
– ajout = O(n);
– Enlever+grand = temps linéaire O(1)
• 3e solution : Tas binaire
6-Tas binaires
Définition
Un tas binaire (max) est un arbre binaire ayant les
propriétés suivantes :
●
Père ≥ fils
●
arbre complet
6-Tas binaires
Exercice
• Quelle est la différence entre la structure des
arbres binaires de recherche et la structure de
tas ?
• Peut-on imprimer les clés d’un tas de n nœuds
dans l’ordre en O(n)? Expliquer pourquoi?
6-Tas binaires

Implantation par un tableau

Si indice Père = k alors
indice fils g = 2k+1
indice fils d = 2k+2

Si indice Fils = K
alors
Indice Père = (k-1)/2

Arbre tassé → pas de trou dans le tableau

6-Tas binaires
Enlever un élément(le plus grand)
– accès: temps constant
– Enlever: temps log(n)

Enlever la racine
6-Tas binaires
Enlever un élément(le plus grand)

Enlever la racine

Mettre le dernier élément à la

racine
Perte de la propriété de
décroissance

Descendre la nouvelle racine tant que la règle

de décroissance n’est pas respectée
6-Tas binaires
Enlever un élément(le plus grand)

Enlever la racine

Mettre le dernier élément à la

racine
Perte de la propriété de
décroissance

Descendre la nouvelle racine tant que la règle

de décroissance n’est pas respectée
6-Tas binaires
Enlever un élément(le plus grand)
Coût: log(n) échanges

Important : connaitre le dernier élément

L’échanger avec la racine
6-Tas binaires
Enlever un élément(le plus grand)
Mettre le dernier à la racine

Descendre tant que la règle

N’est pas respecté
6-Tas binaires
Ajout d’élément
Ajout : 0 et 2 en maintenant l’arbre complet
n: nombre de nœuds

Nombre de Niveau
= log2(n)
6-Tas binaires
Ajout d’élément
Ajout d’un élément dans le tas

Ajouter 11 en dernière
position garder l’arbre
tassé
6-Tas binaires
Ajout d’élément
Ajout d’un élément dans le tas

Ajouter 11 en dernière position

garder l’arbre tassé
Remonter l’élément tant qu’il ne
respecte la règle de décroissance
6-Tas binaires
Ajout d’élément
Ajout d’un élément dans le tas
Ajouter 11 en dernière position
garder l’arbre tassé
Remonter l’élément tant qu’il ne
respecte la règle de décroissance

Coût : log(n) opérations

6-Tas binaires
Ajout d’élément
Ajout d’un élément dans le tas
Ajout de n à la fin

Remonte tant que la règle

n’est pas respectée
6-Tas binaires
Exercice
1. La séquence 23,17,14, 6,13,10,1, 5, 7,12
forme t-elle un tas?

2. Un tableau trié à rebours forme t-il un tas?

3. où pourra se trouver le plus petit élément

d’un tas en supposant que tous les éléments
sont distincts?
6-Tas binaires

entasser(TypeEl tab[], int n, int i)

{Le tableau tab commence a l’indice 1 et se termine a
l’indice n, i est l’indice du sous-arbre dont il faut
etablir la propriete d’un decroissance}
DEBUT
K ← i {k contiendra l’indice du noeud superieur i il y en a}
REPETER
j ← k { j commence par i racine du SA}
SI 2j ≤ n ET tab[2j] > tab[k] ALORS FAIRE
k ← 2j { k prend l’indice du fils gauche car + grand }
SI 2j < n et tab[2j + 1] > tab[k] ALORS FAIRE
k ← 2j + 1 { k prend l’indice du fils droit car + grand }
Echanger (tab[j], tab[k]) { si le père est plus grand que ses fils k= j }
TANTQUE j != k {tant qu’il y a du changement}
FIN
6-Tas binaires
Cette procédure permet donc de créer un tas
avec un tableau, mais il faut l’appeler plusieurs
fois, en partant du centre du tableau (le premier
nœud qui n’est pas une feuille) car les feuilles
respectent trivialement la propriété de tas
Construire (TypeEl tab[], int n, )
debut
POUR i ϵ [n ÷ 2, 1] RÉPÉTER { i ϵ [(n-1)÷2, 0] }
tasser(tab, n, i)
fin
6-Tas binaires
Exercice
Construire tas sur le modèle sur le tableau
A = <5,3,17,10,84,19,6,22,9>