Scribd
Importer
20 vues12 pages

Arbre Binaire de Recherche : Définition et Opérations

L'Arbre Binaire de Recherche (ABR) est défini comme un arbre où chaque nœud respecte les propriétés d'ordre entre ses sous-arbres. Les opérations principales sur un ABR incluent la recherche, l'insertion et la suppression d'éléments, chacune ayant une méthode spécifique. Les ABR peuvent devenir déséquilibrés, ce qui affecte l'efficacité des recherches, d'où l'importance des arbres équilibrés pour optimiser les performances.

Transféré par

yahiamhemdi9
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
20 vues12 pages

Arbre Binaire de Recherche : Définition et Opérations

L'Arbre Binaire de Recherche (ABR) est défini comme un arbre où chaque nœud respecte les propriétés d'ordre entre ses sous-arbres. Les opérations principales sur un ABR incluent la recherche, l'insertion et la suppression d'éléments, chacune ayant une méthode spécifique. Les ABR peuvent devenir déséquilibrés, ce qui affecte l'efficacité des recherches, d'où l'importance des arbres équilibrés pour optimiser les performances.

Transféré par

yahiamhemdi9
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Arbre Binaire de Recherche : Définition

 L’ABR est défini récursivement par:

 l’arbre vide (^) est un ABR

 A = < A1 , x , A2 > est un ABR ssi

 A1 et A2 sont des ABR


 A1 ≤ x < A 2

72
Exemples
Exemples : 7
5

3 7 3

ABR ABR
4 6 5

4 6
Parcours en Infixé d’un ABR
4
Liste Triée en ordre croissant (décroissant)
3 5

NON ABR
6 7

73
Représentation et Opérations
ABR = AB
Opérations:

1) La Recherche d’un élément x dans un ABR A:


Recherche_ABR(A:ABR; x : valeur ; var ptx :ABR)
Debut
si A = NIL alors ptx := NIL
sinon si A^.val = x alors ptx := A
sinon si x < A^.val
alors Recherche_ABR(A^.fg,x,ptx)
sinon Recherche_ABR(A^.fd,x,ptx)
fsi
fsi
fsi
Fin
74
Opérations
2) L’Insertion d’un élément x dans un ABR A :
7

9
Insérer 4 dans : 5

3 6 8

Insérer 8 :

75
Opérations
Insère_ABR ( var A:ABR; x : valeur)
Debut
si A = NIL alors genere_Noeud(A,x)
sinon si x ≤ A^.val
alors Insère_ABR(A^.fg , x)
sinon Insère_ABR(A^.fd , x)
fsi
fsi
Fin

Genere_Noeud(var A:ABR; x : valeur)


Var q : ABR
Debut
créer( q )
q^.val := x
q^.fg := NIL
q^.fd := NIL
A := q
Fin

76
Opérations
3) La suppression d’un élément x dans un ABR A:
Supprimer 5 :

77
Opérations
Résultat : 6

4 9
Supprimer 4

2 8 10

1 3 7

78
Opérations
Résultat : 6

Supprimer 6 2 9

8 10
1 3

7
Remplacer 6 par :
-la plus grande valeur sous son fils gauche
-la plus petite valeur sous son fils droit

79
Résultat : 3

2 9

8 10
1

Ou
7
7

2 9

1 3 8 10
80
Supprime_ABR ( var A:ABR ; x : valeur)
Debut
si A ≠ NIL alors si A^.val = x
alors delete_noeud(A)
sinon si x < A^.val
alors Supprime_ABR(A^.fg , x)
sinon Supprime_ABR(A^.fd , x)
fsi
fsi
fsi
Fin

Delete_noeud (var A:ABR) upd_noeud ( var A , ptrfils : ABR )


Debut Debut
p := A si ptrfils ^.fd ≠ NIL
si A^.fg = NIL alors A := A^.fd alors upd_noeud(A , ptrfils^.fd)

liberer( p ) sinon A^.val := ptrfils ^.val


sinon si A^.fd = NIL alors A := A^.fg p := ptrfils
liberer( p ) ptrfils := ptrfils ^.fg
liberer( p )
sinon upd_noeud(A , A^.fg)
fsi
fsi
Fin
fsi
Fin
81
La Recherche est-elle optimale?
Exemple:
1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10
1

2
3
4

Arbre Dégénéré 6

7
Recherche lente
8

9
Recherche Séquentielle
10
82
7

9
4

2 5 8 10

1 3 6

Arbre Binaire de Recherche de


hauteur minimale
Optimisation sur les ABR
Arbres Equilibrés

83

Vous aimerez peut-être aussi