Binary search tree
Ordinary binary search tree, if it’s a balanced binary tree.
Then, the search time complexity of N nodes is O(log2n), approximately half search. If the binary search tree is completely unbalanced, it degenerates into a linked list
Its time complexity is O(n). Therefore, in order to solve this problem, avL tree (self-balanced binary tree) appeared. Well, it’s not important. It’s not what I’m talking about. (~ ~ ▽ ~) ~
Avl tree
Avl tree A highly balanced binary tree. It has the property that the absolute value of the height difference between the left and right subtrees is no more than 1, and both of its left and right subtrees are balanced binary trees. Avl trees pursue perfect equilibrium. When a new node is inserted, it is balanced by rotation as long as the absolute value of height difference is less than or equal to 1. In this way, performance is sacrificed during frequent insert and delete operations. Well, it’s not important, and it’s not what I’m talking about. &western (=, omega < =) rho ⌒ oblivious
Red and black tree
Next is my main point (✿◡‿◡). The red-black tree is a special avL tree. It does not pursue high balance, it only requires partial balance, adding color and rules to the nodes of the tree to achieve non-strict balance. A standard red-black tree, which satisfies the following properties: 1. The tree nodes are either black or red. 2. The root node is black. 3. The children of the red node must be black. 4. Empty leaf nodes are black. 5. All paths from a node to a leaf node contain the same number of black nodes. 6. The newly inserted node is red, that is, when a node is initialized, it is red.
Red black tree rotation
Essential knowledge ✧
left-handed:
As shown above, left-handed twist node 0078 ↓ below (literally turning node 0078 into the left node of 0089 o‿≖✧)
Discoloration left
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Right hand:
As shown in the figure above, right-turn node 0067 by ↓ (turn node 0067 into the right node of node 0056)
Discoloration left
Maintain rules when red-black tree inserts
The newly inserted node has the following possibilities ✧ : 1. The newly inserted node changes color directly from the root node (Property 2). (· ω<)★ if(root==null){root=new Node(data); Root. Color = color. BLACK; Return true; } 2. The parent node and uncle node of the currently inserted node are red nodes. Parent node, uncle node, grandfather node change color. if(uncle! =null&&parent. Color == color.red &&uncle. Color == color.red){// Parent is RED ->black. ChangeColor (uncle); red->black (uncle); ChangeColor (gParent); // Black ->red; // Black ->red; // the next possible conflict node node=gParent; The continue; }
graphic
3. Red-red conflict, the parent node is red, the uncle node is black, and the current inserted node is the right node of the parent node, the parent node is the right node of the grandfather node, left-rotation of the grandfather node, and color (· ω<)★
// Rotate the core idea to move the red-red conflict down to avoid sweeping up and affecting the whole treeif((uncle==null||uncle.color==Color.BLACK)&&parent.color==Color.RED){
//case2: parent red node Uncle Black node,node is the right node of the parentif(node==parent.right&&parent== gparent.right){// Left node <T> left=parent.left;if(root! =gParent&&gParent.parent.left==gParent){ gParent.parent.left=parent; }else if(root! =gParent){ gParent.parent.right=parent; }else{
root=parent;
}
parent.parent=gParent.parent;
gParent.parent=parent;
parent.left=gParent;
gParent.right=left;
if(left! =null){ left.parent=gParent; } // Change the parent node color changeColor(parent); // Red --> black changeColor(gParent); // The color of the left node of gPatent is black, and the color of the left node of gPatent is black. // So the new conflict point may be to the left of the current gParent. Node =gParent.continue; }}Copy the codeIn the figure left
3. Red red conflict, the parent node is red, the uncle node is black, and the current inserted node is the left node of the parent node, the parent node is the left node of the grandfather node, the grandfather node is right-handed, and color (· ω<)★
// Rotate the core idea to move the red-red conflict down to avoid sweeping up and affecting the whole treeif((uncle==null||uncle.color==Color.BLACK)&&parent.color==Color.RED){
if(node==parent.left&&parent== gparent.left){// Rotate node <T> right = parent.right;if(gParent! =root){if(gParent.parent.left==gParent){
gParent.parent.left=parent;
}else{ gParent.parent.right=parent; }}else{
root=parent;
}
parent.parent=gParent.parent;
parent.right=gParent;
gParent.parent=parent;
gParent.left=right;
if(right! =null){ right.parent=gParent; } // Change the parent node color changeColor(parent); // Red --> black changeColor(gParent); // gPatent's right node is the original parent's right node, and the original parent's color is red, so the original parent's right node is black. // So the new conflict point may be on the right side of the current gParent.continue; }}Copy the codeIn the figure left
All sweaty, finally finished this part
The following is my own implementation of the source code, only to achieve the method of adding, as to delete the method of the coming days.
RedBlackTree.java
import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /** * Red black tree <br> * Rule: <br> * 1. The root node must be black <br> * 2. The children of the red node must be black <br> * 3. All paths from a node to a leaf node contain the same number of black nodes <br> * 4. There are only two node colors: red and black <br> * 5. The empty leaf node is black <br> * 6. The node that has just been inserted in an undetermined position, <br> * @author Administrator * * @param <T> */ public class RedBlackTree<T category <T>> { private Node<T> root; public boolean add(T data){if(root==null){
root=new Node<T>(data);
root.color=Color.BLACK;
return true; } Node<T> node=new Node<>(data); Node<T> currNode=root; // insert position A:while(true) {if(currNode.data.compareTo(node.data)<=0){
if(currNode.right! =null){ currNode=currNode.right; }else{
currNode.right=node;
node.parent=currNode;
breakA; }}else{
if(currNode.left! =null){ currNode=currNode.left; }else{
currNode.left=node;
node.parent=currNode;
breakA; }}} // Check if it is standard red-black tree B:while(true) {if(node==null){
breakB; } // If the node is not newly inserted, go through the color change and rotation to find the next possible conflict nodeif(node.color==Color.BLACK){
break B;
}
if(root==node){// If the current node is the root node and is red, change the color directlyif(root.color==Color.RED){
changeColor(root);
}
breakB; } Node<T> parent = node.parent; // If the parent of the current node is red, red-red conflict, change the parent's colorif(parent==root){
if(root.color==Color.RED){
changeColor(root);
}
breakB; } // The parent node is black, which does not violate the red-black tree ruleif(parent.color==Color.BLACK){
break B;
}
Node<T> uncle=null;
Node<T> gParent=parent.parent;
if(parent==gParent.left){
uncle=gParent.right;
}else{ uncle=gParent.left; } / /case1: Uncle and parent are red nodesif(uncle! =null&&parent. Color == color.red &&uncle. Color == color.red){// Parent is RED ->black. ChangeColor (uncle); red->black (uncle); ChangeColor (gParent); // Black ->red; // Black ->red; // the next possible conflict node node=gParent;continue; } // Rotate the core idea to move the red-red conflict down to avoid sweeping up and affecting the whole treeif((uncle==null||uncle.color==Color.BLACK)&&parent.color==Color.RED){
//case2: parent red node Uncle Black node,node is the right node of the parentif(node==parent.right&&parent== gparent.right){// Left node <T> left=parent.left;if(root! =gParent&&gParent.parent.left==gParent){ gParent.parent.left=parent; }else if(root! =gParent){ gParent.parent.right=parent; }else{
root=parent;
}
parent.parent=gParent.parent;
gParent.parent=parent;
parent.left=gParent;
gParent.right=left;
if(left! =null){ left.parent=gParent; } // Change the parent node color changeColor(parent); // Red --> black changeColor(gParent); // The color of the left node of gPatent is black, and the color of the left node of gPatent is black. // So the new conflict point may be to the left of the current gParent. Node =gParent.continue; } / /case3: parent red node Uncle Black node,node is the left node of the parentelse if(node==parent.left&&parent== gparent.left){// Rotate node <T> right = parent.right;if(gParent! =root){if(gParent.parent.left==gParent){
gParent.parent.left=parent;
}else{ gParent.parent.right=parent; }}else{
root=parent;
}
parent.parent=gParent.parent;
parent.right=gParent;
gParent.parent=parent;
gParent.left=right;
if(right! =null){ right.parent=gParent; } // Change the parent node color changeColor(parent); // Red --> black changeColor(gParent); // gPatent's right node is the original parent's right node, and the original parent's color is red, so the original parent's right node is black. // So the new conflict point may be on the right side of the current gParent.continue;
}
}
}
cengciBinli();
return true;
}
private void changeColor(Node<T> node){
if(node.color==Color.RED){
node.color=Color.BLACK;
}else{ node.color=Color.RED; Public void midPrintNode(node <T> node){Stack< node <T>> Stack =new Stack<>();while(node! =null||! stack.isEmpty()){while(node! =null||! stack.isEmpty()){while(node! =null){ stack.push(node); node=node.left; }if(! stack.isEmpty()){ Node<T> pop = stack.pop(); System.out.print("[data:"+pop.data+",color:"+pop.color.name()+"]");
node=pop.right;
}
}
}
}
public void cengciBinli(){
System.out.println("\n-------------- hierarchical traversal ----------------"); Queue<Node<T>> Queue = new LinkedList<>(); Queue<Node<T>> sq=new LinkedList<>(); queue.add(this.root); A:while(true) {while(queue.size()>0){
Node<T> node = queue.poll();
if(node == null){
break A;
}
System.out.print("[data:"+node.data+",color:"+node.color.name()+",parent:"+(node.parent! =null? node.parent.data:"") +"]");
if(node.left ! = null){ sq.add(node.left); }if(node.right != null){
sq.add(node.right);
}
}
if(sq.size()==0){
break A;
}
queue.addAll(sq);
sq.clear();
System.out.println();
}
}
public Node<T> getRoot() {return this.root;
}
private class Node<T extends Comparable<T>>{
private T data;
private Node<T> left;
private Node<T> right;
private Node<T> parent;
private Color color;
public Node(T data){
this.data=data;
this.color=Color.RED;
}
public Node(){ } } private enum Color{ RED, BLACK; }}Copy the code