Mise en œuvre de l'arbre Rouge et noir en Java

Pas de panique. 2021-09-15 07:42:57
mise en uvre arbre rouge


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 noeud nodeSous - noeud denull Comme un noeud normal .

Ici, Nous utilisons la variable sentinelle RedBlackTree.NULL Au lieu de tout dans l'arbre null( Tous les noeuds foliaires et les noeuds parents des noeuds racine ).

On va passer d'un noeud n(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 dansAvecjava Implémenter un arbre de recherche binaire Voir.

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

Avec une classe d'énumération Color Indique 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égorieRedTreeNode Repré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 noeud nEnfant droit deright Devient son noeud parent ,nDevientrightEnfant gauche de,Alors...rightNon.null.À ce moment - là,n Le pointeur droit est vide ,right Le Sous - arbre gauche de n On se casse. ,Alors...right Le Sous - arbre gauche original s'appelle nSous - arbre droit de.

Rotation à droite: Mettre un noeud nEnfant gauche deleft Devient son noeud parent ,nDevientleftEnfant droit de,Alors...leftNon.null.À ce moment - là,n Le pointeur gauche est vide. ,left Le Sous - arbre droit de n On se casse. ,Alors...left Le Sous - arbre droit original s'appelle nSous - 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) {
// Quandnode Pas le noeud racine ,Etnode La couleur du noeud parent est rouge
while (node.parent.color == Color.Red) {
// Juge d'abordnode Le 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 est nodeEnfant 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;
}
// Avecnode Remplacement direct subséquent de node,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. Quandnode Quand c'est rouge , Juste noir .
  2. Quandnode Quand 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) {
// Sinode Est l'enfant gauche de son parent
if (node == node.parent.left) {
// Enregistrementnode Le 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 {
// Enregistrementnode Le 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) {
// Quandnode Pas le noeud racine ,Etnode La couleur du noeud parent est rouge
while (node.parent.color == Color.Red) {
// Juge d'abordnode Le 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 Est l'enfant droit de son parent , Et le noeud de l'oncle est noir
// C'est exact.node Rotation à gauche du noeud parent de
node = node.parent;
this.leftRotate(node);
} else { // node Si le noeud de l'oncle est noir ,node Est 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) { // Sin1 Est l'enfant gauche de son parent
n1.parent.left = n2;
} else { // Sin1 Est 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 est nodeEnfant 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;
}
// Avecnode Remplacement direct subséquent de node,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) {
// Sinode Est l'enfant gauche de son parent
if (node == node.parent.left) {
// Enregistrementnode Le noeud frère de
Node pointer1 = node.parent.right;
// Sinode Le 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 {
// Enregistrementnode Le 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

版权声明
本文为[Pas de panique.]所创,转载请带上原文链接,感谢
https://javamana.com/2021/09/20210915073956232k.html

  1. 国内一线互联网公司面试题汇总,2021年大厂Java岗面试必问,
  2. 啃完吃透保你涨薪5K,熬夜整理小米Java面试题,
  3. 和字节跳动大佬的技术面谈,Redis成神之路电子版教程已问世,
  4. Le terme professionnel le plus complet de l'histoire des micro - services interview 50 questions, Byte Jumping Java post Classic interview vrai problème,
  5. After using mybatisplus, I haven't written SQL for a long time
  6. [springboot2 starts from 0] how to write a springboot application?
  7. Huawei cloud guassdb (for redis) released a new version, and the two core features were officially unveiled
  8. 和字節跳動大佬的技術面談,Redis成神之路電子版教程已問世,
  9. 啃完吃透保你漲薪5K,熬夜整理小米Java面試題,
  10. Avec l'interview technique du gigolo, le tutoriel électronique redis est sorti.
  11. Après avoir mangé, assurez - vous d'augmenter votre salaire de 5K et de rester debout tard pour trier les questions d'entrevue Java de millet.
  12. Résumé des questions d'entrevue pour les entreprises Internet nationales de première ligne, qui doivent être posées lors de l'entrevue d'emploi Java de la grande usine en 2021,
  13. Le tri des crachats de sang, la force de l'équipe Tencent pour créer le tutoriel d'introduction au printemps,
  14. Java and scala concurrency Fundamentals
  15. Analysis of java thread source code based on Hotspot
  16. 國內一線互聯網公司面試題匯總,2021年大廠Java崗面試必問,
  17. Introduction au module de contrôle de Connexion MySQL
  18. 大厂高级测试面试题,Java面试基础技能罗列,
  19. Comprendre l'architecture sous - jacente d'InnoDB en exécutant une instruction
  20. Chargeur de classe 1 Tomcat
  21. 小白也能看懂的dubbo3应用级服务发现详解
  22. SpringBoot异步使用@Async原理及线程池配置
  23. Questions d'entrevue de test avancé de Dachang, liste des compétences de base de l'entrevue Java,
  24. SpringBoot异步使用@Async原理及線程池配置
  25. Springboot utilise asynchrone le principe @ async et la configuration du pool de threads
  26. Détails de la découverte du Service d'application Dubbo 3 que Xiaobai peut également comprendre
  27. Springboot utilise asynchrone le principe @ async et la configuration du pool de threads
  28. 如何强大且优雅的搞定Linux文件系统,算法题 JVM,
  29. 太牛了,阿里P7架构师带你看透maven的来龙去脉,
  30. Oracle central et Oracle décentralisé
  31. java JavaBean
  32. Java wrapper type
  33. Java super keyword
  34. Java static keyword
  35. Java this keyword
  36. Java interface
  37. 太牛了,阿裏P7架構師帶你看透maven的來龍去脈,
  38. C'est génial, l'architecte Ali p7 vous montre à travers Maven.
  39. Comment traiter le système de fichiers Linux avec puissance et élégance, algorithme JVM,
  40. Java + SSM Social Insurance Pension System for Computer Graduation Design
  41. Usage of Java scanner
  42. Java inheritance
  43. Java method review
  44. java JVM
  45. Java Basics
  46. Java file operation object IO stream
  47. Java console reads multi character input and output
  48. Java simple array sorting
  49. In addition to MySQL master-slave, you have another choice, Galera
  50. Configuration standard dockerfile et docker-composer.yml
  51. 字节大神强推千页PDF学习笔记,2021Java开发学习路线,
  52. 字节大牛耗时八个月又一力作,靠这份Java知识点PDF成功跳槽,
  53. 字节大牛教你手撕Java学习,最新大厂程序员进阶宝典,
  54. Comment l'automne est - il beau?Ces 24 ensembles de modèles d'automne et d'hiver sont grands, minces et vieillissants
  55. 字節大牛教你手撕Java學習,最新大廠程序員進階寶典,
  56. 字節大牛耗時八個月又一力作,靠這份Java知識點PDF成功跳槽,
  57. Byte Bull vous apprend à déchiqueter Java à la main, le dernier dictionnaire avancé des programmeurs de grandes usines,
  58. Byte Bull a pris huit mois à travailler dur et a réussi à changer d'emploi avec ce PDF Java Knowledge point.
  59. Byte God Push 1000 pages PDF Learning notes, 2021 Java Development Learning route,
  60. Five minutes to understand MySQL index push down