This is the 16th day of my participation in Gwen Challenge. For more information, see: Gwen Challenge 😄
A
Features: Properties 1. Nodes are red or black.
Property 2. The root node is black.
Nature 3. All leaves are black. (Leaves are NUIL nodes)
Property 4. Two children of each red node are black. (No two consecutive red nodes on all paths from each leaf to the root)
The nature of the 5.. All paths from any node to each of its leaves contain the same number of black nodes.
Simply say: root black, leaf black, son black, black number is the same, or black should be so red
Insert:
Today, I pulled the red-black tree insertion operation, hoping to memorize several times, firm memory.
package com.jd.platform.async.algorithm.redblacktree;
/ * * *@authorI am you *@version 1.0
* @date 2021/6/16 0013 17:13
*/
public class RBTree {
TreeNode head; // The first node of the tree
// Create a red default node, but no parent is set
public TreeNode getNode(int val) {
TreeNode defaultNode = new TreeNode(val);
defaultNode.color = Color.RED; // The default is red
return defaultNode;
}
/ / print the tree
public void printTree(TreeNode node) {
if(head==null) {
System.out.println("Tree is empty, make sure init() has been executed!");
return ;
}
if(node==null) return ;
else {
// preorder traversal
System.out.print("Node value:"+node.val+"Node color:"+node.color);
if(node.parent! =null) System.out.println("Parent node of a node:"+node.parent.val);
else System.out.println("This is the root node."); printTree(node.left); printTree(node.right); }}/*************************************************minit**************************************************/
// Tree initialization
public void init(int[] arr) {
for(int i=0; i<arr.length; ++i) { insert(head,null,arr[i],-1); }}//inset starts to insert. Lr 0 means left LR 1 means right LR -1 means root node
public void insert(TreeNode head,TreeNode parent,int i,int lr) {
if(head==null) {
TreeNode x = getNode(i);
x.parent=parent;
head = x;
if(lr==1) parent.right = head;
else if(lr==0) parent.left = head;
insert1(head);
}
else { // Recursive insertion
if(i>head.val) insert(head.right,head,i,1);
if(i<head.val) insert(head.left,head,i,0); }}//case1: The node to be inserted is the root node, and the node to be inserted is set to red. The parent node of x in the early stage, x.parent, must be determined
public void insert1(TreeNode x) {
if(x.parent==null) {
x.color = Color.BLACK;
head = x; // Point the first node to x
return ;
} else insert2(x);
}
//case2: The inserted node is not the root node
// If the parent of the inserted node is black, then the red-black tree is unadjusted
public void insert2(TreeNode x) {
if(x.parent.color==Color.BLACK) return ;
else insert3(x);
}
//case3 If the parent of the inserted node is red, both parent and child nodes are red
// If the uncle node is red, just set both the uncle node and the parent node to black and the grandfather node to red
// However, this introduces a new problem. The grandfather node and its own parent node may both be red, using tail recursion to filter up
public void insert3(TreeNode x) {
TreeNode par = x.parent; / / the parent node
TreeNode gra = par.parent; // Grandfather node
TreeNode unc = (par==gra.left)? gra.right : gra.left; // Uncle node
if(unc! =null && unc.color==Color.RED) {
unc.color = Color.BLACK;
par.color = Color.BLACK;
gra.color = Color.RED;
insert1(gra); // tailrecursively filter up
} else insert4(x);
}
//case4: if uncle node is black or null
public void insert4(TreeNode x) {
TreeNode par = x.parent; / / the parent node
TreeNode gra = par.parent; // If the parent node is the left node of the grandfather node, but x is the right node of the parent node, swap x and its parent, and x becomes the parent of its original parent node
if(par==gra.left && x==par.right) {
gra.left = x;
x.left = par;
x.parent = gra;
par.right = null;
par.parent = x;
insert5(par);
}
// If the parent is the right node of the grandfather, but x is the left node of the parent, swap x and its parent, and x becomes the right node of the grandfather
else if(par==gra.right && x==par.left) {
gra.right = x;
x.right = par;
x.parent = gra;
par.left = null;
par.parent = x;
insert5(par);
}
else {
insert5(x); Insert5 is used to determine if the x node is the parent node}}public void insert5(TreeNode x) {
TreeNode par = x.parent; / / the parent node
TreeNode gra = par.parent; // Grandfather node
TreeNode ggra = gra.parent; // The parent of the grandparent node
if(x==par.left) {
gra.left = par.right;
par.right = gra;
par.parent = ggra;
gra.parent = par;
if(gra.left! =null) gra.left.parent = gra; // Update parent information if the node is not empty
//ggra.left = par;
if(ggra==null) head = par;
else {
if(par.val>ggra.val) ggra.right = par;
elseggra.left = par; }}else if(x==par.right) {
//if(x.val==12) system.out.println (" +par.left. Val); //if(x.val==12) system.out.println (" +par.left.
gra.right = par.left;
par.left = gra;
par.parent = ggra;
gra.parent = par;
if(gra.right! =null) gra.right.parent = gra; // Update the parent node information
if(ggra==null) head = par; // The root node should be redirected
else {
if(par.val>ggra.val) ggra.right = par;
elseggra.left = par; }}// Color change
gra.color = Color.RED;
par.color = Color.BLACK;
}
/*************************************************main**************************************************/
public static void main(String[] args) {
int[] arr = {5.3.1.7.9.6.15.12.14.13};
RBTree rbt = new RBTree();
rbt.init(arr);
rbt.printTree(rbt.head);
}
// Red black tree node
private class TreeNode{
Color color=Color.RED;
int val;
TreeNode left;
TreeNode right;
TreeNode parent;
TreeNode(intvalue) { val = value; }}// Tree node enumeration class
private enum Color{ RED,BLACK; }}Copy the codeConclusion:
Case1: The node to be inserted is the root node, and the node to be inserted is set to red
Case2: The inserted node is not the root node
If the parent of the inserted node is black, the red-black tree does not need to be adjusted
Case3 If the parent of the inserted node is red, both parent and child nodes are red
If the uncle node is red, simply set both the uncle node and the parent node to black and the grandfather node to red
But this introduces a new problem. The grandparent and its own parent may both be red, using tail recursion to filter up
Case4: If the uncle node is black or null
If the parent is the left node of the grandparent, but x is the right node of the parent, swap x and its parent, and x becomes the parent of its original parent
If the parent is the right node of the grandparent, but x is the left node of the parent, swap x and its parent, and x becomes the right node of the grandparent
Thank you for reading this, if this article is well written and if you feel there is something to it
Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!
If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️