Through Java util. Treemap source code to enhance the understanding of red and black trees

Before that, the programming tips have sorted out a lot of ideas and solutions about the red black tree of classical problems. This article is through the analysis of Java util. Treemap source code allows you to have a deeper understanding of the problem of red black tree through examples.

This article will combine jdk1 6 treemap source code, to explore the mystery of red black tree. Red black tree is to solve the unbalanced problem of binary search tree.

When inserting (or deleting) a new node, in order to keep the tree balanced, certain rules must be followed. This rule is the red black rule: 1) each node is either red or black 2) the root is always black 3) if the node is red, Then its child nodes must be black (on the contrary, it must not be true). 4) each path from the following node to the leaf node or empty child node must contain the same number of black nodes

Insert a new node

The insertion process of red black tree is basically the same as that of ordinary binary search tree: go from heel to insertion point, and determine whether to go left or right at each node by comparing the relative size of node keywords.

However, in red black tree species, finding the insertion point is more complex because of color transformation and rotation. Fixafterinsertion() method is to handle color transformation and rotation. It is necessary to master how it maintains the tree's balance (use rotations and the color rules to maintain the tree's balance).

In the following discussion, x, P, and G are used to represent associated nodes. X represents a special node. P is the parent of X and G is the parent of P.

X is a node that has caused a rule violation. (Sometimes X refers to a newly inserted node,and sometimes to the child node when a parent and child have a redred conflict.)

On the way down the tree to find the insertion point,you perform a color flip whenever you find a black node with two red children (a violation of Rule 2). Sometimes the flip causes a red-red conflict (a violation of Rule 3). Call the red child X and the red parent P. The conflict can be fixed with a single rotation or a double rotation,depending on whether X is an outside or inside grandchild of G. Following color flips and rotations,you continue down to the insertion point and insert the new node.

After you've inserted the new node X,if P is black,you simply attach the new red node. If P is red,there are two possibilities: X can be an outside or inside grandchild of G. If X is an outside grandchild,you perform one rotation,and if it's an inside grandchild,you perform two. This restores the tree to a balanced state.

According to the above explanation, the discussion can be divided into three parts, arranged according to the complexity: 1) color flips on the way down; 2) rotations after the node is inserted; 3) rotations on the way down

Color flips on the way down

Here's the rule: Every time the insertion routine encounters a black node that has two red children,it must change the children to black and the parent to red (unless the parent is the root,which always remains black)

The flip leaves unchanged the number of black nodes on the path from the root on down through P to the leaf or null nodes.

Although color transformation does not violate rule 4, it may violate rule 3. If the parent of P is black, there will be no problem when P changes from black to red. However, if the parent of P is red, two red nodes will be connected after the color of P changes. This problem needs to be solved before continuing to insert new nodes down the path. This problem can be corrected by rotation, as you will see below.

Rotations after the node is inserted

Before inserting a new node, the tree complies with the red black rule. After inserting a new node, the tree is unbalanced. At this time, the balance of the tree needs to be adjusted by rotation to make it comply with the red black rule again.

Possibility 1: P is black, so you don't have to do anything. Just insert it.

Possibility 2: if P is red and X is an outer descendant node of G, a rotation and some color changes are required. Take the insertion of 50, 25, 75, 12 and 6 as an example. Note that node 6 is an outer descendant node, and both it and its parent node are red.

In this example, X is an outer descendant node and a left child node, and X is an outer descendant node and a right child node, which is symmetrical to this. By creating a tree with 50, 87 and 93, draw another picture in the same way, which is omitted here.

Possibility 3: if P is red and X is an inner descendant node of G, it needs two rotations and some color changes. Taking the insertion of 50 and 18 as an example, note that node 18 is an inner descendant node, and both it and its parent node are red.

Rotations on the way down

Before inserting a new node, the tree actually violates the red black rule, so it needs to be adjusted before inserting a new node. Therefore, the topic of this discussion is "when preparing to insert a new node on the way down, adjust it to make it a standard red black tree, and then insert a new node".

Outer descendant node

Take the insertion of 50, 37, 6, 18 and 3 as an example. The node violating the rule in the example is an outer descendant node.

Inner descendant node

Take the insertion of 50, 31 and 43 as an example. In the example, the node violating the rule is an inner descendant node.

Efficiency of red black tree

Similar to the general binary search tree, the time complexity of finding, inserting and deleting red black tree is O (log2n).

The search time of red black tree should be almost the same as that of ordinary binary search tree. Because the red black feature is not used in the search process. The additional overhead is that the storage space of each node is slightly increased to store red and black colors (a boolean variable).

The insertion and deletion time should be increased by a constant factor, because color transformation and rotation have to be performed on the downstream path and insertion point. On average, one insertion requires about one rotation.

Because in most applications, the number of searches is more than the number of inserts and deletions, the application of red black tree instead of ordinary binary search tree will not increase too much time overhead.