Un arbre rouge et noir est un arbre de recherche binaire équilibré. Chaque nœud a un bit de stockage pour représenter la couleur du nœud, qui peut être rouge ou noir.
Les arbres rouges et noirs ont les propriétés suivantes:
(1) Chaque nœud est rouge ou noir
(2) le nœud racine est noir
(3) Si un nœud est rouge, ses deux fils sont noirs
(4) Pour chaque nœud, tous les chemins de ce nœud à ses descendants contiennent le même nombre de nœuds noirs.
Grâce aux propriétés de l'arbre rouge-noir, il est garanti que toutes les implémentations basées sur l'arbre rouge peuvent garantir que le temps d'exécution de l'opération est logarithmique (sauf la recherche de plage. Le temps supplémentaire qu'il faut est proportionnel au nombre de touches retournées).
Treemap de Java est implémenté par des arbres rouges et noirs.
Si vous ne tracez pas une image, il est facile de se confondre. Ce qui suit est un diagramme pour illustrer l'opération d'insertion de l'arbre rouge et noir.
Après avoir inséré un nœud rouge dans l'arbre rouge et noir, il y aura 6 situations: n représente le nœud inséré, P représente le nœud parent, u représente le nœud oncle, G représente le nœud grand-père et x représente le nœud de fonctionnement actuel
Le code est le suivant:
classe publique redblackbst <key étend comparable <Tey>, valeur> {root de nœud privé; Final statique privé Red booléen = true; Private Static Final Boolean Black = False; Node de classe privée {clé privée; // Valeur privée clé Val; // valeur nœud privé à gauche, à droite, parent; // arbres enfants et gauche et nœud parent de couleur booléenne privée; // La couleur du lien pointée par son nœud public de nœud parent (clé de clé, valeur Val, parent de nœud, couleur booléenne) {this.key = key; this.val = val; this.color = couleur; }} public Value get (clé clé) {node x = root; while (x! = null) {int cmp = key.compareto (x.key); if (cmp <0) x = x.left; else if (cmp> 0) x = x.right; else return x.val; } return null; } public void put (clé de clé, valeur val) {if (root == null) {// s'il s'agit d'un nœud racine, créez le nœud en tant que root noir = nouveau nœud (key, val, null, noir); retour; } // trouver un nœud de position d'insertion approprié parent = null; Nœud cur = root; while (cur! = null) {parent = cur; if (key.compareto (cur.key)> 0) cur = cur.right; else cur = cur.left; } Nœud n = nouveau nœud (key, val, parent, rouge); // ORD NOAL NODE NODE est rouge // Insérez le nouveau nœud sous Parent if (key.compareto (parent.key)> 0) Parent.Right = n; else parent.left = n; // Après avoir inséré un nouveau nœud, vous devez ajuster les couleurs et les propriétés de certains nœuds dans l'arbre pour vous assurer que les caractéristiques de l'arbre rouge et noir ne sont pas détruites. FIXAFTERInSertion (n); } nœud privé parentof (nœud x) {return (x == null? null: x.parent); } private booléen coloref (nœud x) {return (x == null? null: x.right); } nœud privé à gauche (nœud x) {return (x == null? null: x.right); } nœud privé Rightof (nœud x) {return (x == null? null: x.right); } private void setColor (nœud x, couleur booléenne) {if (x! = null) x.color = couleur; } private void fixafterInsertion (nœud x) {while (x! = null && colorof (parentof (x)) == red) {node grandpa = parentof (parentof (x)); Node parent = parentOf (x); if (parent == gauche (grand-père)) {// cas 1 || CASE2 || Case3 Node Oncle = droite (grand-père); if (colorof (oncle) == rouge) {// case1, l'oncle est rouge setColor (parent, noir); // Le nœud parent est Black SetColor (oncle, noir); // Le nœud oncle est Black SetColor (grand-père, rouge); // Le nœud grand-père est rouge x = grand-père; // Parce que le nœud grand-père est rouge du noir au rouge, les attributs rouges et noirs du nœud parent et de ses ancêtres doivent être réajustés} else {// case2 || Case3, l'oncle est noir if (x == droite (parent)) {// case2 x = parent; rotateleft (x); } // Case3 setColor (parent, noir); SetColor (grand-père, rouge); Rotateright (grand-père); }} else {// Case4 || Cas 5 || Case6 Node Oncle = Leftof (grand-père); if (colorof (oncle) == rouge) {// case4 || Case5 || Case6 setColor (parent, noir); SetColor (oncle, noir); SetColor (grand-père, rouge); x = grand-père; } else {// Case5 || Case6, l'oncle est noir if (x == gauche (parent)) {// case5 x = parent; Rotateright (x); } // Case6 setColor (parent, noir); SetColor (grand-père, rouge); Rotateleft (grand-père); }}}} private void rotateleft (nœud x) {if (x == null) return; Nœud y = x.Right; x.Right = y.left; if (y.left! = null) y.left.parent = x; y.left = x; y.parent = x.parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; } private void rotateright (nœud x) {if (x == null) return; Nœud y = x.left; x.left = y.Right; if (y.Right! = null) y.right.parent = x; y.Right = x; y.parent = x.parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; }}Il est nécessaire de dessiner un diagramme pour le rotateleft et le rotateright au-dessus:
L'article ci-dessus est basé sur le principe de l'opération d'insertion d'arbre rouge et noire et de la méthode d'implémentation Java (partage) qui est tout le contenu que je partage avec vous. J'espère que vous pourrez vous faire référence et j'espère que vous pourrez soutenir Wulin.com plus.