I don’t know if you have seen the video of the interviewer being killed today. My magical colleague did not know that the brain circuit was suddenly opened up and asked in the office: Is it possible that the interviewer asked about the red black tree, which caused the interviewer to ask hair? All asked. Then there was a buzz around the office
Tree, one of the key points of data structure and algorithm in college, was really a headache for a long time, but in fact, when I think about it now, no change, still a headache, look at the following picture, the content of the tree
And the content of the tree and binary tree as the focus, first to review the basic knowledge
BST tree:
Binary Search Tree (BST), also known as Binary sorting Tree, is a kind of Tree. Data is organized by Binary Tree. Each node of the Tree contains key value, data value, pointer to the left child node, and pointer to the right child node. The key value is the most core part, and its value determines the organizational shape of the tree. The data value data is the corresponding data of this node. Some scenarios can be ignored. For example, key is the ID number and data is the name of the node. The pointer to the left child node refers to the left child node; The pointer to the right child points to the right child.
Features:
The left and right subtrees are also binary search trees.
All nodes in the left subtree have keys less than those of its root node. All nodes in the right subtree are greater than the key of their root node. The binary search tree can be an empty tree.
In general, each node in the tree has a different key value, but the same key value can be inserted into the tree as needed
AVL tree:
AVL tree, also known as balanced binary search tree, AVL is the short name of its inventor. AVL tree is a kind of tree, and it is also a binary search tree, the difference is that it can ensure the balance of binary search tree through a certain mechanism, the query efficiency of balanced binary search tree is higher.
Features:
AVL tree is a binary search tree.
The left and right child nodes of an AVL tree are also AVL trees.
AVL trees have all the basic features of binary search trees.
The absolute value of the difference between the height of the left and right child nodes of each node is at most 1, that is, the balance factor is in the range [-1,1].
Another one is the focus of our discussion today: red black trees, let’s take a look
Red and black (Red – black) tree
Binary search tree (AVL) is a self-balanced binary search tree, invented by Rudolf Bayer in 1972. It is similar to AVL trees in that the binary search tree can be balanced by rotation during insertion and deletion operations, so as to achieve efficient search performance. It can find, insert, and delete things in order logn time. A red-black tree is an equivalent of a two-three-four tree, but some red-black trees have to be a mangrove tree on the left, so it’s an equivalent of a two-three-four tree. For AVL trees, red-black trees sacrifice some balance in exchange for a small amount of rotation during insert/delete operations, and perform better overall than AVL trees.
Features:
Nodes are red or black. The root node is black.
Each leaf node (NIL node) is black.
Two children of each red node are black. (There cannot be two consecutive red nodes on all paths from each leaf to the root.) All paths from any node to each of its leaves contain the same number of black nodes.
The maximum path is not more than twice the minimum path
This is a simple red-black tree. Where Nil is the leaf node, and it’s black. (The black leaf nodes of H and M are not drawn)
At this point, to avoid confusion, we also need to agree on the names of some nodes of a red-black tree, as shown in Figure 2.
The node we are working on is called the current node. D in Figure 2 is called the parent, its father’s other child is called the sibling, and the father’s father is called the grandfather.
3. Basic operations
What does a red-black tree need to be self-balancing? Three operations: left rotation, right rotation and color change.
- Left-rotation: Counterclockwise rotation, the parent node is replaced by its right child and becomes its own left child (note: left-rotation only affects the structure of the rotation node and its right child, and moves the right child to the left child).
- Dextral: A clockwise rotation in which the parent node is replaced by the left child and becomes its own right child.
- Discoloration: the color of the node changes from red to black or from black to red.
So it’s not hard to see that any rotation is locally changing the nodes of the tree, but in order to maintain the red-black tree nature, the nodes can’t move around, they have to change color. How to change? There are different ways to do it. Let’s see
At this point, the color-changing task is completed, according to the steps, meet the rules, step by step, miss a step may not understand
Okay, so that’s all I have to say about the theory. Are red black trees difficult? Personally, TO be honest, I find this shit too embarrassing
4. Partial implementation of red-black tree
Node implementation of red-black tree
The red-black tree is an improvement on the binary search tree, so the nodes are similar to the binary search tree, except that a Boolean variable is added to represent the node color. public class RBNode<T extends Comparable<T>>{ boolean color; // color T key; RBNode<T> left; RBNode<T> right; // RBNode<T> parent; Public RBNode(T key, Boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {this.key = key; this.color = color; this.parent = parent; this.left = left; this.right = right; } public T getKey() { return key; } public String toString() { return "" + key + (this.color == RED? "R" : "B"); }}Copy the codeThe concrete realization of left-handed rotation
Face on the concept of sinistral already has the perceptual knowledge, there is no longer here, we combine the above diagram from the following code, to discuss specific implementation: her left spin / * * * * * * * * * * * * * to the red and black tree node x for left-handed operation * * * * * * * * * * * * * * * * * * / / * * sinistral diagram: Left-handed * left-handed on node X does three things: * 1. Assign the left child of y to the right child of X, and assign x to the parent of the left child of y (when the left child of y is not null) * 2. Assign the parent of x, P (non-null), to the parent of y, and update the child of P to y(left or right) * 3. Private void leftRotate(RBNode<T> x) {//1. Assign the left child of y to the right child of x, and assign x to the parent of the left child of y (when the left child of y is not null) RBNode<T> y = x. light; x.right = y.left; if(y.left ! = null) y.left.parent = x; //2. Assign the parent node p of x to the parent node of y, and update the child node of P to y(left or right) y.parent = x.parent; if(x.parent == null) { this.root = y; Else {if(x == x.parent.left)} else {if(x == x.parent.left = y; // set y to the left child else x.parent.right = y; } //3. Set the left child of y to x and the parent node of x to y. lift = x; x.parent = y; }Copy the codeDextral rotation is realized
On the concept of face right-handed already has the perceptual knowledge, there is no longer here, we combine the above diagram from the following code, to explore the specific implementation of dextral: / * * * * * * * * * * * * * right on red and black tree node y for operation * * * * * * * * * * * * * * * * * * / / * * sinistral diagram: Right-handed * right-handed on node Y does three things: * 1. Assign the right child of x to the left child of y, and assign y to the parent of the right child of X (when the right child of x is non-null) * 2. Assign y's parent p(non-null) to x's parent, and update P's child to x(left or right) * 3. Private void rightRotate(RBNode<T> y) {//1. Assign the left child of y to the right child of X, and assign x to the parent of the left child of y (when the left child of y is not null) RBNode<T> x = y.left; y.left = x.right; if(x.right ! = null) x.right.parent = y; //2. Assign the parent node of x (p) to the parent node of y, and update the child node of P to y(left or right). if(y.parent == null) { this.root = x; } else {if(y == y.parent.right) // If x is left child y.parent.right = x; // set y to the left child else y.parent.left = x; } //3. Set the left child of y to x and the parent of x to y. y.parent = x; }Copy the codeFunction of 5.
Here I will briefly introduce the reasons for the length (I will not admit that I am hungry and want to have a midnight snack, hey, hey, hey), I will introduce in detail later
5.1 find
Because a red-black tree is a binary balanced tree, and the search does not destroy the balance of the tree, so the search is the same as the search of the binary balanced tree, to make you better understand, look at the following binary tree search flow chart
Very simple, but simple doesn’t mean it’s not efficient. Because a red-black tree is always perfectly balanced with black, its worst-case search time is O(2lgN), when the whole tree is just separated from the black. Such a good search efficiency is due to the self-balancing characteristics of red-black trees, and the insertion operation of red-black trees has contributed to this
5.2 insert
The insert operation consists of two parts:
Find the parent node to insert by looking for the insert location; Two self balancing after insertion.
Finding the parent of an insert is easy, not much different from finding it, but to summarize it with a flow chart
Special attention:
What if you’re in an interview and someone asks you what color you want to insert nodes? The answer is red. The reason for this is simple: if the parent is black (if any), the black balance of the red-black tree is not broken and there is no need for self-balancing. 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.
There is also a delete, is too hungry, not, can not casually deal with everyone, listen to me next time decomposition, ha ha ha, we will explain the application of red black tree in detail next time
This article is published by the Java Architects Association