Table of Contents
Équilibrage des arbres binaire de recherche #
Arbres binaires de recherche #
Les arbres binaires de recherche ont pour but d’organiser une collection de valeur pour les retrouver plus facilement. Le principe est que chaque nœud de l’arbre a une valeur supérieure à la valeur de son fils gauche s’il existe, et inférieure à celle de son fils droit s’il existe.
Structure de données #
Un tel arbre peut être décrit par la structure de donnée suivante.
typedef struct Node_s {
int value ;
int height ;
struct Node_s* left ;
struct Node_s* right ;
} Node ;
Dans cette structure de données, nous avons en plus stocké la hauteur de l’arbre. Cette hauteur impacte directement la complexité des recherches d’éléments dans l’arbre : dans le pire des cas, il faut parcourir l’arbre de haut en bas, et donc le nombre d’opérations est proportionnel à cette hauteur.
Initialisation #
Commençons par coder l’initialisation d’un arbre. Au départ, sa hauteur est 0, et ses deux enfants sont des arbres vides.
.rawInput
#include <stdlib.h>
Node* tree_init(int value) {
Node* node = (Node*) malloc(sizeof(Node)) ;
node->value = value ;
node->height = 0 ;
node->left = NULL ;
node->right = NULL ;
return node ;
}
.rawInput
Insertion #
L’insertion compare le nouvel élément ajouté à la valeur de la racine de l’arbre. Si la valeur de la racine est plus forte, l’insertion est réalisée dans le sous-arbre gauche. Sinon l’insertion est réalisée dans le sous-arbre droit. Lorsque le bas de l’arbre est atteint, une nouvelle feuille est créée.
.rawInput
Node* tree_insert(Node* node, int value) {
if(node) {
/* nous ne sommes pas en bas de l'arbre */
if(value < node->value) {
/* la racine est plus forte, insertion à gauche */
node->left = tree_insert(node->left, value) ;
/* mise à jour de la hauteur */
if(node->height == node->left->height) {
++node->height ;
}
return node ;
} else {
/* la racine est plus faible, insertion à droite */
node->right = tree_insert(node->right, value) ;
/* mise à jour de la hauteur */
if(node->height == node->right->height) {
++node->height ;
}
return node ;
}
}
/* nous sommes en bas de l'arbre */
return tree_init(value) ;
}
.rawInput
Destruction #
Pour terminer notre structure de données, nous la dotons d’une fonction de destruction pour nettoyer la mémoire.
.rawInput
void tree_delete(Node* node) {
if(node){
tree_delete(node->left) ;
tree_delete(node->right) ;
free(node) ;
}
}
.rawInput
Affichage #
Ajoutons une fonction d’affichage pour visualiser l’arbre binaire obtenu
.rawInput
#include <cstdio>
static const char* SPLIT = "\xe2\x94\xa4" ;
static const char* V_BRANCH = "\xe2\x94\x82" ;
static const char* H_BRANCH = "\xe2\x94\x80" ;
static const char* UPPER_BRANCH = "\xe2\x95\xad" ;
static const char* LOWER_BRANCH = "\xe2\x95\xb0" ;
static void print_internal(Node* node, int depth, int code) {
int width = 5 ;
int w ;
if(node) {
print_internal(node->right, depth+1, code*2+1) ;
int i ;
for(i = 0; i < depth-1; ++i) {
if(((code >> (depth-i-1)) & 1 ) != ((code >> (depth-i-2)) & 1)) {
printf("%s",V_BRANCH) ;
} else {
printf(" ") ;
}
for(w = 0; w < width; ++w) {
printf(" ") ;
}
}
if(code%2) {
printf("%s",UPPER_BRANCH) ;
} else {
if(depth) {
printf("%s",LOWER_BRANCH) ;
}
}
if(depth) {
for(w = 0; w < width; ++w) {
printf("%s",H_BRANCH) ;
}
}
printf("%s",SPLIT) ;
printf("%d--%d", node->value, node->height) ;
printf("\n") ;
print_internal(node->left, depth+1, code*2) ;
}
}
static void tree_print(Node* node) {
return print_internal(node, 0, 0) ;
}
.rawInput
Premiers tests #
Nous pouvons tester notre mécanisme d’insertion en insérant des valeurs aléatoires dans l’arbre.
Node* tree = NULL;
for(int i = 0; i < 20; ++i) {
tree = tree_insert(tree, rand() % 100) ;
}
tree_print(tree) ;
╭─────┤93--3
│ │ ╭─────┤92--1
│ │ │ ╰─────┤90--0
│ ╰─────┤86--2
╭─────┤86--4
┤83--7
╰─────┤77--6
│ ╭─────┤72--0
│ ╭─────┤63--1
│ ╭─────┤62--2
│ │ ╰─────┤59--0
│ ╭─────┤49--3
│ │ ╰─────┤40--1
│ │ ╰─────┤36--0
│ ╭─────┤35--4
│ │ │ ╭─────┤27--2
│ │ │ │ │ ╭─────┤26--0
│ │ │ │ ╰─────┤26--1
│ │ ╰─────┤21--3
╰─────┤15--5
Pire cas #
Ces premiers tests nous laissent entrevoir le pire des cas pour la hauteur de l’arbre : les éléments insérés ne changent jamais de hauteur. Ainsi, un élément très faible déséquilibrera l’arbre vers sa droite. À l’inverse, un élément fort déséquilibrera à gauche. Dans le pire des cas, l’insertion des éléments se fait du plus faible au plus fort, ou inversement. Nous pouvons tester l’arbre obtenu ainsi :
tree_delete(tree) ;
tree = NULL ;
for(int i = 0; i < 20; ++i) {
tree = tree_insert(tree, i) ;
}
tree_print(tree) ;
╭─────┤19--0
╭─────┤18--1
╭─────┤17--2
╭─────┤16--3
╭─────┤15--4
╭─────┤14--5
╭─────┤13--6
╭─────┤12--7
╭─────┤11--8
╭─────┤10--9
╭─────┤9--10
╭─────┤8--11
╭─────┤7--12
╭─────┤6--13
╭─────┤5--14
╭─────┤4--15
╭─────┤3--16
╭─────┤2--17
╭─────┤1--18
┤0--19
Rééquilbrage par rotation #
Pour améliorer les arbres binaires, différentes stratégies existent pour rééquilibrer l’arbre au fur et à mesure des insertions. Cest stratégies sont le plus souvent basée sur le concept de rotation. Revenons à un arbre aléatoire.
tree_delete(tree) ;
tree = NULL ;
for(int i = 0; i < 20; ++i) {
tree = tree_insert(tree, rand() % 100) ;
}
tree_print(tree) ;
╭─────┤93--0
╭─────┤82--1
│ ╰─────┤69--0
╭─────┤68--8
│ │ ╭─────┤67--0
│ │ ╭─────┤67--1
│ ╰─────┤67--7
│ │ ╭─────┤62--4
│ │ │ │ ╭─────┤58--2
│ │ │ │ │ ╰─────┤56--1
│ │ │ │ │ ╰─────┤42--0
│ │ │ ╰─────┤35--3
│ │ ╭─────┤30--5
│ │ │ ╰─────┤29--0
│ ╰─────┤29--6
│ ╰─────┤23--2
│ ╰─────┤22--1
│ ╰─────┤11--0
┤11--9
╰─────┤2--0
Principe des rotations #
Une rotation a pour but de faire pivoter la racine d’un sous-arbre. La rotation à gauche fera descendre la racine vers la gauche de l’arbre, en amenant le fils droit de la racine comme nouvelle racine. À l’inverse, une rotation droite de l’arbre fait descendre la racine à droite en amenant son fils gauche à la racine.
Rotation droite #
A B
/ \ / \
B E → C A
/ \ / \
C D D E
Notez le déplacement du sous-arbre D : son placement dans l’arbre fait que ce sous-arbre est plus petit que A. Il peut donc légitimement être placé comme fils gauche de A.
Rotation gauche #
A C
/ \ / \
B C → A E
/ \ / \
D E B D
Notez le déplacement du sous-arbre D : son placement dans l’arbre fait que ce sous-arbre est plus grand que A. Il peut donc légitimement être placé comme fils droit de A.
.rawInput
int max(int a, int b) {
return a < b ? b : a ;
}
int lheight(Node* node) {
return node->left ? node->left->height : -1 ;
}
int rheight(Node* node) {
return node->right ? node->right->height : -1 ;
}
Node* rotate_left(Node* node) {
/* sauvegarde du fils droit */
Node* tmp = node->right;
/* remplacement du fils droit de la racine */
node->right = tmp->left ;
/* placement de la racine sous son fils droit */
tmp->left = node ;
/* recalcul des hauteurs */
node->height = max(lheight(node), rheight(node)) + 1 ;
tmp->height = max(lheight(tmp), rheight(tmp)) + 1 ;
/* renvoi de la nouvelle racine */
return tmp ;
}
Node* rotate_right(Node* node) {
/* sauvegarde du fils gauche */
Node* tmp = node->left;
/* remplacement du fils gauche de la racine */
node->left = tmp->right ;
/* placement de la racine sous son fils gauche */
tmp->right = node ;
/* recalcul des hauteurs */
node->height = max(lheight(node), rheight(node)) + 1 ;
tmp->height = max(lheight(tmp), rheight(tmp)) + 1 ;
/* renvoi de la nouvelle racine */
return tmp ;
}
.rawInput
Muni de ces rotations, nous pouvons maintenant tenter de réésuilibrer notre arbre.
tree = rotate_left(tree) ;
tree_print(tree) ;
╭─────┤93--0
╭─────┤82--1
│ ╰─────┤69--0
┤68--9
│ ╭─────┤67--0
│ ╭─────┤67--1
│ ╭─────┤67--7
│ │ │ ╭─────┤62--4
│ │ │ │ │ ╭─────┤58--2
│ │ │ │ │ │ ╰─────┤56--1
│ │ │ │ │ │ ╰─────┤42--0
│ │ │ │ ╰─────┤35--3
│ │ │ ╭─────┤30--5
│ │ │ │ ╰─────┤29--0
│ │ ╰─────┤29--6
│ │ ╰─────┤23--2
│ │ ╰─────┤22--1
│ │ ╰─────┤11--0
╰─────┤11--8
╰─────┤2--0
tree->left = rotate_left(tree->left) ;
tree_print(tree) ;
╭─────┤93--0
╭─────┤82--1
│ ╰─────┤69--0
┤68--9
│ ╭─────┤67--0
│ ╭─────┤67--1
╰─────┤67--8
│ ╭─────┤62--4
│ │ │ ╭─────┤58--2
│ │ │ │ ╰─────┤56--1
│ │ │ │ ╰─────┤42--0
│ │ ╰─────┤35--3
│ ╭─────┤30--5
│ │ ╰─────┤29--0
│ ╭─────┤29--6
│ │ ╰─────┤23--2
│ │ ╰─────┤22--1
│ │ ╰─────┤11--0
╰─────┤11--7
╰─────┤2--0
tree = rotate_right(tree) ;
tree_print(tree) ;
╭─────┤93--0
╭─────┤82--1
│ ╰─────┤69--0
╭─────┤68--2
│ │ ╭─────┤67--0
│ ╰─────┤67--1
┤67--8
│ ╭─────┤62--4
│ │ │ ╭─────┤58--2
│ │ │ │ ╰─────┤56--1
│ │ │ │ ╰─────┤42--0
│ │ ╰─────┤35--3
│ ╭─────┤30--5
│ │ ╰─────┤29--0
│ ╭─────┤29--6
│ │ ╰─────┤23--2
│ │ ╰─────┤22--1
│ │ ╰─────┤11--0
╰─────┤11--7
╰─────┤2--0
Nous avons réduit la hauteur de 1 ! Rééquilbrer un arbre très déséquilibrer s’avère néanmoins une tâche fastidieuse. Les stratégies pour maintenir un arbre binaire équilibré utilisent plutôt les rotations au fur et à mesure des insertions pour corriger les petits déséquilibres avant qu’ils ne dégénèrent.
AVL #
Les AVL sont uns stratégie classique pour maintenir un arbre équilibré. Ce n’est pas la seule, il en existe une multitude. Vous pouvez par exemple vous renseigner également sur les arbres rouge-noirs
Déséquilibre d’un nœud #
Le déséquilibre d’un nœud est defini comme la différence entre la hauteur de son sous-arbre gauche, et celle de son sous-arbre droit. Un arbre parfaitement équilibré aura un déséquilibre nul à chaque nœud. Un tel arbre n’est possible que si le nombre de nœud est très particulier (il doit être de la forme $2^k - 1$). Il est donc nécessaire d’autoriser un déséquilibre de 1 ou -1 sur les nœuds pour pouvoir avoir un nombre quelconque de nœuds. Les AVL corrigent le déséquilibre dès qu’il est au delà et vaut 2 ou -2.
Déséquilibre à gauche #
Lorsque le déséquilibre est de 2, le sous-arbre gauche est plus lourd que le sous-arbre droit. Dans ce cas, nous aurions envie de faire une rotation à droite.
tree_delete(tree) ;
tree = NULL ;
tree = tree_insert(tree, 3) ;
tree = tree_insert(tree, 2) ;
tree = tree_insert(tree, 1) ;
tree_print(tree) ;
tree = rotate_right(tree) ;
printf("\n \n") ;
tree_print(tree) ;
┤3--2
╰─────┤2--1
╰─────┤1--0
╭─────┤3--0
┤2--1
╰─────┤1--0
Cette stratégie ne marche cependant pas systématiquement.
tree_delete(tree) ;
tree = NULL ;
tree = tree_insert(tree, 3) ;
tree = tree_insert(tree, 1) ;
tree = tree_insert(tree, 2) ;
tree_print(tree) ;
tree = rotate_right(tree) ;
printf("\n \n") ;
tree_print(tree) ;
┤3--2
│ ╭─────┤2--0
╰─────┤1--1
╭─────┤3--1
│ ╰─────┤2--0
┤1--2
Dans la situation ci-dessus, le déséquilibre avait beau être à gauche, il n’était pas complètement à gauche, mais un peu au milieu. La rotation à droite ne rééquilibre en réalité que si le déséquilibre est complètement à gauche. Pour ramener le déséquilibre complètement à gauche, une première rotation gauche est nécessaire.
tree_delete(tree) ;
tree = NULL ;
tree = tree_insert(tree, 3) ;
tree = tree_insert(tree, 1) ;
tree = tree_insert(tree, 2) ;
tree_print(tree) ;
tree->left = rotate_left(tree->left) ;
printf("\n \n") ;
tree_print(tree) ;
┤3--2
│ ╭─────┤2--0
╰─────┤1--1
┤3--2
╰─────┤2--1
╰─────┤1--0
Une fois cette rotation préliminaire effectuée, le déséquilibre est complètement à gauche, et nous pouvons l’envoyer à droite par une rotation droite. comme précédemment.
Déséquilibre à droite #
La gestion d’un déséquilibre à droite suit le même principe. Lorsque le déséquilibre est complètement à droite, une rotation gauche suffit. Lorsque le déséquilibre est à droite, mais centré, une rotation droite préliminaire est nécessaire pour ramener le déséquilibre complètement à droite, avant de faire la rotation gauche.
Résumé des cas #
En résumé nous avons quatre cas :
- déséquilibre à la gauche de la gauche $\Rightarrow$ rotation droite
- déséquilibre à la droite de la gauche $\Rightarrow$ rotation gauche du fils gauche puis rotation droite
- déséquilibre à la droite de la droite $\Rightarrow$ rotation gauche
- déséquilibre à la gauche de la droite $\Rightarrow$ rotation droite du fils droit puis rotation gauche
La fonction d’insertion ci-dessous applique cette stratégie.
.rawInput
Node* tree_insert_balance(Node* node, int value) {
if(node) {
if(value < node->value) {
/* la racine est plus forte, insertion à gauche */
node->left = tree_insert_balance(node->left, value) ;
if(node->height == node->left->height) {
/* la hauteur a changé */
if(lheight(node) > rheight(node) + 1) {
/* le sous arbre est déséquilibré à gauche */
if(lheight(node->left) < rheight(node->left)) {
/* le sous arbre est déséquilibré à la droite de la gauche */
node->left = rotate_left(node->left) ;
}
/* rééqilibrage */
return rotate_right(node) ;
}
++node->height ;
}
return node ;
} else {
/* la racine est plus faible, insertion à droite */
node->right = tree_insert_balance(node->right, value) ;
if(node->height == node->right->height) {
/* la hauteur a changé */
if(rheight(node) > lheight(node) + 1) {
/* le sous arbre est déséquilibré à droite */
if(rheight(node->right) < lheight(node->right)) {
/* le sous arbre est déséquilibré à la gauche de la droite */
node->right = rotate_right(node->right) ;
}
/* rééquilibrage */
return rotate_left(node) ;
}
++node->height ;
}
return node ;
}
}
/* nous sommes en bas de l'arbre */
return tree_init(value) ;
}
.rawInput
Tests #
Nous pouvons maintenant tester l’équilibrage de nos arbres sur une séquence d’insertions aléatoires :
tree_delete(tree) ;
tree = NULL ;
for(int i = 0; i < 50; ++i) {
tree = tree_insert_balance(tree, rand() % 100) ;
}
tree_print(tree) ;
╭─────┤99--0
╭─────┤98--1
╭─────┤96--2
│ ╰─────┤95--0
╭─────┤91--3
│ │ ╭─────┤88--0
│ ╰─────┤87--2
│ │ ╭─────┤84--0
│ ╰─────┤84--1
╭─────┤84--4
│ │ ╭─────┤82--0
│ │ ╭─────┤81--1
│ ╰─────┤80--2
│ │ ╭─────┤78--0
│ ╰─────┤76--1
│ ╰─────┤73--0
╭─────┤73--5
│ │ ╭─────┤70--0
│ │ ╭─────┤70--1
│ │ ╭─────┤67--2
│ │ │ │ ╭─────┤64--0
│ │ │ ╰─────┤62--1
│ │ │ ╰─────┤57--0
│ ╰─────┤56--4
│ │ ╭─────┤54--0
│ │ ╭─────┤51--1
│ │ ╭─────┤50--2
│ │ │ │ ╭─────┤46--0
│ │ │ ╰─────┤45--1
│ │ │ ╰─────┤43--0
│ ╰─────┤37--3
│ │ ╭─────┤36--0
│ ╰─────┤34--1
│ ╰─────┤29--0
┤29--6
│ ╭─────┤27--0
│ ╭─────┤26--1
│ ╭─────┤25--2
│ │ │ ╭─────┤24--0
│ │ ╰─────┤24--1
╰─────┤21--4
│ ╭─────┤19--0
│ ╭─────┤15--2
│ │ │ ╭─────┤14--0
│ │ ╰─────┤13--1
╰─────┤13--3
│ ╭─────┤8--0
╰─────┤5--2
╰─────┤5--1
╰─────┤3--0
Nous pouvons également vérifier que même dans le cas de l’insertion d’une séquence triée qui était le pire cas d’un arbre binaire, nos arbres restent équilibrés.
tree_delete(tree) ;
tree = NULL ;
for(int i = 0; i < 50; ++i) {
tree = tree_insert_balance(tree, i) ;
}
tree_print(tree) ;
╭─────┤49--0
╭─────┤48--1
╭─────┤47--2
│ │ ╭─────┤46--0
│ ╰─────┤45--1
│ ╰─────┤44--0
╭─────┤43--3
│ │ ╭─────┤42--0
│ ╰─────┤41--1
│ ╰─────┤40--0
╭─────┤39--4
│ │ ╭─────┤38--0
│ │ ╭─────┤37--1
│ │ │ ╰─────┤36--0
│ ╰─────┤35--2
│ │ ╭─────┤34--0
│ ╰─────┤33--1
│ ╰─────┤32--0
┤31--5
│ ╭─────┤30--0
│ ╭─────┤29--1
│ │ ╰─────┤28--0
│ ╭─────┤27--2
│ │ │ ╭─────┤26--0
│ │ ╰─────┤25--1
│ │ ╰─────┤24--0
│ ╭─────┤23--3
│ │ │ ╭─────┤22--0
│ │ │ ╭─────┤21--1
│ │ │ │ ╰─────┤20--0
│ │ ╰─────┤19--2
│ │ │ ╭─────┤18--0
│ │ ╰─────┤17--1
│ │ ╰─────┤16--0
╰─────┤15--4
│ ╭─────┤14--0
│ ╭─────┤13--1
│ │ ╰─────┤12--0
│ ╭─────┤11--2
│ │ │ ╭─────┤10--0
│ │ ╰─────┤9--1
│ │ ╰─────┤8--0
╰─────┤7--3
│ ╭─────┤6--0
│ ╭─────┤5--1
│ │ ╰─────┤4--0
╰─────┤3--2
│ ╭─────┤2--0
╰─────┤1--1
╰─────┤0--0