Learn xiao Liu teacher explained red black tree records, Xiao Liu teacher B station ID: Xiao Liu source
1. What is a tree?
A tree is an abstract data type (ADT) used to simulate a collection of data with a tree-like structure. It is composed of n(n>0) finite nodes by connecting their edges to form a hierarchical set.
It is called a tree because it is shaped like an upside-down tree, with roots up and leaves down. There are many kinds of trees. A tree with more than two children on a node is called a multipath tree. A tree with at most two children on a node is called a binary tree.
Nodes: for example, A,B,C,D,E,F,G, and H are nodes. Nodes generally represent entities, which are abstract objects in the Java language.
Edge: The line connecting nodes is called edge, indicating the relationship between nodes. For example, AB is the parent-child relationship. They are called Pointers in C and references in Java.
2. Common terms for tree structures
① Path: go from one node to another node along the edge of the node, the order of the nodes through is called the path.
② Root: The nodes at the top of the tree are called roots. A tree has only one root, and if a collection of nodes and edges is to be called a tree, there must be one and only one path from the root to every other node. A is the root node.
③ Parent node: If a node has children, this node is called the parent node of its children
(4) Child nodes: The nodes in the subtree of a node are called child nodes of the node. F and G are children of C.
(5) Sibling node: nodes with the same parent node are called sibling nodes; F and G nodes are siblings of each other.
⑥ Leaf node: nodes without child nodes are called leaf nodes, also called leaf nodes. For example, H, E, F, and G in the figure above are leaf nodes.
⑦ Subtree: Each node can be the root of a subtree, and it and all of its children, the children of the child node, and so on are contained in the subtree.
The node hierarchy is defined from the root. The root is the first layer, the child nodes of the root are the second layer, and so on.
⑨ depth: For any node n, the depth of n is the unique path length from the root to n, and the depth of the root is 0. (Viewed from above)
⑩ Height: For any node N, the height of n is the longest path from n to a leaf, and the height of all leaves is 0. (Viewed from bottom up)
Binary search tree
Binary tree: Each node of a tree can have a maximum of two child nodes.
Binary search tree: a special binary tree on which constraints are attached.
If its left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root node. If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node. Its left and right subtrees are also binary sort trees respectively.Copy the code
Binary search tree – Search node:
To find a node, we must start at the root node.
① If the search value is larger than the current node value, search the right subtree;
② If the search value is equal to the current node value, stop the search (termination condition);
③ If the search value is less than the current node value, search the left subtree.
Binary search tree – Insert node:
To insert a node, you must first find the insertion location. Similar to the search operation, due to the particularity of binary search trees,
The nodes to be inserted also need to be compared from the root node. If the nodes are smaller than the root node, they are compared with the left subtree of the root node.
Otherwise, it is compared with the right subtree until the left subtree is empty or the right subtree is empty, then it is inserted into the corresponding empty position.
Binary search tree – Traversal nodes:
To traverse a tree is to visit each node of the tree in a particular order. More commonly used are pre-order traversal, order traversal and order traversal. The most commonly used binary search tree is middle order traversal.
Middle order traversal: left subtree -> root node -> right subtree
② Pre-order traversal: root node -> left subtree -> right subtree
③ Post-order traversal: left subtree -> right subtree -> root node
Binary search tree – Find maximum and minimum values:
To find the minimum, you find the left child of the root, and then you keep finding the left child of the left child, until you find a node that has no left child, and that node is the minimum. Similarly, to find the maximum, keep looking for the right child of the root node until there are no right children, which is the maximum.
Binary search tree – Delete node:
Node deletion is the most complex operation in binary search tree. There are three cases of node deletion, the first two are relatively simple, but the third is very complicated.
1. The node is a leaf node
2. This node has one child node
3. This node has two children
① Delete the node that has no child node
To remove a leaf node, simply change the parent reference value of the node to NULL.
② Delete the node with one child node
To delete a node with a child node, we simply change the reference of the parent node to point to the child node of the node.
③ Delete the node with two child nodes
When the deleted node has two child nodes, the location of the two child nodes cannot be handled after the deletion. Since we could not handle it, we thought of a way to replace the deleted node with another node, so which node to replace?
We know that nodes in a binary search tree are arranged according to keywords, and the second-highest keyword of a node is its middle-order traversal successor node. By replacing the deleted node with a successor node, it is clear that the binary search tree is still in order.
So how to find the middle-order successor of the deleted node?
In fact, we have a little analysis, this is actually to find the smallest node in the node set larger than the key value of the deleted node, only in this way to replace the deleted node can meet the characteristics of the binary search tree.
The successor node is the smallest node larger than the deleted node.
④ Is it necessary to delete it?
From the above discussion on delete classification, we find that deleting the Node is quite complicated. In fact, we do not need to delete the Node. We just need to add an identification field isDelete to the Node class.
If this field is true, the node is deleted; otherwise, the node is not deleted. This way, deleting nodes does not change the structure of the tree.
The impact is that the query needs to determine whether the node has been deleted.
Binary search tree-time complexity analysis:
1. Review the classical binary search algorithm
[1,2,3,4,5,6,7,8,9… 100]
Violent algorithm: performance is good on good days, performance plummets on bad days.
Binary search algorithm: The data source must be an ordered array, and the performance is very good, each iteration of the query can exclude half of the results.
2. What are the biggest defects of binary search algorithm?
Force a dependency on ordered arrays to perform well.
3. What are the drawbacks of arrays?
There’s no way to insert quickly, no way to expand
4. So how can we have the high performance of binary lookup and the flexibility of linked lists?
Binary search tree!!
5. Time complexity calculation process of binary search algorithm
| Number of queries | Number of remaining elements to be queried |
|---|---|
| 1 | N/2 |
| 2 | N/(2^2) |
| 3 | N/(2^3) |
| K | N/(2^K) |
As can be seen from the table above, N/(2^K) must be greater than or equal to 1, that is, N/(2^K)>=1. We calculate the time complexity according to the worst case, that is, we only find the data we want when we look up the last remaining number, that is, we find the data we want
N/(2^K) = 1 => 2^K = N => K = log2 (N) =>
Time complexity of binary search algorithm: O(log2(N)) => O(logN)
Common binary search tree fatal flaw: how efficient is this binary tree query? O(N)
How to solve the problem of binary search tree degenerating into linear linked list? If the tree can automatically balance the two sides when inserting elements, it will maintain good lookup performance.
AVL tree Introduction:
What are the characteristics of AVL trees?
1. All features of binary search tree.
2. The height difference between the left and right subtrees of each node is at most equal to 1.
The meaning of “balance” in the balanced binary search tree is to make the whole tree look “symmetric” and “balanced”, so that the left subtree is not tall and the right subtree is very short. This keeps the height of the whole tree relatively low, and the insertion, deletion, and lookup operations are more efficient.
Why do you need a red black tree when you have a balanced tree?
Although the balanced tree solves the problem that binary search tree degenerates into an approximate linked list and can control the search time within O(logn), it is not the best.
Because the left child of each node is balanced tree request tree and the height of the right subtree is poor at most equal to 1, this request is too strict, lead to every time to insert/delete nodes, almost can destroy balance is the second rule of the tree, and then we all need to adjust by left-handed and a right-handed, the balance of the once again become a meet the requirements of the tree.
Obviously, the performance of the balanced tree would be compromised if it had to be adjusted frequently in a scenario where there was a lot of insertion and deletion, so the red-black tree was invented to solve this problem.
4. Red-black tree principle
Properties of red-black trees:
Property 1: Each node is either black or red;
Property 2: The root node is black;
Property 3: Every leaf node is black and NIL, that is, the leaf node does not store data;
Property 4: No adjacent nodes can be red at the same time, that is, red nodes are separated by black nodes, and no two red nodes can be connected.
Property 5: Each node, and all paths from that node to its reachable leaf node, contains the same number of black nodes. Commonly known as: black high!
From property 5, it can be inferred: Property 5.1: If a node has sunspot nodes, the node must have two child nodes.
Red-black tree is not a perfectly balanced binary search tree. It can be seen from the figure that the left subtree of root node P is obviously higher than the right subtree, but the number of black nodes of the left and right subtrees is the same, that is, the path from any node to every leaf node contains the same number of black nodes (property 5). So we call it a red-black tree and this equilibrium is black perfect equilibrium.
Red black trees are self-balancing. What does it depend on? Three operations: left rotation, right rotation and color change.
1. Color change: the color of the node changes from red to black or from black to red.
2. Left-rotation: a node is taken as the fulcrum (rotation node), and its right child becomes the parent of the rotation node, the left child of the right child becomes the right child of the rotation node, and the left child remains unchanged.
3. Right rotation: a node is taken as the fulcrum (rotation node), and its left child becomes the parent of the rotation node, the right child of the left child becomes the left child of the rotation node, and the right child remains unchanged.
Left-handed graphic
Right here
Red-black tree lookup:
Red-black tree insertion:
The insert operation consists of two parts:
1. Locate the insertion position
2. Self-balancing after insertion
Note: insert node, must be red, the reason is simple, red when the parent node (if any) is black, the black balance of the red-black tree is not broken, do not need to do self-balance operation. But if the insertion node is black, then the black node in the subtree where the insertion is always one more, so it has to be self-balanced.
Before each situation, agree:
Red-black tree node insertion scenario analysis:
Scenario 1: The red-black tree is empty
In the simplest case, you just use the insertion node as the root node
Note: According to red-black tree property 2: the root node is black. I also need to make the insert node black.
Scenario 2: The Key inserted into the node already exists
Process: Update the value of the current node to the value of the inserted node.
Scenario 3: The parent of the inserted node is black
Since the nodes inserted are red, when black nodes are inserted, the balance of the red-black tree will not be affected. It can be directly inserted without self-balancing.
Scenario 4: The parent node of the inserted node is red
Again, remember property 2 of a red-black tree: the root is black. If the parent of the inserted node is a red node, then that parent cannot be the root, so the inserted node always has a grandparent.
This is critical because subsequent rotation operations will definitely require grandparent.
Insert scenario 4.1: The uncle node exists and is red
According to property 4 of red-black tree, red nodes cannot be connected ==> Grandfather nodes must be black nodes.
Because you can’t have two connected red nodes at the same time. Then the number of red and black layers to be inserted into the subtree is: black, red and red.
Obviously the easiest way to do this is to change it to: red black red
Processing:
1. Change the color of P and U to black
2. Change the PP to red
3. Set the PP to the current node and perform subsequent operations
As you can see, we have set PP to red. If the parent of PP is black, there is no need to do anything;
But if the parent of PP is red, it violates the red-black tree property. Therefore, PP needs to be set as the current node, and continue to perform the self-balancing process of the insertion operation until it is balanced.
Insert scenario 4.2: The uncle node does not exist or is black, and the father node of the insert node is the left child of the grandfather node
Note: From the purely insertion point, the uncle node is not a NIL node, otherwise it breaks red-black tree property 5 and this path will have one more black node than the other paths.
Insert scenario 4.2.1: Newly inserted node, the left child node of its parent node (LL double red case)
Processing:
1. Change color: set P to black and PP to red
2. Right-rotate the PP node
Insert scenario 4.2.2: Newly inserted node, the right child node of its parent node (LR double red case)
Processing:
1. Left-handed rotation of P
2. Set P to the current node to obtain LL red
3. Treat as LL red (1. Change color 2. Dextral PP)
Insertion scenario 4.3: The uncle node does not exist or is black, and the father node of the inserted node is the right child of the grandfather node
This scenario corresponds to scenario 4.2, but the direction is reversed and we look at the picture directly.
Insert scenario 4.3.1: Newly inserted node, the right child of its parent node (RR double red case)
Solution: 1. Change color: set P to black and PP to red. 2
Insert scenario 4.3.2: Newly inserted node, the left child of its parent node (RL red)
Solution: 1. Right-rotate P. 2. Set P as the current node, and obtain RR red case 3. Treat as RR red (1. Change color 2. Left-handed PP)
5. Case study of red-black tree insertion
Red black tree implementation
package rbtree;
public class RBTree<K extends Comparable<K>, V> {
private static final boolean RED = true;
private static final boolean BLACK = false;
/** Defines a reference to the root node */
private RBNode root;
/** * Public insert interface *@param The key key *@param The value value * /
public void insert(K key, V value) {
RBNode node = new RBNode();
node.setKey(key);
node.setValue(value);
node.setColor(RED);
insert(node);
}
/** * Internal insert interface definition */
private void insert(RBNode node) {
//1. Find the insertion position
RBNode parent = null;
RBNode x = this.root;
while(x ! =null) {
parent = x;
If a > b, return 1, otherwise return -1, equal return 0
int cmp = node.key.compareTo(parent.key);
if(cmp < 0) {
x = x.left;
} else if(cmp == 0) {
parent.setValue(node.value);
return;
} else {
x = x.right;
}
}
node.parent = parent;
if(parent ! =null) {
if(node.key.compareTo(parent.key) < 0) {
parent.left = node;
} else{ parent.right = node; }}else {
this.root = node;
}
// After insertion, we need to repair the red black tree to rebalance the red black tree again.
insertFixUp(node);
}
/ * * * insert after repair the red-black tree balance method * | - scene 1: a red-black tree is empty tree, the root section touched to black * | - scene 2: insert node key already exists, do not need to deal with * | - scene 3: Insert the node's parent is black, because of no change of insert path of black nodes, so the red-black tree still balance, don't need to deal with scenario 4 need we to deal with * * * | - scene 4: insert the node's parent red * | - 4.1) : Uncle nodes exist, and red (parent - tertiary double red), * will dad and uncle section transition is black, the grandpa section transition, to red, and then to grandpa nodes for the current node next processing * | - 4.2) : uncle node does not exist, or is black, the parent node for grandpa left subtree * | - scene 2: Inserted into the left child node of the node as its parent (LL), will dad dyed black, grandpa will be dyed red, with grandpa node right * | - 4.2.2) : Insert the right child node as its parent node (LR), * to father nodes are left-handed, get LL double red scene (2), and then specify father node to the next step for the current node processing * | - 4.3) : Uncle node does not exist, or is black, the parent node for grandpa node right subtree, * | - scene 4.3.1: insert the right child node as its parent node (RR), the father dyed black, grandpa will be dyed red, with grandpa node sinistral * | - 4.3.2) : Insert the node as the left child node of its parent node (RL case), * rotate the parent node to the right to obtain RR double red scenario (4.3.1), and then designate the parent node as the current node for the next step */
private void insertFixUp(RBNode node) {
this.root.setColor(BLACK);
RBNode parent = parentOf(node);
RBNode gparent = parentOf(parent);
// Scenario 4: The parent of the inserted node is red
if(parent ! =null && isRed(parent)) {
// If the parent node is red, then there must be a grandfather node
RBNode uncle = null;
if (parent == gparent.left) { // The parent node is the left child tree of the grandfather node
uncle = gparent.right;
// Scenario 4.1: The uncle node exists and is red (parent - uncle double red)
if(uncle ! =null && isRed(uncle)) {
// Color the father and uncle nodes black, and the grandfather node red, and then take the grandfather node as the current node for the next step
setBlack(parent);
setBlack(uncle);
setRed(gparent);
insertFixUp(gparent);
return;
}
// Scenario 4.2: The uncle node does not exist or is black
if (uncle == null || isBlack(uncle)) {
// Scenario 4.2.1: Insert the node as the left child node of its parent node (LL case), dye the father black, dye the grandfather red, and rotate the grandfather node right
if (node == parent.left) {
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
return;
}
// Scenario 4.2.2: Insert the node as the right child node of its parent node (LR case), rotate the parent node left to get LL double red scenario (4.2.1), and then designate the parent node as the current node for the next step
if (node == parent.right) {
leftRotate(parent);
insertFixUp(parent);
return; }}}else { // The parent node is the right child tree of the grandfather node
uncle = gparent.left;
// Scenario 4.1: The uncle node exists and is red (parent - uncle double red)
if(uncle ! =null && isRed(uncle)) {
// Color the father and uncle nodes black, and the grandfather node red, and then take the grandfather node as the current node for the next step
setBlack(parent);
setBlack(uncle);
setRed(gparent);
insertFixUp(gparent);
return;
}
// Scenario 4.3: The uncle node does not exist or is black
if (uncle == null || isBlack(uncle)) {
// Scenario 4.3.1: Insert the node as the right child of its parent (RR case), dye the father black, dye the grandfather red, and rotate the grandfather node left
if (node == parent.right) {
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
return;
}
// Scenario 4.3.2: Insert the node as the left child node of its parent node (RL case), rotate the parent node right to get RR double red scenario (4.3.1), and then designate the parent node as the current node for the next step
if (node == parent.left) {
rightRotate(parent);
insertFixUp(parent);
return;
}
}
}
}
}
/** ** ** ** */
public void inOrderPrint() {
if (this.root ! =null) {
inOrderPrint(this.root);
}
}
private void inOrderPrint(RBNode node) {
inOrderPrint(node.left);
System.out.println("key: " + node.getKey() + ", value: " + node.getValue());
inOrderPrint(node.right);
}
/ sinistral method * * * * sinistral diagram: left-handed node * p p * x | | * x * y / \ -- -- -- -- > / / \ \ * ry lx y x * / \ * ly ry lx ly * * 1. Point the right child of x to the left child of y and update the parent of the left child of y to x * 2. When the parent of x is not empty, point the parent of x to y and update the parent of y to x * 3. Point the left child of y to x and update the parent of x to y */
private void leftRotate(RBNode x) {
RBNode y = x.right;
// 1. Point the right child of x to the left subtree of y and update the parent of the left node of y to x
x.right = y.left;
if(y.left ! =null) {
y.left.parent = x;
}
// 2. When the parent of x is not empty, point x's parent to y and update y's parent to the parent of x
if(x.parent ! =null) {
if (x.parent.left == x) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.parent = x.parent;
} else {
this.root = y;
this.root.parent = null;
}
// 3. Set y's left child node to x and update x's parent node to y
y.left = x;
x.parent = y;
}
/ * * * * right method right diagram: right node p p * * * y | | * * x/y \ -- -- -- -- > / \ * x ry lx / \ \ * y * lx ly ly ry * * 1. Change the left child of y to the left child of x, and update the parent of the left child of x to y * 2. When y's parent node is not empty, point y's parent node to x and update x's parent node to y's parent * 3. Point the right child of x to y and update the parent of y to x */
private void rightRotate(RBNode y) {
RBNode x = y.left;
// 1. Change the parent of the left child of x to y
y.left = x.right;
if(x.right ! =null) {
x.right.parent = y;
}
// 2. If y's parent is not empty, point y's parent to x and update x's parent to y's parent
if(y.parent ! =null) {
if (y == y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
x.parent = y.parent;
} else {
this.root = x;
this.root.parent = null;
}
// 3. Change the parent node of y to x
x.right = y;
y.parent = x;
}
/** * Sets the current node to black *@param node* /
private void setBlack(RBNode node) {
if(node ! =null) { node.setColor(BLACK); }}/** * Sets the current node to red *@param node* /
private void setRed(RBNode node) {
if(node ! =null) { node.setColor(RED); }}/** * Checks whether the current node is black *@param node
* @return* /
private boolean isBlack(RBNode node) {
if(node ! =null) {
return node.color == BLACK;
}
return false;
}
/** * Checks whether the current node is red *@param node
* @return* /
private boolean isRed(RBNode node) {
if(node ! =null) {
return node.color == RED;
}
return false;
}
/** * Gets the parent node * of the current node@param node
* @return* /
private RBNode parentOf(RBNode node) {
if(node ! =null) {
return node.parent;
}
return null;
}
/** * Create RBNode *@param <K>
* @param <V>
*/
static class RBNode<K extends Comparable<K>, V> {
private RBNode left;
private RBNode right;
private RBNode parent;
private boolean color;
private K key;
private V value;
public RBNode() {
}
public RBNode(RBNode left, RBNode right, RBNode parent, boolean color, K key, V value) {
this.left = left;
this.right = right;
this.parent = parent;
this.color = color;
this.key = key;
this.value = value;
}
public RBNode getLeft() {
return left;
}
public void setLeft(RBNode left) {
this.left = left;
}
public RBNode getRight() {
return right;
}
public void setRight(RBNode right) {
this.right = right;
}
public RBNode getParent() {
return parent;
}
public void setParent(RBNode parent) {
this.parent = parent;
}
public boolean isColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value; }}/** * Print Method */
public void padding(String ch, int n) {
int i;
for (i = 0; i < n; i++) { System.out.printf(ch); }}void print_node(RBNode root, int level) {
if (root == null) {
padding("\t", level);
System.out.println("NIL");
} else {
print_node(root.right, level + 1);
padding("\t", level);
if (root.color == BLACK) {
System.out.printf(root.key + "(" + (root.isColor() ? "Red" : "Black") + ")" + "\n");
} else
System.out.printf(root.key + "(" + (root.isColor() ? "Red" : "Black") + ")" + "\n");
print_node(root.left, level + 1); }}void print_tree() {
print_node(this.root, 0);
System.out.printf("-------------------------------------------\n"); }}/** * prints the red black tree */
public class TreeOperation {
/* Example of tree structure: 1 / \ 23 / \ / \ 4 5 6 7 */
// Get the number of layers of the tree
public static int getTreeDepth(RBTree.RBNode root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
}
private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// Make sure the input tree is not empty
if (currNode == null) return;
// Save the current node to a two-dimensional array
res[rowIndex][columnIndex] = String.valueOf(currNode.getKey() + "-" + (currNode.isColor() ? "R" : "B") + "");
// Calculate the current level in the tree
int currLevel = ((rowIndex + 1) / 2);
// If you reach the last layer, return
if (currLevel == treeDepth) return;
// Calculate the interval between the current row and the next row, each element (the interval between the next row's column index and the current element's column index)
int gap = treeDepth - currLevel - 1;
// Judge the left son. If there is a left son, record the corresponding "/" and the value of the left son
if(currNode.getLeft() ! =null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// Judge the right son, if there is a right son, then record the corresponding "\" and the value of the right son
if(currNode.getRight() ! =null) {
res[rowIndex + 1][columnIndex + gap] = "\ \";
writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public static void show(RBTree.RBNode root) {
if (root == null) System.out.println("EMPTY!");
// Get the depth of the tree
int treeDepth = getTreeDepth(root);
// The width of the last line is 2 to the power of n minus 1 times 3, plus 1
// As the width of the entire two-dimensional array
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// Use an array of strings to store the elements that should be displayed at each location
String[][] res = new String[arrayHeight][arrayWidth];
// Initializes the array with a space by default
for (int i = 0; i < arrayHeight; i ++) {
for (int j = 0; j < arrayWidth; j ++) {
res[i][j] = ""; }}// Process the entire tree recursively, starting from the root node
// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
writeArray(root, 0, arrayWidth/ 2, res, treeDepth);
// At this point, all the elements that need to be displayed are stored in a two-dimensional array, which can be spliced and printed
for (String[] line: res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i ++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2: line[i].length() - 1; } } System.out.println(sb.toString()); }}}/** * TestRBTree */
public class TestRBTree {
public static void main(String[] args) {
RBTree<String.Object> rbt = new RBTree();
while(true) {
Scanner sc = new Scanner(System.in);
System.out.println("Please enter key:");
String key = sc.next();
rbt.insert(key, null);
TreeOperation.show(rbt.getRoot());
// rbt.print_tree();}}}Copy the code