Les arbres rouges et noirs sont nombreux“Équilibre”Un des modes de recherche de l'arbre,Dans le pire des cas,La complexité temporelle de ses opérations estO(log n).

1、Propriétés de l'arbre Rouge et noir

L'arbre Rouge et noir est un arbre de recherche binaire,Une différence par rapport à l'arbre de recherche binaire normal est,Chaque noeud de l'arbre Rouge et noir a une couleur(color)Propriétés.La valeur de la propriété est rouge,Ou noir.

En limitant la couleur des noeuds sur n'importe quel chemin simple de la racine à la feuille,L'arbre Rouge et noir assure qu'il n'y a pas de chemin deux fois plus long que tout autre chemin,Pour que l'arbre soit approximativement équilibré.

Supposons que l'attribut du noeud Red Black Tree ait une clé(key)、Couleur(color)、Sous - noeud gauche(left)、Noeud enfant droit(right),Noeud parent(parent).

Un arbre Rouge et noir doit satisfaire aux caractéristiques suivantes(Propriétés de l'arbre Rouge et noir):

  1. Chaque noeud de l'arbre est rouge,Ou noir;
  2. Le noeud racine est noir;
  3. Chaque noeud de feuille(null)C'est noir;
  4. Si un noeud est rouge,Ses deux noeuds enfants sont noirs;
  5. Pour chaque noeud à l'un des noeuds foliaires suivants(null)Tous les chemins de,Tous ont le même nombre de noeuds noirs.

Pour faciliter le traitement des conditions limites dans le Code Red Black Tree,Nous avons remplacénull.Pour un arbre Rouge et noirtree,Variable sentinelleRedBlackTree.NULL(Dans les codes suivants)Est un noeud avec les mêmes attributs que les autres noeuds,Sa couleur(color)La propriété est noire,D'autres propriétés peuvent être arbitrairement évaluées.

Nous utilisons la variable sentinelle parce que nous pouvons mettre un noeudnodeSous - noeud denullComme un noeud normal.

Ici,Nous utilisons la variable sentinelleRedBlackTree.NULLAu lieu de tout dans l'arbrenull(Tous les noeuds foliaires et les noeuds parents des noeuds racine).

On va passer d'un noeudn(Non compris)Le nombre de noeuds noirs sur n'importe quel chemin de noeud de feuille est appeléHauteur Noire,Avecbh(n)Représentation.La hauteur noire d'un arbre Rouge et noir est la hauteur noire de ses noeuds racinaires.

À propos de la recherche de Red Black Trees,Trouver le minimum,Max,Recherche de précurseurs,Le Code pour trouver ces opérations subséquentes est essentiellement le même que le Code pour ces opérations dans l'arbre de recherche binaire.Ça pourrait être dansAvecjavaImplémenter un arbre de recherche binaireVoir.

Les codes suivants sont donnés en combinaison avec les codes ci - dessus.

Avec une classe d'énumérationColorIndique la couleur:

public enum Color {
Black("Noir"), Red("Rouge"); private String color; private Color(String color) {
this.color = color;
} @Override
public String toString() {
return color;
}
}

CatégorieNodeReprésente le noeud:

public class Node {
public int key;
public Color color;
public Node left;
public Node right;
public Node parent; public Node() {
} public Node(Color color) {
this.color = color;
} public Node(int key) {
this.key = key;
this.color = Color.Red;
} public int height() {
return Math.max(left != RedBlackTree.NULL ? left.height() : 0, right != RedBlackTree.NULL ? right.height() : 0) + 1;
} public Node minimum() {
Node pointer = this;
while (pointer.left != RedBlackTree.NULL)
pointer = pointer.left;
return pointer;
} @Override
public String toString() {
String position = "null";
if (this.parent != RedBlackTree.NULL)
position = this.parent.left == this ? "left" : "right";
return "[key: " + key + ", color: " + color + ", parent: " + parent.key + ", position: " + position + "]";
}
}

CatégorieRedTreeNodeReprésente un arbre Rouge et noir:

public class RedBlackTree {

    // Représente la variable sentinelle
public final static Node NULL = new Node(Color.Black); public Node root; public RedBlackTree() {
this.root = NULL;
} }

2、Rotation

Insertion et suppression d'arbres rouges et noirs,Peut changer la structure des arbres rouges et noirs,Peut - être qu'il n'a plus certaines des caractéristiques décrites précédemment.Pour maintenir ces caractéristiques,Nous devons changer la couleur et la position de certains noeuds dans l'arbre.

Nous pouvons changer la structure des noeuds en tournant.Principalement:Rotation à gaucheEtRotation à droiteDeux façons.Voir la figure ci - dessous pour plus de détails..

Rotation à gauche:Mettre un noeudnEnfant droit derightDevient son noeud parent,nDevientrightEnfant gauche de,Alors...rightNon.null.À ce moment - là,nLe pointeur droit est vide,rightLe Sous - arbre gauche denOn se casse.,Alors...rightLe Sous - arbre gauche original s'appellenSous - arbre droit de.

Rotation à droite:Mettre un noeudnEnfant gauche deleftDevient son noeud parent,nDevientleftEnfant droit de,Alors...leftNon.null.À ce moment - là,nLe pointeur gauche est vide.,leftLe Sous - arbre droit denOn se casse.,Alors...leftLe Sous - arbre droit original s'appellenSous - arbre gauche de.

Oui.RedTreeNodeDans la classe,Ajouter le Code d'implémentation suivant:

    public void leftRotate(Node node) {
Node rightNode = node.right; node.right = rightNode.left;
if (rightNode.left != RedBlackTree.NULL)
rightNode.left.parent = node; rightNode.parent = node.parent;
if (node.parent == RedBlackTree.NULL)
this.root = rightNode;
else if (node.parent.left == node)
node.parent.left = rightNode;
else
node.parent.right = rightNode; rightNode.left = node;
node.parent = rightNode;
} public void rightRotate(Node node) {
Node leftNode = node.left; node.left = leftNode.right;
if (leftNode.right != RedBlackTree.NULL)
leftNode.right.parent = node; leftNode.parent = node.parent;
if (node.parent == RedBlackTree.NULL) {
this.root = leftNode;
} else if (node.parent.left == node) {
node.parent.left = leftNode;
} else {
node.parent.right = leftNode;
} leftNode.right = node;
node.parent = leftNode;
}

3、Insérer

Le Code d'insertion de l'arbre Rouge et noir est très similaire au Code d'insertion de l'arbre de recherche binaire.C'est juste que l'insertion de l'arbre Rouge et noir change la structure de l'arbre Rouge et noir,Pour qu'il n'ait pas les propriétés qu'il devrait avoir.

Ici,Le noeud nouvellement inséré est rouge par défaut.

Donc après avoir inséré le noeud,Pour avoir un code qui maintient les caractéristiques de l'arbre Rouge et noir.

    public void insert(Node node) {
Node parentPointer = RedBlackTree.NULL;
Node pointer = this.root; while (this.root != RedBlackTree.NULL) {
parentPointer = pointer;
pointer = node.key < pointer.key ? pointer.left : pointer.right;
} node.parent = parentPointer;
if(parentPointer == RedBlackTree.NULL) {
this.root = node;
}else if(node.key < parentPointer.key) {
parentPointer.left = node;
}else {
parentPointer.right = node;
} node.left = RedBlackTree.NULL;
node.right = RedBlackTree.NULL;
node.color = Color.Red;
// Comment conserver les propriétés de l'arbre Rouge et noir
this.insertFixUp(node);
}

Lors de l'insertion d'un nouveau noeud comme décrit ci - dessus,Il existe deux types de situations qui violent les caractéristiques des arbres rouges et noirs.

  1. Quand il n'y a pas de noeuds dans l'arbre,Le noeud inséré s'appelle le noeud racine,Et la couleur de ce noeud est rouge.
  2. Lorsque le noeud nouvellement inséré devient un enfant d'un noeud rouge,Il y a un noeud rouge avec un noeud rouge Enfant.

Pour les cas de catégorie I,Le noeud racine peut être réglé directement en noir;Et pour la deuxième catégorie,Selon les conditions spécifiques,Faire les solutions appropriées.

Les codes spécifiques sont les suivants::

    public void insertFixUp(Node node) {
// QuandnodePas le noeud racine,EtnodeLa couleur du noeud parent est rouge
while (node.parent.color == Color.Red) {
// Juge d'abordnodeLe noeud parent de est le noeud enfant gauche,Ou le noeud enfant droit,C'est différent.,La solution sera différente
if (node.parent == node.parent.parent.left) {
Node uncleNode = node.parent.parent.right;
if (uncleNode.color == Color.Red) { // Si le noeud de l'oncle est rouge,Alors le père doit être noir
// En changeant le noeud parent en rouge,Le noeud parent et le noeud frère deviennent noirs,Ensuite, pour déterminer si la couleur du noeud parent est appropriée
uncleNode.color = Color.Black;
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
node = node.parent.parent;
} else if (node == node.parent.right) {
node = node.parent;
this.leftRotate(node);
} else {
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
this.rightRotate(node.parent.parent);
}
} else {
Node uncleNode = node.parent.parent.left;
if (uncleNode.color == Color.Red) {
uncleNode.color = Color.Black;
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
node = node.parent.parent;
} else if (node == node.parent.left) {
node = node.parent;
this.rightRotate(node);
} else {
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
this.leftRotate(node.parent.parent);
}
}
}
// S'il n'y avait pas de noeuds dans l'arbre avant,Le nouveau point ajouté devient alors le nouveau noeud,Et les noeuds nouvellement insérés sont tous rouges,Il faut donc le modifier..
this.root.color = Color.Black;
}

Les figures ci - dessous correspondent respectivement aux six cas de la deuxième catégorie et aux résultats de traitement correspondants.

La situation1:

La situation2:

La situation3:

La situation4:

La situation5:

La situation6:

4、Supprimer

La suppression d'un noeud dans un arbre Rouge et noir fait qu'un noeud remplace un autre.Donc d'abord mettre en œuvre ce code:

    public void transplant(Node n1, Node n2) {
if(n1.parent == RedBlackTree.NULL){
this.root = n2;
}else if(n1.parent.left == n1) {
n1.parent.left = n2;
}else {
n1.parent.right = n2;
}
n2.parent = n1.parent;
}

Le Code de noeud de suppression de l'arbre Rouge et noir est basé sur le Code de noeud de suppression de l'arbre de recherche binaire.

Supprimer le Code du noeud:

    public void delete(Node node) {
Node pointer1 = node;
// Utilisé pour enregistrer les couleurs supprimées,Si c'est rouge,Ça ne me dérange pas,Mais si c'est noir,Peut détruire les propriétés de l'arbre Rouge et noir
Color pointerOriginColor = pointer1.color;
// Utilisé pour enregistrer le point où le problème s'est produit
Node pointer2;
if (node.left == RedBlackTree.NULL) {
pointer2 = node.right;
this.transplant(node, node.right);
} else if (node.right == RedBlackTree.NULL) {
pointer2 = node.left;
this.transplant(node, node.left);
} else {
// Si l'octet à supprimer a deux noeuds enfants,Trouver son successeur direct(Sous - arbre droit minimum),Le noeud successeur direct n'a pas de sous - noeud gauche non vide.
pointer1 = node.right.minimum();
// Enregistrez les couleurs qui suivent directement et leurs enfants de droite
pointerOriginColor = pointer1.color;
pointer2 = pointer1.right;
// Si son successeur immédiat estnodeEnfant droit de,Pas besoin de traitement
if (pointer1.parent == node) {
pointer2.parent = pointer1;
} else {
// Sinon,Extraire d'abord le suivi direct de l'arbre,Pour remplacernode
this.transplant(pointer1, pointer1.right);
pointer1.right = node.right;
pointer1.right.parent = pointer1;
}
// AvecnodeRemplacement direct subséquent denode,SuccessionnodeCouleur
this.transplant(node, pointer1);
pointer1.left = node.left;
pointer1.left.parent = pointer1;
pointer1.color = node.color;
}
if (pointerOriginColor == Color.Black) {
this.deleteFixUp(pointer2);
}
}

.La méthode d'appel est nécessaire pour maintenir les propriétés de l'arbre Rouge et noir lorsque la couleur du noeud supprimé est noire.

Il existe deux grandes catégories de situations:

  1. QuandnodeQuand c'est rouge,Juste noir.
  2. QuandnodeQuand c'est noir,Besoin d'ajuster la structure de l'arbre Rouge et noir.,
    private void deleteFixUp(Node node) {
// SinodePas le noeud racine,Et noir
while (node != this.root && node.color == Color.Black) {
// SinodeEst l'enfant gauche de son parent
if (node == node.parent.left) {
// EnregistrementnodeLe noeud frère de
Node pointer1 = node.parent.right;
// Si le noeud de son frère est rouge
if (pointer1.color == Color.Red) {
pointer1.color = Color.Black;
node.parent.color = Color.Red;
leftRotate(node.parent);
pointer1 = node.parent.right;
}
if (pointer1.left.color == Color.Black && pointer1.right.color == Color.Black) {
pointer1.color = Color.Red;
node = node.parent;
} else if (pointer1.right.color == Color.Black) {
pointer1.left.color = Color.Black;
pointer1.color = Color.Red;
rightRotate(pointer1);
pointer1 = node.parent.right;
} else {
pointer1.color = node.parent.color;
node.parent.color = Color.Black;
pointer1.right.color = Color.Black;
leftRotate(node.parent);
node = this.root;
}
} else {
// EnregistrementnodeLe noeud frère de
Node pointer1 = node.parent.left;
// Si le noeud de son frère est rouge
if (pointer1.color == Color.Red) {
pointer1.color = Color.Black;
node.parent.color = Color.Red;
rightRotate(node.parent);
pointer1 = node.parent.left;
}
if (pointer1.right.color == Color.Black && pointer1.left.color == Color.Black) {
pointer1.color = Color.Red;
node = node.parent;
} else if (pointer1.left.color == Color.Black) {
pointer1.right.color = Color.Black;
pointer1.color = Color.Red;
leftRotate(pointer1);
pointer1 = node.parent.left;
} else {
pointer1.color = node.parent.color;
node.parent.color = Color.Black;
pointer1.left.color = Color.Black;
rightRotate(node.parent);
node = this.root;
}
} }
node.color = Color.Black;
}

Dans le cas de la catégorie II,Là - Bas.8Espèce:

La situation1:

La situation2:

La situation3:

La situation4:

La situation5:

La situation6:

La situation7:

La situation8:

5、Tous les codes

public enum Color {
Black("Noir"), Red("Rouge"); private String color; private Color(String color) {
this.color = color;
} @Override
public String toString() {
return color;
}
}
public class Node {
public int key;
public Color color;
public Node left;
public Node right;
public Node parent; public Node() {
} public Node(Color color) {
this.color = color;
} public Node(int key) {
this.key = key;
this.color = Color.Red;
} /**
* Trouvez la hauteur du noeud dans l'arbre
*
* @return
*/
public int height() {
return Math.max(left != RedBlackTree.NULL ? left.height() : 0, right != RedBlackTree.NULL ? right.height() : 0) + 1;
} /**
* Dans l'arbre avec ce noeud comme noeud racine,Trouver le plus petit noeud
*
* @return
*/
public Node minimum() {
Node pointer = this;
while (pointer.left != RedBlackTree.NULL)
pointer = pointer.left;
return pointer;
} @Override
public String toString() {
String position = "null";
if (this.parent != RedBlackTree.NULL)
position = this.parent.left == this ? "left" : "right";
return "[key: " + key + ", color: " + color + ", parent: " + parent.key + ", position: " + position + "]";
}
}
import java.util.LinkedList;
import java.util.Queue; public class RedBlackTree { public final static Node NULL = new Node(Color.Black); public Node root; public RedBlackTree() {
this.root = NULL;
} /**
* Rotation à gauche
*
* @param node
*/
public void leftRotate(Node node) {
Node rightNode = node.right; node.right = rightNode.left;
if (rightNode.left != RedBlackTree.NULL)
rightNode.left.parent = node; rightNode.parent = node.parent;
if (node.parent == RedBlackTree.NULL)
this.root = rightNode;
else if (node.parent.left == node)
node.parent.left = rightNode;
else
node.parent.right = rightNode; rightNode.left = node;
node.parent = rightNode;
} /**
* Rotation à droite
*
* @param node
*/
public void rightRotate(Node node) {
Node leftNode = node.left; node.left = leftNode.right;
if (leftNode.right != RedBlackTree.NULL)
leftNode.right.parent = node; leftNode.parent = node.parent;
if (node.parent == RedBlackTree.NULL) {
this.root = leftNode;
} else if (node.parent.left == node) {
node.parent.left = leftNode;
} else {
node.parent.right = leftNode;
} leftNode.right = node;
node.parent = leftNode;
} public void insert(Node node) {
Node parentPointer = RedBlackTree.NULL;
Node pointer = this.root; while (pointer != RedBlackTree.NULL) {
parentPointer = pointer;
pointer = node.key < pointer.key ? pointer.left : pointer.right;
} node.parent = parentPointer;
if (parentPointer == RedBlackTree.NULL) {
this.root = node;
} else if (node.key < parentPointer.key) {
parentPointer.left = node;
} else {
parentPointer.right = node;
} node.left = RedBlackTree.NULL;
node.right = RedBlackTree.NULL;
node.color = Color.Red;
this.insertFixUp(node);
} private void insertFixUp(Node node) {
// QuandnodePas le noeud racine,EtnodeLa couleur du noeud parent est rouge
while (node.parent.color == Color.Red) {
// Juge d'abordnodeLe noeud parent de est le noeud enfant gauche,Ou le noeud enfant droit,C'est différent.,La solution sera différente
if (node.parent == node.parent.parent.left) {
Node uncleNode = node.parent.parent.right;
if (uncleNode.color == Color.Red) { // Si le noeud de l'oncle est rouge,Alors le père doit être noir
// En changeant le noeud parent en rouge,Le noeud parent et le noeud frère deviennent noirs,Ensuite, pour déterminer si la couleur du noeud parent est appropriée
uncleNode.color = Color.Black;
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
node = node.parent.parent;
} else if (node == node.parent.right) { // nodeEst l'enfant droit de son parent,Et le noeud de l'oncle est noir
// C'est exact.nodeRotation à gauche du noeud parent de
node = node.parent;
this.leftRotate(node);
} else { // nodeSi le noeud de l'oncle est noir,nodeEst l'enfant gauche de son parent,Le noeud parent est noir
// Transformer le noeud parent en noir,Le noeud parent devient rouge,Rotation à droite du noeud parent
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
this.rightRotate(node.parent.parent);
}
} else {
Node uncleNode = node.parent.parent.left;
if (uncleNode.color == Color.Red) {
uncleNode.color = Color.Black;
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
node = node.parent.parent;
} else if (node == node.parent.left) {
node = node.parent;
this.rightRotate(node);
} else {
node.parent.color = Color.Black;
node.parent.parent.color = Color.Red;
this.leftRotate(node.parent.parent);
}
}
}
// S'il n'y avait pas de noeuds dans l'arbre avant,Le nouveau point ajouté devient alors le nouveau noeud,Et les noeuds nouvellement insérés sont tous rouges,Il faut donc le modifier..
this.root.color = Color.Black;
} /**
* n2Substitutionn1
*
* @param n1
* @param n2
*/
private void transplant(Node n1, Node n2) { if (n1.parent == RedBlackTree.NULL) { // Sin1Est le noeud racine
this.root = n2;
} else if (n1.parent.left == n1) { // Sin1Est l'enfant gauche de son parent
n1.parent.left = n2;
} else { // Sin1Est l'enfant droit de son parent
n1.parent.right = n2;
}
n2.parent = n1.parent;
} /**
* Supprimer le noeudnode
*
* @param node
*/
public void delete(Node node) {
Node pointer1 = node;
// Utilisé pour enregistrer les couleurs supprimées,Si c'est rouge,Ça ne me dérange pas,Mais si c'est noir,Peut détruire les propriétés de l'arbre Rouge et noir
Color pointerOriginColor = pointer1.color;
// Utilisé pour enregistrer le point où le problème s'est produit
Node pointer2;
if (node.left == RedBlackTree.NULL) {
pointer2 = node.right;
this.transplant(node, node.right);
} else if (node.right == RedBlackTree.NULL) {
pointer2 = node.left;
this.transplant(node, node.left);
} else {
// Si l'octet à supprimer a deux noeuds enfants,Trouver son successeur direct(Sous - arbre droit minimum),Le noeud successeur direct n'a pas de sous - noeud gauche non vide.
pointer1 = node.right.minimum();
// Enregistrez les couleurs qui suivent directement et leurs enfants de droite
pointerOriginColor = pointer1.color;
pointer2 = pointer1.right;
// Si son successeur immédiat estnodeEnfant droit de,Pas besoin de traitement
if (pointer1.parent == node) {
pointer2.parent = pointer1;
} else {
// Sinon,Extraire d'abord le suivi direct de l'arbre,Pour remplacernode
this.transplant(pointer1, pointer1.right);
pointer1.right = node.right;
pointer1.right.parent = pointer1;
}
// AvecnodeRemplacement direct subséquent denode,SuccessionnodeCouleur
this.transplant(node, pointer1);
pointer1.left = node.left;
pointer1.left.parent = pointer1;
pointer1.color = node.color;
}
if (pointerOriginColor == Color.Black) {
this.deleteFixUp(pointer2);
}
} /**
* The procedure RB-DELETE-FIXUP restores properties 1, 2, and 4
*
* @param node
*/
private void deleteFixUp(Node node) {
// SinodePas le noeud racine,Et noir
while (node != this.root && node.color == Color.Black) {
// SinodeEst l'enfant gauche de son parent
if (node == node.parent.left) {
// EnregistrementnodeLe noeud frère de
Node pointer1 = node.parent.right;
// SinodeLe noeud frère est rouge
if (pointer1.color == Color.Red) {
pointer1.color = Color.Black;
node.parent.color = Color.Red;
leftRotate(node.parent);
pointer1 = node.parent.right;
}
if (pointer1.left.color == Color.Black && pointer1.right.color == Color.Black) {
pointer1.color = Color.Red;
node = node.parent;
} else if (pointer1.right.color == Color.Black) {
pointer1.left.color = Color.Black;
pointer1.color = Color.Red;
rightRotate(pointer1);
pointer1 = node.parent.right;
} else {
pointer1.color = node.parent.color;
node.parent.color = Color.Black;
pointer1.right.color = Color.Black;
leftRotate(node.parent);
node = this.root;
}
} else {
// EnregistrementnodeLe noeud frère de
Node pointer1 = node.parent.left;
// Si le noeud de son frère est rouge
if (pointer1.color == Color.Red) {
pointer1.color = Color.Black;
node.parent.color = Color.Red;
rightRotate(node.parent);
pointer1 = node.parent.left;
}
if (pointer1.right.color == Color.Black && pointer1.left.color == Color.Black) {
pointer1.color = Color.Red;
node = node.parent;
} else if (pointer1.left.color == Color.Black) {
pointer1.right.color = Color.Black;
pointer1.color = Color.Red;
leftRotate(pointer1);
pointer1 = node.parent.left;
} else {
pointer1.color = node.parent.color;
node.parent.color = Color.Black;
pointer1.left.color = Color.Black;
rightRotate(node.parent);
node = this.root;
}
} }
node.color = Color.Black;
} private void innerWalk(Node node) {
if (node != NULL) {
innerWalk(node.left);
System.out.println(node);
innerWalk(node.right);
}
} /**
* Traversée de l'ordre moyen
*/
public void innerWalk() {
this.innerWalk(this.root);
} /**
* Traversée hiérarchique
*/
public void print() {
Queue<Node> queue = new LinkedList<>();
queue.add(this.root);
while (!queue.isEmpty()) {
Node temp = queue.poll();
System.out.println(temp);
if (temp.left != NULL)
queue.add(temp.left);
if (temp.right != NULL)
queue.add(temp.right);
}
} // Trouver
public Node search(int key) {
Node pointer = this.root;
while (pointer != NULL && pointer.key != key) {
pointer = pointer.key < key ? pointer.right : pointer.left;
}
return pointer;
} }

6、Présentation

Code de présentation:

public class Test01 {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 };
RedBlackTree redBlackTree = new RedBlackTree();
for (int i = 0; i < arr.length; i++) {
redBlackTree.insert(new Node(arr[i]));
}
System.out.println("Hauteur de l'arbre: " + redBlackTree.root.height());
System.out.println("Hauteur du sous - arbre gauche: " + redBlackTree.root.left.height());
System.out.println("Hauteur du sous - arbre droit: " + redBlackTree.root.right.height());
System.out.println("Traversée hiérarchique");
redBlackTree.print();
// Pour supprimer un noeud
Node node = redBlackTree.search(4);
redBlackTree.delete(node);
System.out.println("Hauteur de l'arbre: " + redBlackTree.root.height());
System.out.println("Hauteur du sous - arbre gauche: " + redBlackTree.root.left.height());
System.out.println("Hauteur du sous - arbre droit: " + redBlackTree.root.right.height());
System.out.println("Traversée hiérarchique");
redBlackTree.print();
}
}

Résultats:

Hauteur de l'arbre: 4
Hauteur du sous - arbre gauche: 2
Hauteur du sous - arbre droit: 3
Traversée hiérarchique
[key: 4, color: Noir, parent: 0, position: null]
[key: 2, color: Rouge, parent: 4, position: left]
[key: 6, color: Rouge, parent: 4, position: right]
[key: 1, color: Noir, parent: 2, position: left]
[key: 3, color: Noir, parent: 2, position: right]
[key: 5, color: Noir, parent: 6, position: left]
[key: 7, color: Noir, parent: 6, position: right]
[key: 8, color: Rouge, parent: 7, position: right]
Hauteur de l'arbre: 3
Hauteur du sous - arbre gauche: 2
Hauteur du sous - arbre droit: 2
Traversée hiérarchique
[key: 5, color: Noir, parent: 0, position: null]
[key: 2, color: Rouge, parent: 5, position: left]
[key: 7, color: Rouge, parent: 5, position: right]
[key: 1, color: Noir, parent: 2, position: left]
[key: 3, color: Noir, parent: 2, position: right]
[key: 6, color: Noir, parent: 7, position: left]
[key: 8, color: Noir, parent: 7, position: right]

7、RÉFÉRENCES

《Introduction à l'algorithme》(No3Édition) Version anglaise

AvecJava Autre article available in English under the Titanic Titanic Titanic Titanic Titanic Titanic Titanic Titanic Titanic Titanic Titanic Titanic Titanic Titanic Titanic titanics

  1. JavaRéaliser l'arbre Rouge et noir

    De:http://www.cnblogs.com/skywang12345/p/3624343.html Introduction à l'arbre Rouge et noir Arbre Rouge et noir(Red-Black Tree,AbréviationsR-B Tree), C'est un binaire spécial ...

  2. Basé surJava Réaliser le fonctionnement de base de l'arbre Rouge et noir

    Tout d'abord,, Avant de lire l'article , J'espère que le lecteur saura quelque chose sur l'arbre binaire , Parce que l'essence de l'arbre Rouge et noir est un arbre binaire . Donc ce blog n'est pas l'opération de base pour ajouter ou supprimer des arbres binaires , Les étudiants qui ont besoin de savoir peuvent venir à un blog que j'a i écrit plus tôt sur les opérations de base de l'arbre binaire :htt ...

  3. Java Ensemble | Arbre Rouge et noir | Connaissance préalable

    Un..Préface 0tnv1e.png Pourquoi apprendre l'acridine Rouge et Noire ? Parce que l'auteur est en retard sur le projet récemment , N'oubliez pas de prendre le temps de revoir Java Connaissances de base, Maintenant, préparez - vous à regarder le code source de la collection .J'ai entendu,HashMap In jdk 1.8 Quand,Niveau inférieur ...

  4. javaStructure des données——Arbre Rouge et noir(R-B Tree)

    Les arbres rouges et noirs sont plus équilibrés que les arbres binaires (AVL) C'est un arbre faiblement équilibré , Et possède les caractéristiques suivantes : 1.Chaque noeud n'est pas rouge ou noir; 2. Le noeud racine est noir ; 3.Chaque noeud foliaire(Le noeud foliaire est la queue de l'arbreNULLPointeur ouNULLNoeud)Tout est noir; 4.Comme le montre la figure,Si un ...

  5. JavaStructure des données——Arbre Rouge et noir

    Arbre Rouge et noir Introduction arbre Rouge et noir (Red-Black Tree),Un arbre de recherche binaire spécial.Effectuer une recherche.Insérer. La complexité temporelle des opérations telles que la suppression est O(logn). L'arbre Rouge et noir est un arbre de recherche binaire spécial , Cela signifie qu'il satisfait aux caractéristiques de l'arbre de recherche binaire : N'importe quel noeud ...

  6. Arbre Rouge et noir(Cinq)De JavaRéalisation

    Résumé La connaissance théorique de l'arbre Rouge et noir a été introduite plus tôt .Rouge et noirCLangues etC++Réalisation. Ce chapitre présente les JavaRéalisation, Si le lecteur n'est pas familier avec la théorie des arbres rouges et noirs , Construire une connaissance théorique de l'arbre Rouge et noir d'abord , Revenez à ce chapitre .C'est un vieux dicton.,Rouge et noirC/C+ ...

  7. Arbre Rouge et noir JavaRéalisation

    Résumé La connaissance théorique de l'arbre Rouge et noir a été introduite plus tôt .Rouge et noirCLangues etC++Réalisation. Ce chapitre présente les JavaRéalisation, Si le lecteur n'est pas familier avec la théorie des arbres rouges et noirs , Construire une connaissance théorique de l'arbre Rouge et noir d'abord , Revenez à ce chapitre .C'est un vieux dicton.,Rouge et noirC/C+ ...

  8. De2-3-4 Arbre à arbre Rouge et noir (En bas.) JavaAvecCRéalisation

    Bienvenue à explorer,Veuillez corriger toute erreur Si nécessaire,Veuillez indiquer la source   http://www.cnblogs.com/nullzx/ Blogs connexes: De2-3-4 Arbre à arbre Rouge et noir (Allez.) De2-3-4 Arbre à arbre Rouge et noir (Moyenne) 1. Techniques de réalisation ...

  9. javaMoyennetreemapEttreesetRéalisation(Arbre Rouge et noir)

    javaMoyennetreemapEttreesetRéalisation(Arbre Rouge et noir)   TreeMap L'implémentation est la structure de données Red Black Tree , C'est un arbre binaire auto - équilibré , Cela garantit que lorsqu'un noeud spécifié doit être récupéré rapidement . TreeSet Et Tre ...

  10. Java 7 Type de collection pour - Arbre de tri binaire、Arbre d'équilibre、Arbre Rouge et noir---Tourne.

    http://blog.csdn.net/mazhimazh/article/details/19961017 Pour comprendre TreeMap Mise en œuvre sous - jacente de, Les arbres binaires de tri et d'équilibre doivent être introduits en premier , Puis continuez à présenter Rouge et noir ...

Recommandation aléatoire

  1. Educational Codeforces Round 15 Road to Post Office

    Road to Post Office Titre: Un homme doit partir de 0Allez.d, On peut y aller en voiture kM, Après ça, la voiture va se casser , Vous pouvez réparer ou non , Il faut des fleurs pour réparer tTemps, Coût par Unit é de distance aTemps, Coût par Unit é de distance de marche bTemps,Oui.d Durée minimale . Explication du problème ...

  2. IE6En bas.div Couvrir select La meilleure solution pour

    a. Sélection de cette section html5/css Sur la chaîne IE6En bas.div Couvrir select La meilleure solution pour Principes:Utilisationiframe Pour couvrir select,Réutiliserdiv Pour couvrir iframe,C'est si simple.. 1)Tout d'abord,,Construire undivCouche eti ...

  3. FermermyeclipseMoyennejspFonction de vérification

    window--->preference--->Myeclipse--->Validation, Décochez la case rouge ci - dessous .

  4. MO_GLOBAL - EBS R12 Moyenne Multi Org Une étude approfondie du design (3)

    C'est le troisième article d'une visite Multi - organisations ,Traduction depuisAnil PassiDeMO_GLOBAL-Dive into R12 Multi Org Design J'espère que vous avez lu l'article  EBS R12 Dans Multi Org ...

  5. JDKEtJREStructure du Répertoire

    JDK Structure du fichier et Répertoire : c:\jdk1.7.0: JDKInstaller le Répertoire racine, Y compris les droits d'auteur . Permis et READEMEDocumentation,Contient égalementser.zipEnregistrementJava Archives de la plateforme . c:\jdk1.7.0\bin Inclus dansJavaDéveloppement ...

  6. 20165309 Linux Installation et apprentissage

    Linux Installation et apprentissage Installer une machine virtuelle En lien avec le blog de Mlle Lou <Basé surVirtualBoxInstallation de machines virtuellesUbuntuTutoriels graphiques> Et Baidu pour quelques petits problèmes , J'ai fini l'installation en douceur . Et puis, Suivez les étapes pour installer Virtual Machine add ...

  7. Java Comment utiliser l'exception thread ?

    InJavaEn programmation, Comment utiliser l'exception thread ? Cet exemple montre comment gérer les exceptions lors du traitement d'un thread . package com.yiibai; class MyThread extends Thread { public voi ...

  8. python3 os.walk()Utiliser

    os.walk() La méthode est utilisée pour afficher le nom du fichier dans le répertoire en errant dans l'arborescence du Répertoire ,Vers le haut ou vers le bas. InUnix,WindowsMoyenne efficace. os.walk(top[, topdown=True[, onerror=Non ...

  9. Python Résumé des erreurs et des exceptions

    1.PythonClasse d'exception PythonEst un langage orienté objet, ..Donc l'exception lancée par le programme est aussi une classe .FréquentPython Les exceptions sont les suivantes , Il suffit de jeter un coup d'oeil , Il y a une image , Quand il sera temps de programmer , Je suis sûr que vous les rencontrerez plus d'une fois ( À moins que tu ne ...

  10. Wechat public Number Le journaltokenÉchec de la validation

    J'ai rencontré token Problèmes de validation échoués ,Comme le montre la figure ci - dessous Et puis une recherche folle sur Internet , J'ai rencontré beaucoup de gens , Il y a probablement ces raisons : 1)ServeurURL Pas d'authentification de nom réel 2)token Nouveau nom (C'est presque impossible.) 3) Projet déployé par le serveur ...