1. Basic concepts of red-black trees.

Red and black trees are both familiar and unfamiliar to many children. School middle school, only understand about; Not so much in the workplace, but in interviews. Every time you need to look at the content of a red-black tree, it's hard to understand its content in a more vivid way. Yes, the content of this article is to solve this problem, using simple language, with static and dynamic pictures (using the brain graphics memory), let you have a deeper understanding of the red black tree and clearer memory, I hope friends will not be too big when they meet the problem of red black tree again. Every node can only be red or black the root node is black and every leaf node (NIL node, empty node) is black. If one node is red, both of its children are black. That is, you can't have two red nodes next to each other on a path. All paths from any node to each of its leaves contain the same number of black nodes.Copy the code

TreeMap can add and delete nodes from a red-black tree by using put and deleteEntry.

3. TreeMap data structure

TreeMap is defined as follows:

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap extends AbstractMap and implements NavigableMap, Cloneable, Serializable interfaces. AbstractMap indicates that TreeMap is a Map that supports key-value

TreeMap put() method implementation analysis

The implementation method of TreeMap PUT () is mainly divided into two steps: first, build sorted binary tree, second, balance binary tree.

For the creation of sorted binary trees, the process of adding nodes is as follows:

The root node is retrieved as the initial node. Compared with the current node, if the value of the new node is large, the right child node of the current node is used as the new current node. Otherwise, use the left child of the current node as the new current node. Cycle recursion2The step knows until the appropriate leaf node is retrieved. Associate the new node with3Compare the nodes found in the step. If the new node is large, add it as the right child node. Otherwise, it is added as the left child node. Following this step we can add a new node to the appropriate position in the sorted binary treeCopy the code

4. Definition of red-black tree (Characteristics)

1. The root node is black. 2. Each node is either black or red. Both children of every [red] node must be [black] 4. Every leaf node (NIL) is [black] 5. The path of any node to the leaf node contains the same number of black nodes - this is also called black perfect balance 6. The newly inserted node must be [red] -> Why? If the new node is [black], it will destroy the perfect black balance no matter where it is inserted, because the path of any node to the leaf node must be different in the number of black nodes (6).Copy the code

5,Comparison between red-black trees and AVL trees

1. The time complexity of AVL tree is better than that of red-black tree, but for modern computers, the difference can be ignored. The insertion and deletion of red-black trees is easier to control than AVL trees. 3. The overall performance of red-black tree is slightly better than AVL tree. (The rotation of red-black trees is less than that of AVL trees). 4. AVL trees are better than red black trees if there are many additions and deletions, and red black trees are perfect for frequent additions and deletionsCopy the code

What is the balance between adding and removing nodes in a red-black tree? That’s left rotation, right rotation plus discoloration

left-handed,Right handadddiscolorationDefinition of (spin the opposite direction of the other half of the child node to each other)

1. To use a node as a fixed support point (rotating around the node) so that the right child becomes the parent of the rotating node, the left child of the right child becomes the right child of the rotating node, and the left child remains the same: With a node as a fixed support point (rotating around the node), its left child node becomes the parent of the rotating node, the right child node of the left child node becomes the left child node of the rotating node, and the right child node remains unchanged color change: the color of the node changes from red to black, or from black to redCopy the code

left-handed:

R stands for rotating node, which has no other special meaning. The following nodes are of no practical significanceLet’s say that this is a tree with rotation, let’s say that point R is the rotation node, according toleft-handedThe first feature:The right child of the rotation node becomes the parent of the rotation node Directly findRotate the nodeAnd then rotate the node’sThe right child nodeSet toRotate the parent node of the node. The next step is toRotate the nodetheThe right child nodetheThe left child nodeSet toRotate the right child of the nodeLook at the picture belowRight:To rotate R as the rotation node, first set the left child node L of R to be the parent node of R, and then it looks like thisAnd then the second little point, the right child of the left node of R (L) is set to the left child of R (LR), and that should be obvious from the figure above, so it looks something like this