"Algorithm - Simple to Understand" red black tree insertion

First, “Algorithm – Simple” N fork tree introduction

Two, “Algorithm – simple” red black tree rotation

Three, “Algorithm – Simple” red black tree insertion

4. Delete the red black tree of algorithm – Simple and Simple

One, foreword

We believe that you have the basic knowledge of node rotation, this article directly into the topic: new nodes.

There are two basic theories for new nodes: the new node must be inserted into a leaf node (unless the tree is empty); The color of the new node must be red first.

The first point is easy to understand, because RBT is also a BST tree, so after finding the leaf node through dichotomy, insert a new node. As for point 2, why is the new node red? \color{red}{as for point 2, why is the new node red? } As for point 2, why is the new node red? This is to satisfy the property of point 5 of red-black tree (the number of black nodes on all paths from any node to the leaf node must be the same). Therefore, adding red nodes will not change this property.

Second, the insert

A) According to the above basic theory, insertion can also be divided into:

The new node is in the left leaf node of the left subtree.
The new node is in the right leaf node of the left subtree.
The new node is in the left leaf node of the right subtree.
The new node is in the right leaf node of the right subtree.

B) At the same time because the new node is a red node:

If the parent is black, it’s done, no adjustments needed;
If the parent node is red, then it violates point 4 of RBT, there cannot be consecutive red nodes adjacent to the upper and lower nodes;

So, we only need to consider the four cases in (A) + the second case in (B).

When adjusting a red-black tree, we need to look not only at the parent node, but also at the uncle node (both the father and uncle nodes are the sons of their grandfather) :As shown above:

Before 14 nodes are inserted, possible states are as follows: grandfather black, father red, and uncle black.
After 14 nodes are inserted, point 4 is violated;

But if you just change the color of the “parent”, you might violate point 5 (all paths have the same number of black nodes).

This is because the RBT has met the 5 requirements before, but the color of “parent node” is inconsistent with that of “uncle node”.

You can see the example of red-black tree in the introduction to N-tree in Algorithm-Simple.

Therefore, after inserting the node, whether to adjust the RBT depends on the color of the parent node and the uncle node, and then consider the left or right rotation of the subtree.

2.1. Left subtree + new node

If the parent node is black, the time ends.

While loop \color{red}{While loop}While loop: when the parent exists && the parent is red (the grandfather must be black, RBT point 4) : 2. If the uncle node is red, then;

Change the parent node and uncle node to black, and the grandfather node to red;
Point the current node to the grandfather node;
To continue;

If the new node is the right node of the parent node:

Left-handed parent node;
Swap the pointer between the parent node and the new node;

If the uncle node is black (the uncle node is black if it does not exist, and the NIL node is black if the RBT leaf 3 is black), then:

Change the parent node to black and the grandfather node to red;
Dextral grandfather node;
To continue;

For the above 2, 3 and 4, we use the figure to illustrate:

Schematic diagram of Point 4:

Schematic diagram of Point 3:

Schematic diagram of Point 2:

Please take a closer look at the three diagrams above:

You will find that the situation in point 2 and 3 will eventually translate into the initial state in point 4! Let me combine the above three pictures into a big picture.

2.2. Right subtree + new node

After analyzing “left subtree + new node”, “right subtree + new node” is actually a left, right, and rotation interchange of its conditions!

2.3 complete legend

Third, algorithm implementation

Public class RBTree {/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * insert the new node *****************************************************************************/ public void insert(TreeNode cur) { TreeNode p = root; TreeNode g = p; while (p ! = null) { g = p; if (cur.value < p.value) { p = p.left; } else { p = p.right; } } if (g == null) { root = cur; } else if (cur.value < g.value) { g.left = cur; } else { g.right = cur; } cur.parent = g; cur.color = TreeNode.RED; // If a node is red, its children must be black. // If a node is red, its children must be black. // If a node is red, its children must be black. } /***************************************************************************** * g: Grandfather node * U: uncle node * P: parent node * cur: Insert the new node * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / private void fixedInsert (TreeNode cur) { TreeNode g, u; TreeNode p; while ((p = cur.parent) ! = null && p.color == TreeNode.RED) { g = p.parent; / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * algorithm of left and right 】 【 mirror image ******************************************************/ if (g ! = null) {/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * uncle node and red: * 1. Modify: P & u is black; * 2. Modify: g is red; *************************************************/ u = (p == g.left ? g.right : g.left); if (u ! = null && u.color == TreeNode.RED) { u.color = TreeNode.BLACK; p.color = TreeNode.BLACK; g.color = TreeNode.RED; cur = g; continue; } / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * left subtree is * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / if (p = =  g.left) { /********************************************* * g g g * / / / * p => cur => p * \ / / * cur p cur *********************************************/ if (cur == p.right) { rotateLeft(p); TreeNode temp = cur; cur = p; p = temp; } / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1. 2. The uncle node does not exist. Is NIL leaf nodes are black g p * * * / / \ * p = > cur cur g * / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / p.c olor = TreeNode.BLACK; g.color = TreeNode.RED; rotateRight(g); } else { /********************************************* * g g g * \ \ \ * p => cur => p * / \ \ * cur p cur *********************************************/ if (cur == p.left) { rotateRight(p); TreeNode temp = cur; cur = p; p = temp; } / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1. 2. The uncle node does not exist. The leaf node NIL is black p * * * g \ / cur * \ * \ * p = > g cur * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / p.c olor = TreeNode.BLACK; g.color = TreeNode.RED; rotateLeft(g); Root.color = treenode.black; // The root node must be BLACK; // The root node must be BLACK. }}Copy the code

Github red black tree complete source code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

“Algorithm – Simple to Understand” red black tree insertion

One, foreword