Arbres rouge et noir
Pourquoi ?
Parce que. Non, plus sérieusement, pourquoi expliquer une énième fois ce qu’est un arbre rouge et noir quand il y a tant de ressources à disposition ? De un, parce que j’ai envie. De deux, parce que en France, il n’y a pas grand monde qui sait ce que c’est − et c’est bien dommage, parce que c’est marrant. De trois, parce que ma fonction de suppression est géniale. Je m’adresse maintenant à ceux qui pensent que je vais parler horticulture : vous pouvez rester, mais la suite risque d’être assez pénible. Un petit test : regardez la page wikipédia sur les arbres rouge et noir en français − ça devrait être rapide, il n’y a pas grand chose. N’allez PAS voir celle en anglais. Elle est très complète, mais justement, il y a beaucoup d’infos qui ne sont pas forcément pertinentes, même si c’est vrai que les chercheurs adooooooorent présenter les arbres rouge et noir comme une manière d’abstraire un arbre B symétrique, lui même une abstraction de ce qu’est un arbre B d’ordre 4. Bon, j’espère qu’avec ça je vous ai convaincu. C’est pas que ce n’est pas intéressant, mais c’est pas forcément utile tout de suite maintenant. Donc restez au chaud chez moi, et vous pourrez aller regarder à la fin − si vos neurones fonctionnent encore évidemment :-).
Ensuite, les arbres rouge noir sont quand même très présents autour de nous, et ils reviennent régulièrement dans les discussions pour savoir si telle ou telle chose devrait être implémentée en utilisant l’un de ceux-là. Il y en a dans le noyau linux, et ce sont eux qui se cachent derrière les TreeSet/TreeMap de Java ou la std::map de C++. Donc oui, ils ont une réelle utilité − on note que ce n’est pas toujours le cas quand on parle de structures de données −, ce n’est pas juste un délire de chercheur.
Maintenant on commence à rentrer dans le vif du sujet. Un arbre rouge et noir (ou arbre bicolore) est un arbre binaire de recherche qui s’organise comme un grand pour être à peu près équilibré, on va voir comment. Parmi les ressources à disposition pour apprendre comment ça marche, il y a des tutos (en anglais) sur Internet, des slides de cours dans des universités américaines, quelques implémentations qui traînent, du pseudo-code, et un livre qui fait référence : “Introduction to Algorithms” de Cormen, Leiserson et Rivest (c’est le ‘R’ de ‘RSA’). Personnellement, je n’ai pas le bouquin, mais je suis tombé sur l’EXCELLENT tutoriel de Julienne Walker.
Le problème avec la majorité des ressources à disposition, c’est qu’elles présentent le sujet de la même manière, et trop souvent de manière incomplète. C’est à dire qu’ils expliquent comment insérer une valeur dans un arbre, mais pas comment la supprimer. Ou alors pire, ils ne donnent que le pseudo-code des méthodes − parfois même avec la mention “l’implémentation est laissée en exercice”.
Vous l’avez compris, l’implémentation est compliquée − ce serait un peu se foutre de vous que de dire que ce n’est pas le cas. D’un point de vue personnel, j’ai passé à peu près 30 heures à essayer de faire marcher mon arbre, et noirci un peu plus de 7 pages et quelques tableaux de croquis divers et variés. C’est beaucoup, parce qu’en suivant un simple article qui explique tous les cas possibles les uns après les autres, il y en a pour beaucoup moins de temps. Mais comme je n’étais pas satisfait des implémentations existantes, il fallait bien que je bosse un peu par moi-même pour en faire une nouvelle - de ce côté là j’aurais certainement mis plus longtemps sans le tutoriel précédent.
Petit background
Pour ceux qui auraient oublié ce que sont les arbres binaires de recherche - que je nommerai affectueusement ABR -, ce sont des structures de données qui permettent en général de rechercher une clé en O(log N). Ils ne sont pas idéaux, mais ont le mérite d’être simples. Ils ont quand même le défaut de ne pas bien réagir quand on insère des éléments dans un ordre particulier. Typiquement, insérez 1 000 éléments par ordre croissant et vous obtenez littéralement une liste chaînée - en forme de mille-pattes. 1 000 c’est beaucoup, donc je vais juste montrer pour 1,2,3,4,5.
Arbre Mille-pattes (à cinq pattes)
1
/ \ 1 -- 2 -- 3 -- 4 -- 5
2 | | | | |
/ \
3
/ \
4
/ \
5
/ \
On est d’accord, un arbre comme ça n’est pas très efficace, et il y a toujours un risque de tomber sur un cas pathologique.
Du coup, il y a pas mal de gens qui se sont efforcés de faire mieux, en faisant en sorte que l’arbre se réarrange de lui-même notamment. Il y a quelques structures qui sont aujourd’hui connues, comme les arbres AVL (AVL tree), les arbres étendus (splay tree), les arbres B (B tree), les arbres B+ (B+ tree) et encore quelques autres mais on en parlera pas.
Concernant les arbres rouges et noirs, leur nom vient du fait que les liens peuvent avoir deux couleurs : vert et bleu - non je déconne là. Dans certains articles, vous trouverez la mention de noeuds qui deviennent “double noir” - avec le nouvel Omo, lave plus noir que noir… ? - mais j’ai pas vraiment essayé de comprendre ce qu’ils entendaient par là donc on en parlera pas non plus. Et puis j’ai réussi sans, donc on fera sans.
Je sais bien que je vous avais dit qu’on ne parlerait pas des arbres B d’ordre 4, mais j’ai menti - méchant Dobby. J’en dirais juste que ce sont des arbres dont les noeuds peuvent avoir 2, 3 ou 4 fils. J’en parle parce que ça permet de comprendre les lois qui régissent les arbres rouge et noir, et que je préfère les introduire de façon logique et compréhensible plutôt que d’asséner “C’est comme ça et pas autrement”.
Cependant, les arbres B restent quand même des arbres ordonnés, donc quand un noeud gagne un fils il gagne une valeur. Un noeud d’ordre 2 stocke 1 valeur et 2 fils, un noeud d’ordre 3 stocke 2 valeurs et 3 fils, un noeud d’ordre 4 stocke 3 valeurs et 4 fils. Avec un dessin, ça donne ça.
Noeud d'ordre 2 Noeud d'ordre 3 Noeud d'ordre 4
1 1 3 1 3 5
/ \ / | \ / | | \
0 2 0 2 4 0 2 4 6
On s’arrêtera là pour ceux là. Maintenant il faut savoir qu’il y a une équivalence entre ce qu’il y a en haut et les arbres rouge noir - ils ont été conçus pour ça à la base. Pourtant les arbres rouge noir sont des arbres binaires - un noeud stocke une valeur et deux fils - alors comment faire pour représenter un noeud qui a plus de valeurs et d’enfants ? Et bien ça mon cher Fred, c’est parce qu’on peut considérer que les liens rouges sont des liens logiques et viennent étendre le noeud auquel ils sont liés pour en faire un noeud logique plutôt que lui rajouter un fils. Du coup, pour faire un noeud d’ordre 3 il faut un noeud dont un des fils soit rouge, et pour faire un noeud d’ordre 4 il faut que les deux fils soient rouges.
Pour l’exemple je vais représenter les noeuds du dessus dans le cas d’un arbre rouge noir. L’idée c’est qu’on peut représenter les liens rouges horizontalement. C’est joli, mais je ne le ferais qu’ici parce que c’est casse-pieds. Pour les notations, je stocke la couleur du lien à côté de la valeur du noeud.
Noeuds d'ordre 3 (deux possibilités) Noeud d'ordre 4
1,B−−3,R 1,R−−3,B 1,R−−3,B−−5,R
/ | \ / | \ / \ / \
0,B 2,B 4,B 0,B 2,B 4,B 0,B 2,B 4,B 6,B
Version arbre ça donne :
1,B 3,B 3,B
/ \ / \ / \
0,B 3,R 1,R 4,B 1,R 5,R
/ \ / \ / \ / \
2,B 4,B 0,B 2,B 0,B 2,B 4,B 6,B
Je l’ai déjà évoqué, mais on a besoin de stocker la couleur du lien. Pour cela, on va se mettre tout de suite d’accord qu’elle va se trouver dans les informations du noeud. Donc noeud rouge = noeud lié à son papa par un lien rouge. Ensuite on va se mettre d’accord sur le vocabulaire : comme je supporte la parité j’alternerai entre les termes papa et maman pour désigner le parent - le premier sang a été tiré à pile ou face.
Donc les liens rouges servent à étendre un autre noeud. On en déduit la première règle : la racine de l’arbre ne peut pas être rouge, puisqu’elle n’a pas de maman. Déjà une règle - plus que 2 -, la racine est toujours noire.
Ensuite, on peut en déduire de la même façon qu’il n’y a pas deux liens rouge consécutifs. C’est parce que la seule manière de faire un noeud d’ordre 4, c’est en lui collant deux noeuds rouge, un à droite et un à gauche. Règle elle-même définie par Sedgewick et Guidas quand ils ont proposé la structure de donnée. Bon, ça fait partie des règles, et au final ça nous arrange. Quand cette règle n’est pas respectée, on appelle ça une violation rouge - oui, ça sonne mieux en anglais (red violation) mais je fais ce que je peux pour traduire.
On a deux règles qui nous disent à peu près comment l’ensemble est fichu, mais jusqu’ici rien qui montre que c’est un type d’arbre relativement équilibré - on reviendra sur le relativement -, c’est le rôle de la 3e règle : Le chemin qui va de la racine à chacune des feuilles traverse le même nombre de noeuds noirs. On fait de la discrimination parce que les noeuds rouges font partie de noeuds logiques. Ce que cette règle veut dire, c’est que si vous prenez n’importe quel arbre rouge noir et que vous le dessinez comme je l’ai fait au début - les noeuds rouge à l’horizontale - alors TOUTES les feuilles s’arrêtent sur la même ligne. Perso je trouve que c’est plus simple dit comme ça. Si cette règle est enfreinte, on appelle ça une violation noire - ok là c’est presque trash, en anglais c’est comme vous vous en doutez black violation.
Je reviens rapidement sur la question de l’équilibrage - qui est quand même la raison principale qui fait que ces arbres existent. J’ai dit qu’ils sont relativement équilibrés, pour être plus précis ils sont équilibrés sans l’être - oui on vient de passer d’Einstein à Schrödinger, pas sur que ce soit mieux. Si on considère les arbres rouge noir sous la forme binaire - les noeuds rouges sont de vrais fils -, alors ils ne sont pas équilibrés, mais leur hauteur est comprise entre log N et 2log N - ça découle intuitivement des propriétés 2 et 3. Par contre, si on les représente sous forme de B arbre d’ordre 4 - les noeuds rouges à l’horizontale -, alors ils sont équilibrés. Donc ils sont équilibrés sans l’être. Magie ! Pour parler de la hauteur d’un arbre rouge et noir, on parle souvent de hauteur noire - le nombre de noeuds noirs traversés pour arriver à une feuille.
On résume rapidement les trois règles. J’ai mis les 2 et 3 de différentes manières parce que même si elles sont équivalentes, il y en a peut-être une que vous visualiserez mieux que l’autre.
- La racine est toujours noire (1)
- Un noeud rouge a un parent noir (2)
- Un noeud rouge n’a que des fils noirs (2)
- Il ne peut y avoir deux noeuds rouges consécutifs sur le même chemin (2)
- Le chemin qui va de la racine à chacune des feuilles comporte le même nombre de noeuds noirs (3)
- En représentant un arbre rouge noir avec les noeuds rouge à l’horizontale de leur papa, toutes les feuilles tombent sur la même ligne (3)
Violation rouge Violation rouge Violation noire Violation noire Combo !
2,B 4,B 2,B 2,B 4,B
/ \ / \ / \ / \ / \
1,R 4,R 1,R 6,R 1,B 0,R 1,B 6,B 1,B 6,R
/ / / / \ / \
0,R 5,R 0,B 4,R 8,R 5,B 7,R
Préparons l’implémentation
Bon, pour les préliminaires, sachez que j’ai fait mon arbre en Ruby. Si vous n’êtes pas très familiers, pas de panique. Déjà, je n’utilise pas de fonctionnalités très avancées ou de raccourcis de syntaxe aussi beaux qu’incompréhensibles. En fait, mon implémentation ressemble à ce que j’aurais fait en Java, mais en profitant - un peu - de la syntaxe de Ruby. Pour les spécificités, on verra ça en temps et en heure.
Il y a beaucoup d’implémentations qui utilisent une référence vers le noeud parent, ça rend les choses plus faciles. Moi pas. Si ça vous intéresse, il y a ce livre qui couvre une implémentation en utilisant un pointeur vers la maman et une autre en utilisant une pile au lieu de faire de la récursion. Encore une fois, je vous conseille de ne pas regarder le code qu’il fournit pour le moment. Déjà parce que c’est du C - ça pique un peu les yeux - et ensuite parce que sa méthode pour supprimer un noeud est pas belle - mais c’est celle qui est considérée comme une référence aujourd’hui (en particulier, c’est la manière la plus efficace de faire).
Dans un premier temps, il faut choisir ce que l’on met dans un noeud. Pour commencer une valeur - que j’appellerai clé par moments -, c’est ce qui va servir à faire les comparaisons. Pour la couleur, elle est classiquement représentée par un booléen donc je ne dérogerai pas à la règle. Pour les enfants d’un noeud, j’ai l’habitude de faire une référence right et left. Si le noeud est une feuille alors ces références sont à nil - le null de Ruby.
J’ai dis que j’ai l’habitude de faire ça, mais dans le cas présent je me suis rangé à la structure de Julienne Walker, à savoir un tableau qui contient les deux enfants. Le premier élément est le fils gauche, et le deuxième est le fils droit. C’est un peu déroutant au début, mais ça fait gagner beaucoup de lignes de code. Voici donc lesdites structures :
class RBNode
# Childs is an array of the two childs of the node
# Key contained in the node
# Color of the node
attr_accessor :childs, :key, :color
@@RED = true
@@BLACK = false
# Initializes a new node
def initialize(key = nil, color = @@RED)
@key = key
@color = color
@childs = [nil, nil]
end
def self.red
@@RED
end
def self.black
@@BLACK
end
def flip
@color = !@color
end
endEn décortiquant un peu, il n’y a rien de compliqué. Les variables RED et BLACK sont des variables de classe, et on leur associe les méthodes red et black respectivement pour pouvoir y accéder depuis l’extérieur (en Ruby les attributs sont tous privés par défaut). La ligne attr_accessor se charge de créer automatiquement les getter et setter des attributs concernés, donc ça fait du travail en moins. La méthode flip change la couleur d’un noeud (on s’en servira plus tard). On voit aussi que les noeuds sont rouges par défaut, mais là encore j’expliquerai tout en temps voulu. Ce qu’il y a à retenir : une clé pour comparer les noeuds, une couleur qui est un booléen, et un tableau pour stocker les fils d’un noeud.
Maintenant pour la représentation de l’arbre en lui même, on reste très simple, à savoir juste la racine de l’arbre. On peut aussi stocker la taille, mais c’est accessoire dans notre implémentation. Ce qui donne :
class RedBlackTreeST
# Initializes an empty tree
def initialize
@root = nil
end
endAvec ça, on est déjà capables de voir la différence entre une implémentation classique d’un noeud - avec références left et right explicites - et celle avec un tableau de fils à la place. On va prendre pour l’exemple l’insertion classique dans un arbre binaire de recherche selon les deux méthodes.
# Usual way
def insert(node, key)
return RBNode.new(key) if not node
cmp = key <=> node.key
return node if cmp == 0
if cmp < 0
node.left = insert(node.left, key)
else
node.right = insert(node.right, key)
end
return node
end
# My way (thanks to Julienne Walker)
class FalseClass; def to_i; 0; end end
class TrueClass; def to_i; 1; end end
def insert(node, key)
return RBNode.new(key) if not node
cmp = key <=> node.key
return node if cmp == 0
dir = (cmp > 0).to_i
node.childs[dir] = insert(node.childs[dir], key)
return node
endPetit point syntaxe. La traduction de “if not node” en Java, c’est “if (node != null)”, c’est juste une petite simplification. Un petit mot sur l’opérateur ‘<=>‘. En Ruby il s’agit de l’opérateur de comparaison, c’est à dire que a <=> b rend -1 si a < b, 0 si a == b et 1 si a > b. Le résultat nous aide à choisir la direction à prendre. C’est tout l’intérêt des méthodes to_i que l’on a rajouté dynamiquement aux booléens de ruby (TrueClass et FalseClass). Si la clé est plus grande que celle du noeud courant on va à droite, si elle est plus petite on va à gauche et sinon on s’arrête parce que la clé est déjà présente. Ce petit trick va quand même nous faire gagner beaucoup de lignes, et au final ce n’est pas si compliqué.
Une petite note, je n’ai trouvé cette manière de faire - le tableau de fils - nulle part ailleurs, alors qu’elle a toute les raisons d’être répandue. Sachant que les arbres rouge et noir existent depuis 1978, c’est quand même un peu dommage de s’en tenir à de légères variantes d’une unique implémentation. Je ne sais pas trop comment l’interpréter, mais comme les arbres rouge noir ont une sale réputation - j’ai trouvé le terme de ‘structure diabolique’ - on préfère s’en tenir à copier une implémentation/méthode qui marche − voire à ne rien implémenter du tout − plutôt que de chercher un meilleur moyen, comme ça on est sur de ne pas se tromper. De mon point de vue, c’est triste.
Préliminaires
Bon, maintenant qu’on sait comment la structure est faite, on va s’intéresser d’un peu plus près à comment ça marche. Vous vous souvenez, j’ai dit que les arbres rouge et noir étaient capables de s’auto-équilibrer. C’est bien joli, mais ce n’est pas magique et il va falloir l’implémenter avec nos petites mains. Et sans rien casser - c’est à dire en respectant les règles -, sinon c’est pas drôle. On va commencer par parler un peu desdites règles. Pour la première, pas de souci, c’est facile.
Maintenant au niveau des violations, les deux sont mauvaises mais il y en a une moins pire que l’autre. Dans le cas d’une violation noire, c’est l’arbre entier qui est corrompu, mais dans le cas d’une violation rouge, ce sont seulement deux noeuds. Par nature, les violations rouges sont très localisées, alors que les violations noires sont globales. Du coup, si on a vraiment pas le choix on préférera induire une violation rouge pour la réparer après plutôt qu’une violation noire.
Encore une chose avant de vraiment commencer − promis c’est la dernière. Une fonction d’aide c’est bien, donc on va allègrement utiliser la fonction suivante pour savoir si un noeud est rouge ou pas.
def red?(x)
x and x.color
endRien de compliqué vous le voyez. On va continuer l’échauffement avec une fonction pour modifier la couleur d’un noeud et de ses deux fils. Plus précisément, il s’agit d’écrire une fonction pour passer de l’arbre droit à l’arbre gauche, ou du gauche vers le droit.
1,R 1,B
/ \ <---> / \
0,B 2,B 0,R 2,R
Contrat respecté, on n’a généré aucune violation noire. Et si on a fait attention, alors on a pas non plus provoqué de violation rouge. Cette première fonction est dédiée à simplement switcher les couleurs, et ça va nous permettre de retrouver la fonction flip que l’on avait laissée un peu plus haut.
def flip_colors(x)
x.flip
x.childs[0].flip
x.childs[1].flip
endPlace maintenant aux rotations, j’en distingue deux types : les simples et les doubles - on verra pourquoi après. En gros, ça consiste à bouger quelques noeuds, mais de manière à ne pas provoquer de violations. C’est quelque chose de commun à tout les arbres qui s’auto-ajustent, en même temps il faut bien qu’ils trouvent un moyen de garder l’équilibre - sans roulettes. C’est véritablement là que joue l’importance d’avoir stocké des fils dans un tableau et pas explicitement : les implémentations classiques distinguent deux types de rotation : vers la droite et vers la gauche. Les deux sont exactement les même, sauf que l’on substitue les appels à left par des appels à right et vice versa. Chez nous, il y a juste à connaître la direction et le tour est joué. Assez parlé, le dessin - je considère maintenant que je montre n’importe quel sous-arbre de l’arbre, sans indiquer la racine ni les feuilles.
Rotation vers la droite Rotation vers la gauche (la même mais à l'envers)
4,B 1,B 1,B 4,B
/ \ / \ / \ / \
1,R 5,B --> 0,B 4,R 0,B 4,R --> 1,R 5,R
/ \ / \ / \ / \
0,B 2,B 2,B 5,B 2,B 5,R 0,B 2,B
Un point très important de cette manière de procéder : aucune violation n’est ajoutée à l’arbre. Vous pouvez prendre une feuille et un crayon pour essayer, mais vous verrez qu’en suivant ce principe on n’induit pas de violation, ni rouge ni noire. En fait, on va même s’en servir pour ‘réparer’ notre arbre, comme sur l’exemple de droite où on supprime une violation rouge. Comme la rotation est un peu le seul élément dont on dispose pour réorganiser notre arbre, elle a bien méritée sa fonction à elle.
def rotate_once(x, dir)
y = x.childs[dir^1]
x.childs[dir^1] = y.childs[dir]
y.childs[dir] = x
y.color = x.color
x.color = RBNode.red
return y
endPas de problème particulier ici, c’est juste l’exacte translation de ce qui se passe au dessus. Le chapeau c’est le symbole du XOR en Ruby, ça permet de choisir la direction opposée − 0^1 = 1 et 1^1 = 0. Vous aurez remarqué que la fonction est très spécifique dans l’affectation des couleurs − Fixer la couleur de x à rouge alors qu’il n’a rien demandé. C’est simplement que cette fonction est appelée pour passer un noeud rouge de droite à gauche ou de gauche à droite, jamais autre part. Maintenant, on va voir à quoi ressemble une rotation double. Pas d’inquiétude, c’est simplement deux fois la première − étonnant −, et on va aussi s’en servir pour supprimer une violation rouge :
Arbre initial Après rotation de 3 autour de 2 Après rotation de 3 autour de 5
5,B 5,B 3,B
/ \ / \ / \
2,R 6,B ---> 3,R 6,B -----> 2,R 5,R
/ \ / \ / / \
0,B 3,R 2,R 4,B 0,B 4,B 6,B
\ /
4,B 0,B
Cette rotation là n’a pas le droit à sa propre méthode, par contre on peut quand même les factoriser toutes les deux, mais vous le verrez très bien quand on y arrivera.
L’assurance vie
Ça y est, fini de s’échauffer, vous êtes enfin prêts à voir comment insérer un item dans un arbre rouge et noir ! Mais avant, cette partie est à destination de ceux qui veulent réellement implémenter un tel arbre − pas juste recopier du code trouvé sur Internet. Je vous encourage VIVEMENT à écrire une fonction qui va vérifier si votre arbre est correct ou pas. Sans rire, ça a sauvé des vies − au moins la mienne. Ce n’est pas très dur, juste un peu de récursion en faisant attention à ce que les propriétés énoncées soient respectées. Une fois n’est pas coutume, je ne vais pas donner de solution ici. Considérez ça comme une mise en bouche avant l’entrée - l’insertion. Pour les flemmards − dont je fais partie −, Julienne Walker en a écrit une ici en C. Cependant, si vous avez des difficultés à faire cela, je vous conseille de vous rabattre sur un vulgaire arbre binaire de recherche, parce que vous n’êtes pas au bout de vos peines.
Insertion
Bon, tout le monde est prêt ? Alors on peut commencer à vraiment travailler sur les deux opérations majeures d’un arbre, en commençant par la plus simple : l’insertion. Sachant qu’un noeud peut-être rouge ou noir, de quelle couleur doit être le noeud qu’on insère ? C’est pas compliqué, on va juste dérouler les cas. Déjà, le nouveau noeud va forcément être une feuille, ça simplifie les choses. Dans le cas où il est noir, on va avoir à tous les coups une violation noire. Pour vous en convaincre, représentez juste l’arbre rouge noir avec des noeuds rouges à l’horizontale. Si vous voulez ajoutez une feuille noire, cela créé forcément un niveau puisque l’arbre est équilibré au départ.
Maintenant, si vous voulez ajouter un noeud rouge, il y a une chance pour que ça se passe bien : si vous l’accrochez à un papa noir. Dans le cas ou la maman est rouge, alors il y a une violation rouge qu’il va falloir résoudre, mais chaque chose en son temps. Comme on a déjà montré pourquoi les violations rouges c’était moins compliqué que les violations noires, on est fixé sur la couleur du nouveau noeud : rouge. C’est bien, ça permet de faire le lien avec la valeur par défaut du constructeur de RBNode. Si on récapitule l’insertion, ça donne ça.
def insert(key)
@root = insert_h(@root, key)
@root.color = RBNode.black
end
def insert_h(node, key)
return RBNode.new(key) if not node
cmp = key <=> node.key
return node if cmp == 0
dir = (cmp > 0).to_i
node.childs[dir] = insert_h(node.childs[dir], key)
# Ici on réorganise l'arbre
return node
endOn l’avait déjà vu avant, mais on va s’attarder un peu plus sur comment le code marche. Déjà, il ne faut pas oublier de remettre la racine noire à la fin de l’insertion, sinon la suite ne va pas très bien se passer. Ensuite, il y a deux principes clés dans cette fonction : la récursion et l’approche ascendante.
La récursion, c’est simplement appeler insert_h dans insert_h, et on s’arrête quand on a trouvé que la clé à insérer est déjà présente ou que l’on a atteint une feuille. C’est aussi une méthode élégante de résolution de problèmes, c’est pour ça que je l’aime. Rien de transcendant, mais quand on travaille avec des arbres c’est la base. Pour l’approche ascendante (bottom-up), c’est juste que l’on modifie l’arbre en remontant. Le principe est le suivant : on descend tout en bas de l’arbre pour introduire le nouveau noeud. Si il y a une violation on la règle et on monte au niveau supérieur, et on recommence jusqu’à atteindre la racine.
Il ne reste plus qu’à définir ces fameuses violations pour pouvoir les régler, et on en parle plus. On s’était mis d’accord pour dire que la seule violation possible, c’est une violation rouge, alors il ne reste plus qu’à énumérer les cas. Deux cas possibles : le nouveau noeud est lié à un papa rouge qui a un frère rouge ; le nouveau noeud est lié à une maman rouge qui n’a pas de frère ou est fille unique. Pour ce dernier cas, deux variantes sont à considérer. Comme souvent, c’est plus clair avec un dessin − pour s’y retrouver dans chacun des exemples, le nouveau noeud inséré portera le numéro 42.
Cas 1 Cas 2 Cas 2 bis
1,B 1,B 1,B
/ \ / \ / \
0,R 2,R 0,B 2,R 0,B 50,R
\ \ /
42,R 42,R 42,R
Normalement, vous devriez reconnaître les 3 cas que l’on avait étudié pour définir nos fonctions d’aide : changement de couleur, rotation simple et rotation double. Si ce n’est pas évident ce n’est pas grave, on est là pour ça. Je vais donc détailler comment résoudre ces trois conflits. Si vous êtes observateurs, vous aurez vu que les cas 2 et 2 bis de l’exemple comportent une violation noire. Comme on insère un noeud dans un arbre rouge noir valide, cela n’arrivera jamais et ces exemples servent seulement à illustrer comment se débarasser d’une violation rouge, donc inutile de s’en préoccuper.
Cas 1 Après changement de couleur
1,B 1,R
/ \ / \
0,R 2,R ----> 0,B 2,B
\ \
42,R 42,R
Pour le premier cas, l’objectif est rempli : il n’y a plus de violation en bas, cependant on a changé la couleur du noeud parent. Ceci peut donc provoquer une autre violation rouge un niveau plus haut si le parent du parent est rouge lui aussi. Et c’est précisément pour cela qu’on utilise la récursion. Maintenant que le travail est fait dans la couche inférieure, on laisse la fonction remonter toute seule et appliquer le même traitement à la couche supérieure. Ça marche comme cela parce que les cas considérés sont les mêmes quelque soit le niveau. L’insertion d’un noeud rouge ne provoque pas de violation noire et toute les transformations que l’on effectue n’en induisent pas. Et au niveau des violations rouges, les trois seuls cas possibles sont ceux que j’ai détaillé. Si vous n’êtes pas sur, prenez une feuille et faîtes un dessin pour vous en convaincre :-).
Cas 2 Après rotation de 2 autour de 1
1,B 2,B
/ \ / \
0,B 2,R ----> 1,R 42,R
\ /
42,R 0,B
Là encore, il s’agit simplement de ce que l’on a vu plus haut. Cependant, on peut remarquer que si cette opération a lieu, alors on supprime définitivement la violation rouge. Cette fois-ci on ne remonte pas de parent rouge, et les rotations n’introduisent pas de violation. Il nous reste un dernier cas à traiter et tout sera bon !
Cas 2 bis Après rotation de 42 autour de 50 Après rotation de 42 autour de 1 (cas 2)
1,B 1,B 42,B
/ \ / \ / \
0,B 50,R ----> 0,B 42,R ----> 1,R 50,R
/ \ /
42,R 50,R 0,B
Et voilà, tous les cas sont bouclés, on a supprimé les violations rouges potentielles. En terme de code, cela se fait très simplement, sans ajouter beaucoup de lignes.
def insert_h(node, key)
return RBNode.new(key) if not node
cmp = key <=> node.key
return node if cmp == 0
dir = (cmp > 0).to_i
node.childs[dir] = insert(node.childs[dir], key, value)
if red?(node.childs[dir])
if red?(node.childs[dir^1])
flip_colors(node)
else
node.childs[dir] = rotate_once(node.childs[dir], dir) if red?(node.childs[dir].childs[dir^1])
node = rotate_once(node, dir^1) if red?(node.childs[dir].childs[dir])
end
end
return node
endJ’avais mentionné la factorisation de la rotation simple et double, vous pouvez ici voir ce que ça donne. Pour le coup, je ne m’attend pas à être cru sur parole, alors tracez l’exécution du code si vous le souhaitez :-). En tout cas, le résultat final est à la fois simple, élégant et fonctionnel, ce qui est le principal − les trois à la fois, pas que le dernier. Pour ce qui se passe lors d’une insertion, le principe est simple : en remontant l’arbre, on swap les couleurs dès que possible jusqu’à effectuer une rotation qui supprime pour de bon la violation. Il peut aussi arriver que l’on remonte tout l’arbre jusqu’à la racine en inversant les couleurs. Dans ce cas, la racine va tout de même être remise en noir, souvenez-vous.
Allez, on va faire un dernier exemple un peu plus complet sur un arbre valide pour le plaisir et on en aura fini de l’insertion :-).
Insertion de 7 Flip_colors Rotation de 3 autour de 1
1,B 1,B 1,B 3,B
/ \ / \ / \ / \
0,B 3,R 0,B 3,R 0,B 3,R 1,R 5,R
/ \ ---> / \ ---> / \ ---> / \ / \
2,B 5,B 2,B 5,B 2,B 5,R 0,B 2,B 4,B 6,B
/ \ / \ / \ \
4,R 6,R 4,R 6,R 4,B 6,B 7,R
\ \
7,R 7,R
Une dernière précision sur l’insertion : elle nécessite très peu de rotations. Si vous avez fait attention, vous aurez vu qu’une seule rotation (simple ou double) suffisait à restaurer les règles d’un arbre binaire rouge noir, donc lors d’une insertion, il y a au plus deux rotations effectuées.
A ce niveau là, vous pouvez avoir envie d’une pause − c’est compréhensible −, alors faîtes-en une si vous le voulez. Si vous n’êtes pas convaincu par ce que j’ai dit, libre à vous de manipuler d’autres arbres pour vous en convaincre. De même, si vous vous sentez légèrement fatigué, prenez une pause, cet article sera toujours là quand vous reviendrez. Je dis ça car comparé à la suppression, l’insertion d’un noeud dans un arbre rouge noir c’est de la rigolade. Non ? Pas de pause ? J’aurais prévenu :-).
Suppression
Re-bienvenue ! Prêts pour les choses sérieuses ? Moi non plus. J’ai mentionné au début qu’une partie non négligeable des articles ou des implémentations d’arbres rouge noir ne comportaient pas la suppression de clé - si quelqu’un a une idée de l’utilité de cette démarche, je suis preneur. Et l’autre partie implémente une version presque toute faite qui sort d’un bouquin. Je n’ai pas parlé de longueur de code au début pour ne pas vous faire partir, mais ma version fait 24 lignes − 26 pour la lisibilité, 33 si on ne conserve que les fonctions d’aide définies jusqu’à présent. Le souci, c’est que toutes les autres implémentations que j’ai vu en procédural en font plus de 100. Pour être plus précis, en C on tourne allègrement autour de 150 − parfois bien plus. En Java, j’en ai vu une d’un peu plus de 100 lignes. Et en Ruby, j’ai vu 75. En fait, la plus courte que j’ai vu est celle fournie par Julienne Walker (top-down deletion). Vous pourrez arguer que Ruby est un langage de plus haut niveau, donc c’est normal que cela prenne moins de lignes. Certes, mais ce que je fais en une ligne en ruby, c’est aussi possible de le faire en une ligne en C (peut-être 2 dans un ou deux cas particuliers, mais c’est tout).
La plus grosse différence vient de la manière dont est implémentée cette méthode de suppression. Dans l’immense majorité des cas, on fait pareil que pour l’insertion : on supprime le noeud visé, puis on remonte en réparant ce qui est cassé. Sauf qu’il y a bien plus de cas à considérer, donc en général il ne s’agit pas de programmation mais de répondre aux cas les uns après les autres (il y en a 6) comme sur l’article de wikipédia version anglaise. Certes au final l’algorithme est récursif, mais il n’est ni simple ni élégant, c’est pour cela que j’en ai implémenté une variante.
L’implémentation de Julienne et la mienne diffèrent des autres en cela qu’au lieu de descendre tout l’arbre et d’ensuite réparer, l’idée est de pousser un noeud rouge du haut de l’arbre vers la feuille à supprimer PENDANT la descente. Et c’est tout. Enfin un dernier point concernant mon implémentation − oui c’est le dernier − : pour la suppression, toutes les implémentations que j’ai vu − même celle de JW − gardent un pointeur sur le noeud courant, son père, son grand-père, son frère et parfois son oncle. Chez moi, rien de tout ça, on se débrouille comme des grands à partir du noeud courant. Petite note pour la suite. Je peux employer l’expression “son fils” alors qu’un noeud en a deux. Cela signifie “l’arbre fils qui contient le noeud à supprimer”, donc en gros la direction à prendre.
Voilà, maintenant vous êtes fin prêts pour apprendre à supprimer une clé d’un arbre rouge noir ! Comme pour l’insertion, on va partir de la suppression pour un arbre binaire et faire des modifications ensuite. L’idée est simple dans le cas d’un arbre binaire : Si le noeud à supprimer est une feuille tout se passe bien. Si ce n’est pas une feuille, alors il prend la valeur de son successeur direct, et on supprime la feuille qui contient le successeur − qui ne sert plus à rien. Sur un arbre binaire, le successeur direct d’un noeud x est le plus petit noeud du sous-arbre droit de x. On le choisit lui car il a le bon gout de ne pas poser de problème : l’arbre est encore un arbre binaire. Dans l’exemple suivant, 2 est le noeud à supprimer.
On remplace 2 par son successeur On supprime le successeur
2 3 3
/ \ / \ / \
1 4 ---> 1 4 ---> 1 4
/ \ / \ \
3 5 3 5 5
Déjà très bonne nouvelle, puisque l’on vient de réduire le problème à “Comment supprimer une feuille ?”. De manière analogue à l’insertion, supprimer une feuille noire va causer une violation noire, et on aime pas ça. Par contre, si on pouvait supprimer une feuille rouge, ça ce serait bien ! On ne causerait même pas de violation rouge ! En fait, on va même étendre légèrement ce cas. Si on pouvait supprimer une feuille rouge où une feuille noire qui est liée à une feuille rouge ça serait bien.
Ok, ça mérite quelques explications, ce n’est pas aussi évident que ça en a l’air. Dans un arbre rouge noir, une feuille est un noeud qui a au plus un fils − sinon ce n’est pas une feuille. En fait, il y a trois cas possibles de feuilles qui ne violent aucune des règles de l’arbre :
Feuille rouge seule (1 et 3) Feuille noire seule (1 et 3) Feuille noire accompagnée (1 et 3)
2,B 2,R 2,R
/ \ / \ / \
1,R 3,R 1,B 3,B 1,B 3,B
/ \
0,R 4,R
Et il n’y a que ces trois cas là. Si une feuille est rouge, elle ne peut pas avoir de fils rouge (violation rouge) ni de fils noir (violation noire). Et si une feuille est noire, elle ne peut avoir qu’un fils rouge ou pas de fils du tout. Maintenant, souvenez-vous que l’objectif est qu’à chaque instant de la descente, le noeud courant ou son fils soit rouge. Donc, on ne sera jamais dans le cas d’un noeud noir seul, puisque ce noeud est noir et que ses fils ne sont pas rouges − il n’en a pas.
On est en droit de se demander ce que ça pourrait donner de supprimer une feuille dans les cas 1 et 3. Voici donc :
Arbre 1 Suppression de 0 Suppression de 3
2,R 2,R 2,R
/ \ / \ / \
1,B 3,B ---> 1,B 3,B ---> 1,B 4,B
/ \ \
0,R 4,R 4,R
Et voilà, il n’y a rien d’autre à faire, nous avons traité les deux cas de suppression de feuille. Il ne reste plus qu’à trouver comment descendre le noeud rouge et nous en aurons fini. Encore une fois, plusieurs cas se présentent, on va commencer par le plus facile : le changement de couleur.
2,R 2,B
/ \ ---> / \
1,B 3,B 1,R 3,R
ATTENTION : ce n’est pas tout à fait comme dans le cas de l’insertion. Rappelez-vous, en insérant on remontait l’arbre, donc on pouvait causer au plus une violation. Ici, on descend le noeud rouge, donc on peux en causer 4 en tout. En fait, on utilise cette méthode uniquement lorsque les petits-fils du noeud courant sont noirs ou nuls. Sinon, on va se retrouver avec un arbre invalide et ce n’est pas génial. Mais l’objectif est quand même atteint : la branche vers laquelle on se dirige est colorée en rouge. Je ne redonne pas l’implémentation de ceci, il s’agit de la méthode flip_colors que l’on a vu précédemment.
Le deuxième cas est à peine plus compliqué, il s’agit d’une rotation simple. Dans l’exemple suivant, imaginez que la valeur que l’on cherche à supprimer se trouve dans le sous-arbre droit (ça marche de la même manière en inversant les côtés).
1,B 0,B
/ \ ---> \
0,R 2,B 1,R
\
2,B
Encore une fois, objectif atteint. La branche vers laquelle on se dirige est rouge, et nous n’avons pas introduit de violation en effectuant la transformation. Il s’agit d’une simple rotation vers la droite dont encore une fois je ne redonnerai pas le code.
On arrive au deux derniers cas à traiter, qui sont une rotation simple et une rotation double. La question est la suivante : “Mon fils et ses fils sont noirs, comment est-ce que j’introduis un noeud rouge dans tout ça ?”. La réponse est : “Va le chercher du côté de l’autre branche”. Mettons que le noeud que l’on veut supprimer se trouve à droite. L’idée des deux derniers cas est de voler un noeud rouge à gauche pour le mettre à droite, et donc s’assurer qu’à tout moment le noeud courant ou son fils soit rouge. Cette opération est réalisée grâce à une astucieuse combinaison de rotations et de coloration.
Cas 3 (rotation simple)
2,R 1,R
/ \ / \
1,B 3,B ---> 0,B 2,B
/ \
0,R 3,R
Cas 3 bis (rotation double)
2,R 1,R
/ \ / \
0,B 3,B ---> 0,B 2,B
\ \
1,R 3,R
Une nouvelle fois, on a réussi à déplacer un noeud rouge sans créer de violations. Pour le coup, ces transformations méritent que l’on s’y attarde, parce qu’il y a une nuance dans la réalisation. Si l’on se contente de la fonction rotate_once que l’on connait, les couleurs ne seront pas les bonnes. Et c’est la que la fonction flip_colors intervient, elle va nous permettre de correctement colorier tous ces noeuds !
En fait, on va même définir une fonction d’aide qui va gérer toute seule les cas 3 et 3 bis. Ça rendra la fonction de suppression plus lisible. Alors voici.
def rotate_del(node, dir)
flip_colors(node)
node.childs[dir^1] = rotate_once(node.childs[dir^1], dir^1) if red?(node.childs[dir^1].childs[dir])
node = rotate_once(node, dir)
flip_colors(node)
return node
endAlors là, je vous conseille de prendre le temps de comprendre comment ça marche, et de vous convaincre que cette fonction produit l’effet escompté et n’a pas d’effets de bords comme colorier d’autres noeuds sans qu’on ne l’ait voulu. Je vous rassure, une fois que vous avez compris ça vous êtes tout bon, et on passera à la fonction de suppression en prenant en compte tous les cas que l’on vient de voir.
Et une nouvelle fois, il n’y a que ces cas là à considérer, faîtes quelques dessins par vous-même pour vous en convaincre au besoin. Mais du coup on est quand même tout près de la fin, alors haut les coeurs ! On passe maintenant à la fonction principale de suppression, qui est remarquablement courte. En fait, je n’ai jamais vu plus court, donc il se pourrait que j’ai trouvé une manière d’implémenter la suppression inconnue à ce jour − comme quoi, tous les problèmes ne sont pas résolus en info.
Voilà la bête :
# Noircit le noeud au besoin
def blacken(node)
node.color = RBNode.black if node
return node
end
# Trouve le noeud minimum dans un sous-arbre
def min_node(node)
return node if not node.childs[0]
return min_node(node.childs[0])
end
def delete_h(node, key)
return nil if not node
cmp = key <=> node.key
# On a trouvé le noeud à supprimer
if cmp == 0
# Si c'est une feuille qui n'a pas de fils droit, noircit et retourne le fils gauche
return blacken(node.childs[0]) if not node.childs[1]
# Remplace le noeud courant par son successeur
x = min_node(node.childs[1])
node.key = x.key
key = node.key
end
dir = (cmp >= 0).to_i
if not red?(node.childs[dir])
# Cas 2
if red?(node.childs[dir^1])
node = rotate_once(node, dir) if not red?(node)
elsif node.childs[dir] and not red?(node.childs[dir].childs[0]) and not red?(node.childs[dir].childs[1])
# Cas 3 et 3 bis
if node.childs[dir^1] and (red?(node.childs[dir^1].childs[dir^1]) or red?(node.childs[dir^1].childs[dir]))
node = rotate_del(node, dir)
# Cas 1
else
flip_colors(node)
end
end
end
node.childs[dir] = delete_h(node.childs[dir], key)
return node
endEt voilà, j’ai introduit les fonctions blacken et min_node afin de raccourcir un peu le code, mais cela correspond exactement à ce dont on parlait au début. A savoir, si on supprime une feuille noire accompagnée d’une feuille rouge, alors la feuille rouge devient noire. Et si le noeud à supprimer n’est pas une feuille, alors on le remplace avec son successeur et on détruit la feuille désormais inutile. Concernant la descente du noeud rouge, cela correspond aux exemples. Si il y a beaucoup d’appels à red?, c’est parce qu’il y a pas mal de noeuds dont il faut vérifier la couleur pour être sûr d’appliquer la bonne transformation. C’est l’inconvénient de ne pas avoir de ne références pour des noeuds intermédiaires : il faut multiplier les indirections pour vérifier les couleurs.
Comme vous êtes attentifs, vous aurez remarqué qu’il manque la fonction delete et que je n’ai toujours pas parlé de ce fameux noeud rouge qui descend de nul part. Alors c’est très simple, le tout premier noeud rouge vient de la racine. On colore la racine en rouge avant d’effectuer la récursion, et on la re-colore en noir à la fin pour ne pas briser la première règle. Cependant il y a une petite subtilité que je vous laisse découvrir dans le code.
def delete(key)
return if not @root
@root.color = RBNode.red if not red?(@root.childs[0]) and not red?(@root.childs[1])
@root = delete_h(@root, key)
@root.color = RBNode.black if @root
endOui, il y a une condition toute moche pour colorer la racine. En fait, sans ça il y a certains cas particuliers qui aboutissent à des erreurs. Mais comme je suis sympa je vous donne un exemple, vous allez vite comprendre pourquoi cela pose problème :-).
Imaginez que delete(7) soit appelé sur l'arbre suivant et
qu'il n'y a pas de condition pour colorer la racine
7,B
/ \
1,R 8,B
/ \
0,R 5,B
/ \
3,R 6,R
Et voilà, vous maîtrisez maintenant la suppression comme personne ! Un rapide point sur la comparaison de ma méthode par rapport à la suppression classique. Dans l’algorithme classique, il y a au plus trois rotations par suppression, alors que le mien n’est pas limité de ce côté là. Cependant, je préfère quand même ma méthode, qui est immensément plus élégante - sérieusement, si vous ne me croyez pas allez voir ici, il y en a pour 150-200 lignes. Cela dit, si vous trouvez une meilleure manière pour supprimer n’hésitez pas à me contacter, ça m’intéresse !
L’optimisation des méthodes delete et delete_h est laissée en exercice. Bon courage :P.
Conclusion
Bon, ce n’était pas de tout repos, mais on a réussi. En tout cas si vous êtes arrivé jusque là bravo à vous, parce que pour avoir galéré avec les arbres rouge noir je sais que ce n’est pas évident :-). Et puis je vous avais prévenu que vos neurones en prendraient un coup. Si il en reste parmi vous qui pensaient que j’allais parler d’horticulture, je ne sais pas du tout comment vous avez fait pour tenir, mais merci à vous :-).
Ceci dit, je crois m’être pas trop mal débrouillé pour démystifier les arbres bicolores et avoir enlevé une bonne partie de ce qui les rend si complexes. En pratique, les arbres rouge noir restent une solution privilégiée pour implémenter des tables. Ils ont la particularité d’être ordonnés − ce sont des arbres après tout −, ce qui est un avantage par rapport à des Hash qui eux ne le sont pas. Leur plus gros compétiteur est l’arbre AVL, en particulier parce qu’il est mieux équilibré que l’arbre rouge et noir, mais les deux solutions se valent à peu près. Un autre avantage est que tous les algorithmes que vous avez pû apprendre pour les arbre de recherche binaire sont aussi vrais pour l’arbre rouge et noir, je pense notamment à la recherche d’élément ou au parcours infixe, suffixe et préfixe des noeuds de l’arbre.
Enfin, si le sujet vous intéresse vous pouvez maintenant visiter la page anglaise de wikipédia ou regarder une version différente des arbres rouge et noir : j’ai nommé les arbres rouge noir qui penchent à gauche − Très sérieusement, le nom anglais c’est left-leaning red-black BST − qui ont été créés justement pour réduire la longueur de la méthode delete. Oui, je rigole un peu là :-).
