البـــــوابـــة
La recherche en table et le tri peuvent être aussi traités avec des arbres. Nous l'avons vu implicitement dans le cas de Quicksort. En effet, si on dessine les partitions successives obtenues par les appels récursifs de Quicksort, on obtient un arbre. On introduit pour les algorithmes de recherche d'un élément dans un ensemble ordonné la notion d'arbre binaire de recherche celui-ci aura la propriété fondamentale suivante: tous les noeuds du sous-arbre gauche d'un noeud ont une valeur inférieure (ou égale) à la sienne et tous les noeuds du sous-arbre droit ont une valeur supérieure (ou égale) à la valeur du noeud lui-même (comme dans la figure 4.8). Pour la recherche en table, les arbres de recherche ont un intérêt quand la table évolue très rapidement, quoique les méthodes avec hachage sont souvent aussi bonnes, mais peuvent exiger des contraintes de mémoire impossibles à satisfaire. (En effet, il faut connaître la taille maximale a priori d'une table de hachage). Nous allons voir que le temps d'insertion d'un nouvel élément dans un arbre de recherche prend un temps comparable au temps de recherche si cet arbre est bien agencé. Pour le moment, écrivons les procédures élémentaires de recherche et d'ajout d'un élément.
static Arbre recherche (int v, Arbre a) {
if (a == null || v == a.contenu)
return a;
else if (v < a.contenu)
return recherche (v, a.filsG);
else
return recherche (v, a.filsD);
}
static Arbre ajouter (int v, Arbre a) {
if (a == null)
a = new Arbre (v, null, null);
else if (v <= a.contenu)
a.filsG = ajouter (v, a.filsG);
else
a.filsD = ajouter (v, a.filsD);
return a;
}
if (a == null)
return new Arbre (v, null, null);
else if (v <= a.contenu)
return new Arbre (v, ajouter (v, a.filsG), a.filsD);
else
return new Arbre (v, a.filsG, ajouter (v, a.filsG));
}
Le nombre d'opérations de la recherche ou de l'insertion dépend de la hauteur de l'arbre. Si l'arbre est bien équilibré, pour un arbre de recherche contenant N noeuds, on effectuera O(log N) opérations pour chacune des procédures. Si l'arbre est un peigne, c'est à dire complètement filiforme à gauche ou à droite, la hauteur vaudra N et le nombre d'opérations sera O(N) pour la recherche et l'ajout. Il apparaît donc souhaitable d'équilibrer les arbres au fur et à mesure de l'ajout de nouveaux éléments, ce que nous allons voir dans la section suivante.
Enfin, l'ordre dans lequel sont rangés les noeuds dans un arbre de recherche est appelé ordre infixe. Il correspond au petit numéro qui se trouve au dessus de chaque noeud dans la figure 4.8. Nous avons déjà vu dans le cas de l'évaluation des expressions arithmétiques (cf page X) l'ordre préfixe, dans lequel tout noeud reçoit un numéro d'ordre inférieur à celui de tous les noeuds de son sous-arbre de gauche, qui eux-mêmes ont des numéros inférieurs aux noeuds du sous-arbre de droite. Finalement, on peut considérer l'ordre postfixe qui ordonne d'abord le sous-arbre de gauche, puis le sous-arbre de droite, et enfin le noeud. C'est un bon exercice d'écrire un programme d'impression correspondant à chacun de ces ordres, et de comparer l'emplacement des différents appels récursifs.
4.5 Arbres équilibrés
La notion d'arbre équilibré a été introduite en 1962 par deux russes Adel'son-Vel'skii et Landis, et depuis ces arbres sont connus sous le nom d'arbres AVL. Il y a maintenant beaucoup de variantes plus ou moins faciles à manipuler. Au risque de paraître classiques et vieillots, nous parlerons principalement des arbres AVL. Un arbre AVL vérifie la propriété fondamentale suivante: la différence entre les hauteurs des fils gauche et des fils droit de tout noeud ne peut excéder 1. Ainsi l'arbre de gauche de la figure 4.8 n'est pas équilibré. Il viole la propriété aux noeuds numérotés 2 et 7, tous les autres noeuds validant la propriété. Les arbres représentant des tas, voir figure 4.5 sont trivialement équilibrés.
On peut montrer que la hauteur d'un arbre AVL de N noeuds est de l'ordre de log N, ainsi les temps mis par la procédure Recherche vue page X seront en O(log N).
Il faut donc maintenir l'équilibre de tous les noeuds au fur et à mesure des opérations d'insertion ou de suppression d'un noeud dans un arbre AVL. Pour y arriver, on suppose que tout noeud contient un champ annexe bal contenant la différence de hauteur entre le fils droit et le fils gauche. Ce champ représente donc la balance ou l'équilibre entre les hauteurs des fils du noeud, et on s'arrange donc pour maintenir -1 £ a.bal £ 1 pour tout noeud pointé par a.
L'insertion se fait comme dans un arbre de recherche standard, sauf qu'il faut maintenir l'équilibre. Pour cela, il est commode que la fonction d'insertion retourne une valeur représentant la différence entre la nouvelle hauteur (après l'insertion) et l'ancienne hauteur (avant l'insertion). Quand il peut y avoir un déséquilibre trop important entre les deux fils du noeud où l'on insère un nouvel élément, il faut recréer un équilibre par une rotation simple (figure 4.9) ou une rotation double (figure 4.10). Dans ces figures, les rotations sont prises dans le cas d'un rééquilibrage de la gauche vers la droite. Il existe bien sûr les 2 rotations symétriques de la droite vers la gauche. On peut aussi remarquer que la double rotation peut se réaliser par une suite de deux rotations simples. Dans la figure 4.10, il suffit de faire une rotation simple de la droite vers la gauche du noeud A, suivie d'une rotation simple vers la droite du noeud B. Ainsi en supposant déjà écrites les procédures de rotation rotD vers la droite et rotG vers la gauche, la procédure d'insertion s'écrit
static Arbre ajouter (int v, Arbre a) {
return ajouter1 (v, a).p2;
}
static Paire ajouter1 (int v, Arbre a) {
int incr, r;
Paire p;
r = 0;
if (a == null) {
a = new Arbre (v, null, null);
a.bal = 0;
r = 1;
} else {
if (v <= a.contenu) {
p = ajouter1 (v, a.filsG);
incr = -p.p1;
a.filsG = p.p2;
} else {
p = ajouter1 (v, a.filsD);
incr = p.p1;
a.filsD = p.p2;
}
a.bal = a.bal + incr;
if (incr != 0 && a.bal != 0)
if (a.bal < -1)
/* La gauche est trop grande */
if (a.filsG.bal < 0)
a = rotD (a);
else {
a.filsG = rotG (a.filsG);
a = rotD (a);
}
else
if (a.bal > 1)
/* La droite est trop grande */
if (a.filsD.bal > 0)
a = rotG (a);
else {
a.filsD = rotD (a.filsD);
a = rotG (a);
}
else
r = 1;
}
return new Paire (r, a);
}
static class Paire {
int p1;
Arbre p2;
Paire (int r, Arbre a) {
p1 = r;
p2 = a;
}
}
temps O(log N). On vérifie aisément qu'au plus une seule rotation (éventuellement double) est nécessaire lors de l'insertion d'un nouvel élément. Il reste à réaliser les procédures de rotation. Nous ne considérons que le cas de la rotation vers la droite, l'autre cas s'obtenant par symétrie.
static Arbre rotD (Arbre a) {
Arbre b;
int bA, bB, bAnew, bBnew;
b = a;
a = a.filsG;
bA = a.bal; bB = b.bal;
b.filsG = a.filsD;
a.filsD = b;
// Recalculer le champ a.bal
bBnew = 1 + bB - Math.min(0, bA);
bAnew = 1 + bA + Math.max(0, bBnew);
a.bal = bAnew;
b.bal = bBnew;
return a;
}
Il y a un petit calcul savant pour retrouver le champ représentant l'équilibre après rotation. Il pourrait être simplifié si nous conservions toute la hauteur du noeud dans un champ. La présentation avec les champs bal permet de garder les valeurs possibles entre -2 et 2, de tenir donc sur 3 bits, et d'avoir le reste d'un mot machine pour le champ contenu. Avec la taille des mémoires actuelles, ce calcul peut se révéler surperflu. Toutefois, soient h(a), h(b) et h(c) les hauteurs des arbres a, b et c de la figure 4.9. En appliquant la définition du champ bal, les nouvelles valeurs b'(A) et b'(B) de ces champs aux noeuds A et B se calculent en fonction des anciennes valeurs b(A) et b(B) par
Les formules pour la rotation vers la gauche s'obtiennent par symétrie. On peut même remarquer que le champ bal peut tenir sur 1 bit pour signaler si le sous-arbre a une hauteur égale ou non à celle de son sous-arbre ``frère''. La suppression d'un élément dans un arbre AVL est plus dure à programmer, et nous la laissons en exercice. Elle peut demander jusqu'à O(log N) rotations.
Les arbres AVL sont délicats à programmer à cause des opérations de rotation. On peut montrer que les rotations deviennent inutiles si on donne un peu de flexibilité dans le nombre de fils des noeuds. Il existe des arbres de recherche 2-3 avec 2 ou 3 fils. L'exemple le plus simple est celui des arbres 2-3-4 amplement décrits dans le livre de Sedgewick [47]. Un exemple d'arbre 2-3-4 est décrit dans la figure 4.11. La propriété fondamentale d'un tel arbre de recherche est la même que pour les noeuds binaires: tout noeud doit avoir une valeur supérieure ou égale à celles contenues dans ses sous-arbres gauches, et une valeur inférieure (ou égale) à celles de ses sous-arbres droits. Les noeuds ternaires contiennent 2 valeurs, la première doit être comprise entre les valeurs des sous-arbres gauches et du centre, la deuxième entre celles des sous-arbres du centre et de droite. On peut deviner aisément la condition pour les noeuds à 4 fils.
L'insertion d'un nouvel élément dans un arbre 2-3-4 se fait en éclatant tout noeud quaternaire que l'on rencontre comme décrit dans la figure 4.12. Ces opérations sont locales et ne font intervenir que le nombre de fils des noeuds. Ainsi, on garantit que l'endroit où on insère la nouvelle valeur n'est pas un noeud quaternaire, et il suffit de mettre la valeur dans ce noeud à l'endroit désiré. (Si la racine est quaternaire, on l'éclate en 3 noeuds binaires). Le nombre d'éclatements maximum peut être log N pour un arbre de N noeuds. Il a été mesuré qu'en moyenne très peu d'éclatements sont nécessaires.
static Arbre recherche (int v, Arbre a) {
if (a == null || v == a.contenu)
return a;
else if (v < a.contenu)
return recherche (v, a.filsG);
else
return recherche (v, a.filsD);
}
static Arbre ajouter (int v, Arbre a) {
if (a == null)
a = new Arbre (v, null, null);
else if (v <= a.contenu)
a.filsG = ajouter (v, a.filsG);
else
a.filsD = ajouter (v, a.filsD);
return a;
}
A nouveau, des programmes récursifs correspondent à la structure récursive des arbres. La procédure de recherche renvoie un pointeur vers le noeud contenant la valeur recherchée, null si échec. Il n'y a pas ici d'information associée à la clé recherchée comme au chapitre 1. On peut bien sûr associer une information à la clé recherchée en ajoutant un champ dans l'enregistrement décrivant chaque noeud. Dans le cas du bottin de téléphone, le champ contenu contiendrait les noms et serait du type String; l'information serait le numéro de téléphone.static Arbre ajouter (int v, Arbre a) {
La recherche teste d'abord si le contenu de la racine est égal à la valeur recherchée, sinon on recommence récursivement la recherche dans l'arbre de gauche si la valeur est plus petite que le contenu de la racine, ou dans l'arbre de droite dans le cas contraire. La procédure d'insertion d'une nouvelle valeur suit le même schéma. Toutefois dans le cas de l'égalité des valeurs, nous la rangeons ici par convention dans le sous arbre de gauche. La procédure ajouter modifie l'arbre de recherche. Si nous ne voulons pas le modifier, nous pouvons adopter comme dans le cas des listes la procédure suivante, qui consomme légèrement plus de place, laquelle place peut être récupérée très rapidement par le glaneur de cellules:
if (a == null)
return new Arbre (v, null, null);
else if (v <= a.contenu)
return new Arbre (v, ajouter (v, a.filsG), a.filsD);
else
return new Arbre (v, a.filsG, ajouter (v, a.filsG));
}
Le nombre d'opérations de la recherche ou de l'insertion dépend de la hauteur de l'arbre. Si l'arbre est bien équilibré, pour un arbre de recherche contenant N noeuds, on effectuera O(log N) opérations pour chacune des procédures. Si l'arbre est un peigne, c'est à dire complètement filiforme à gauche ou à droite, la hauteur vaudra N et le nombre d'opérations sera O(N) pour la recherche et l'ajout. Il apparaît donc souhaitable d'équilibrer les arbres au fur et à mesure de l'ajout de nouveaux éléments, ce que nous allons voir dans la section suivante.
Enfin, l'ordre dans lequel sont rangés les noeuds dans un arbre de recherche est appelé ordre infixe. Il correspond au petit numéro qui se trouve au dessus de chaque noeud dans la figure 4.8. Nous avons déjà vu dans le cas de l'évaluation des expressions arithmétiques (cf page X) l'ordre préfixe, dans lequel tout noeud reçoit un numéro d'ordre inférieur à celui de tous les noeuds de son sous-arbre de gauche, qui eux-mêmes ont des numéros inférieurs aux noeuds du sous-arbre de droite. Finalement, on peut considérer l'ordre postfixe qui ordonne d'abord le sous-arbre de gauche, puis le sous-arbre de droite, et enfin le noeud. C'est un bon exercice d'écrire un programme d'impression correspondant à chacun de ces ordres, et de comparer l'emplacement des différents appels récursifs.
4.5 Arbres équilibrés
La notion d'arbre équilibré a été introduite en 1962 par deux russes Adel'son-Vel'skii et Landis, et depuis ces arbres sont connus sous le nom d'arbres AVL. Il y a maintenant beaucoup de variantes plus ou moins faciles à manipuler. Au risque de paraître classiques et vieillots, nous parlerons principalement des arbres AVL. Un arbre AVL vérifie la propriété fondamentale suivante: la différence entre les hauteurs des fils gauche et des fils droit de tout noeud ne peut excéder 1. Ainsi l'arbre de gauche de la figure 4.8 n'est pas équilibré. Il viole la propriété aux noeuds numérotés 2 et 7, tous les autres noeuds validant la propriété. Les arbres représentant des tas, voir figure 4.5 sont trivialement équilibrés.
On peut montrer que la hauteur d'un arbre AVL de N noeuds est de l'ordre de log N, ainsi les temps mis par la procédure Recherche vue page X seront en O(log N).
Il faut donc maintenir l'équilibre de tous les noeuds au fur et à mesure des opérations d'insertion ou de suppression d'un noeud dans un arbre AVL. Pour y arriver, on suppose que tout noeud contient un champ annexe bal contenant la différence de hauteur entre le fils droit et le fils gauche. Ce champ représente donc la balance ou l'équilibre entre les hauteurs des fils du noeud, et on s'arrange donc pour maintenir -1 £ a.bal £ 1 pour tout noeud pointé par a.
L'insertion se fait comme dans un arbre de recherche standard, sauf qu'il faut maintenir l'équilibre. Pour cela, il est commode que la fonction d'insertion retourne une valeur représentant la différence entre la nouvelle hauteur (après l'insertion) et l'ancienne hauteur (avant l'insertion). Quand il peut y avoir un déséquilibre trop important entre les deux fils du noeud où l'on insère un nouvel élément, il faut recréer un équilibre par une rotation simple (figure 4.9) ou une rotation double (figure 4.10). Dans ces figures, les rotations sont prises dans le cas d'un rééquilibrage de la gauche vers la droite. Il existe bien sûr les 2 rotations symétriques de la droite vers la gauche. On peut aussi remarquer que la double rotation peut se réaliser par une suite de deux rotations simples. Dans la figure 4.10, il suffit de faire une rotation simple de la droite vers la gauche du noeud A, suivie d'une rotation simple vers la droite du noeud B. Ainsi en supposant déjà écrites les procédures de rotation rotD vers la droite et rotG vers la gauche, la procédure d'insertion s'écrit
static Arbre ajouter (int v, Arbre a) {
return ajouter1 (v, a).p2;
}
static Paire ajouter1 (int v, Arbre a) {
int incr, r;
Paire p;
r = 0;
if (a == null) {
a = new Arbre (v, null, null);
a.bal = 0;
r = 1;
} else {
if (v <= a.contenu) {
p = ajouter1 (v, a.filsG);
incr = -p.p1;
a.filsG = p.p2;
} else {
p = ajouter1 (v, a.filsD);
incr = p.p1;
a.filsD = p.p2;
}
a.bal = a.bal + incr;
if (incr != 0 && a.bal != 0)
if (a.bal < -1)
/* La gauche est trop grande */
if (a.filsG.bal < 0)
a = rotD (a);
else {
a.filsG = rotG (a.filsG);
a = rotD (a);
}
else
if (a.bal > 1)
/* La droite est trop grande */
if (a.filsD.bal > 0)
a = rotG (a);
else {
a.filsD = rotD (a.filsD);
a = rotG (a);
}
else
r = 1;
}
return new Paire (r, a);
}
static class Paire {
int p1;
Arbre p2;
Paire (int r, Arbre a) {
p1 = r;
p2 = a;
}
}
temps O(log N). On vérifie aisément qu'au plus une seule rotation (éventuellement double) est nécessaire lors de l'insertion d'un nouvel élément. Il reste à réaliser les procédures de rotation. Nous ne considérons que le cas de la rotation vers la droite, l'autre cas s'obtenant par symétrie.
static Arbre rotD (Arbre a) {
Arbre b;
int bA, bB, bAnew, bBnew;
b = a;
a = a.filsG;
bA = a.bal; bB = b.bal;
b.filsG = a.filsD;
a.filsD = b;
// Recalculer le champ a.bal
bBnew = 1 + bB - Math.min(0, bA);
bAnew = 1 + bA + Math.max(0, bBnew);
a.bal = bAnew;
b.bal = bBnew;
return a;
}
Il y a un petit calcul savant pour retrouver le champ représentant l'équilibre après rotation. Il pourrait être simplifié si nous conservions toute la hauteur du noeud dans un champ. La présentation avec les champs bal permet de garder les valeurs possibles entre -2 et 2, de tenir donc sur 3 bits, et d'avoir le reste d'un mot machine pour le champ contenu. Avec la taille des mémoires actuelles, ce calcul peut se révéler surperflu. Toutefois, soient h(a), h(b) et h(c) les hauteurs des arbres a, b et c de la figure 4.9. En appliquant la définition du champ bal, les nouvelles valeurs b'(A) et b'(B) de ces champs aux noeuds A et B se calculent en fonction des anciennes valeurs b(A) et b(B) par
|
Les formules pour la rotation vers la gauche s'obtiennent par symétrie. On peut même remarquer que le champ bal peut tenir sur 1 bit pour signaler si le sous-arbre a une hauteur égale ou non à celle de son sous-arbre ``frère''. La suppression d'un élément dans un arbre AVL est plus dure à programmer, et nous la laissons en exercice. Elle peut demander jusqu'à O(log N) rotations.
Les arbres AVL sont délicats à programmer à cause des opérations de rotation. On peut montrer que les rotations deviennent inutiles si on donne un peu de flexibilité dans le nombre de fils des noeuds. Il existe des arbres de recherche 2-3 avec 2 ou 3 fils. L'exemple le plus simple est celui des arbres 2-3-4 amplement décrits dans le livre de Sedgewick [47]. Un exemple d'arbre 2-3-4 est décrit dans la figure 4.11. La propriété fondamentale d'un tel arbre de recherche est la même que pour les noeuds binaires: tout noeud doit avoir une valeur supérieure ou égale à celles contenues dans ses sous-arbres gauches, et une valeur inférieure (ou égale) à celles de ses sous-arbres droits. Les noeuds ternaires contiennent 2 valeurs, la première doit être comprise entre les valeurs des sous-arbres gauches et du centre, la deuxième entre celles des sous-arbres du centre et de droite. On peut deviner aisément la condition pour les noeuds à 4 fils.
L'insertion d'un nouvel élément dans un arbre 2-3-4 se fait en éclatant tout noeud quaternaire que l'on rencontre comme décrit dans la figure 4.12. Ces opérations sont locales et ne font intervenir que le nombre de fils des noeuds. Ainsi, on garantit que l'endroit où on insère la nouvelle valeur n'est pas un noeud quaternaire, et il suffit de mettre la valeur dans ce noeud à l'endroit désiré. (Si la racine est quaternaire, on l'éclate en 3 noeuds binaires). Le nombre d'éclatements maximum peut être log N pour un arbre de N noeuds. Il a été mesuré qu'en moyenne très peu d'éclatements sont nécessaires.
