Red-black tree realization

Red-black tree realization

table of Contents

1. Red-black tree principle

In order to prevent the binary search tree from degenerating into a linked list, a self-balanced binary search tree appears.
AVL tree: Balanced binary tree, the difference between the height of its left and right subtrees is not more than 1, but it is too ideal.
The red-black tree is selected through comprehensive consideration of performance.

1. The nature of red and black trees

1. Each node is either red or black.
2. It is impossible to have red nodes connected together.
3. The root node is all black.
4. The two sub-nodes of each red node are all black.
5. The leaf nodes are all black (leaf nodes refer to NULL nodes)
6. All paths from a node to the descendants of the node contain the same number of black nodes.

2. Transformation rules (from the perspective of inserting nodes)

There are three types of transformation rules:

Discoloration, left-handed, right-handed

1. Discoloration

The premise of the color change: the parent node of the current node is red, and the other node of its grandfather node == (uncle node) is also red ==.
The process of discoloration:

1. Set the parent node to black
2. Set the uncle node to black
3. Set the grandfather node to red
4. Set the pointer to the grandfather node as the node to be operated currently.
5. Continue to analyze and judge

The example is as follows:
Insert the corresponding node 6 according to the rules of the binary search tree; it is found that the rule is violated, and the two red ones are connected together, and meet the premise of changing the color, so the color is changed

Figure 1 Insert node 6 as the current nodeFigure 2 After the color transformation is completed, the previous grandfather node is used as the current node

2. Left hand

Observing the tree after the discoloration, it is still a violation of the rules: 5 and 12 red are connected together.
Then look at whether it meets the prerequisite of discoloration: Obviously it does not, because the uncle node 30 of 12 is not red. Then it is time to judge whether the premise of left-handedness is met.
The premise of left-handed rotation: when the
current parent node is red, and the uncle is black, and the current node is the right subtree.
The process of left-handedness:

Rotating with the parent node as the center, the dynamic graph is as follows:
1. Connect the current subtree (between E and S) with the current node as the root node to the
larger node of the grandfather node E 2, E and S Move to the root node as

Comparison before and after left rotation:

Figure 1 Left-handed anteriorFigure 2 Left-handed

3. Right-handed

Observing the left-handed tree, it is still a violation of the rules: the two red nodes 5 and 12 are connected together. And does not meet the conditions for discoloration and left-handedness.
Then right
- handed right - handed conditions are used next : the
current parent node is red, the uncle node is black, and the current node is the left subtree.
Right-hand operation:

1. Change the parent node to black
2. Change the grandfather node to red
3. Rotate with the grandfather node

Right-handed comparison before and after; 13 reconnect.

Figure 1 Right-handed prerotationFigure 2 Right-handed

3. Points to note when deleting nodes

1, the red-black tree as a binary search tree, the node is deleted from the binary search tree
2, tree is corrected by rotating and discoloration of operation, making it again become a red-black tree
on binary Deleting nodes in the search tree is not the focus of this note. You can refer to my previous rewriting notes, which is still more useful:

Insertion, deletion, pruning, and construction operations of binary search tree (leetcode701, 450, 669, 108)

If you are afraid of trouble, you can also directly look at the screenshot below:

2. Code

1. Define nodes and constructors

Each node has a color and value, left and right children and pointers to the parent node.
Define a constructor with parameters

template < class T > class RBTNode { public : RBTColor color; //Color T key; //Keyword (key value) RBTNode *left; //Left child RBTNode *right; //Right child RBTNode *parent; //Parent node RBTNode (T value, RBTColor c, RBTNode *p, RBTNode *l, RBTNode *r): key (value), color (c), parent (), left (l), right (r) () }; Copy code

2. Define the red-black tree class and the method of declaring it

Every tree has a root node and an empty node

template < class T > class RBTree { private : RBTNode<T> *mRoot; // Root node public : RBTree (); ~ RBTree (); // Preorder traversal "red and black trees" void preOrder () ; //Middle order traversal of "red and black trees" void inOrder () ; //Post order traversal of "red and black trees" void postOrder () ; //(Recursive implementation) Find the node with the key value in the "Red-Black Tree" RBTNode<T>* search (T key) ; //(Non-recursive implementation) Find the node with the key value in the "Red-Black Tree" RBTNode<T>* iterativeSearch (T key) ; //Find the smallest node: return the key value of the smallest node. T minimum () ; //Find the largest node: return the key value of the largest node. T maximum () ; //Find the successor node of node (x). That is, find the "minimum node" in which the data value in the red-black tree is greater than the node. RBTNode<T>* successor (RBTNode<T> *x) ; //Find the predecessor node of node (x). That is, find the "maximum node" whose data value in the red-black tree is less than the node. RBTNode<T>* predecessor (RBTNode<T> *x) ; //Insert the node (key is the node key value) into the red-black tree void insert (T key) ; //Delete the node (key is the key value of the node) void remove (T key) ; //Destroy the red-black tree void destroy () ; //Print the red-black tree void print () ; private : //traverse the "red-black tree" in preorder void preOrder (RBTNode<T>* tree) const ; //traverse the "red-black tree" in the middle order void inOrder (RBTNode< T>* tree) const ; //Traverse the "red-black tree" in postorder void postOrder (RBTNode<T>* tree) const ; //(Recursive implementation) Find the node whose key value is key in "Red-Black Tree x" RBTNode<T>* search (RBTNode<T>* x, T key) const ; //(Non-recursive implementation) Find "red-black" The node whose key value is key in the tree "x" RBTNode<T>* iterativeSearch (RBTNode<T>* x, T key) const ; //Find the smallest node: return the smallest node of the red-black tree whose root node is tree. RBTNode<T>* minimum (RBTNode<T>* tree) ; //Find the largest node: return the largest node of the red-black tree with tree as the root node. RBTNode<T>* maximum (RBTNode<T>* tree) ; //Left-handed void leftRotate (RBTNode<T>* &root, RBTNode<T>* x) ; //Right-handed void rightRotate (RBTNode<T>* &root, RBTNode<T>* y) ; //Insert function void insert ( RBTNode<T>* &root, RBTNode<T>* node) ; //insert correction function void insertFixUp (RBTNode<T>* &root, RBTNode<T>* node) ; //delete function void remove (RBTNode<T>* &root, RBTNode<T> *node) ; //Delete the correction function void removeFixUp (RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent) ; //Destroy the red-black tree void destroy (RBTNode<T>* &tree) ; //Print the red-black tree void print (RBTNode<T>* tree, T key, int direction) ; # define rb_parent(r) ((r)->parent) # define rb_color(r) ((r)->color) # define rb_is_red(r) ((r)->color==RED) # define rb_is_black(r ) ((r)->color==BLACK) # define rb_set_black(r) do {(r)->color = BLACK;} while (0) # define rb_set_red(r) do {(r)->color = RED ;} while (0) # define rb_set_parent(r,p) do {(r)->parent = (p);} while (0) # define rb_set_color(r,c) do {(r)->color = ( c);} while (0) }; Copy code

3. Left-handed

/* * Rotate the node (x) of the red-black tree to the left * * Left-handed schematic diagram (left-handed node x): * px px *// * xy *//--(Left-handed) -->//# * lx yx ry *//// * ly ry lx ly * * */ template < class T > void RBTree<T>:: leftRotate (RBTNode<T>* &root, RBTNode<T>* x) { //Set the right child of x to y RBTNode<T> *y = x->right; //Set "y's left child" to "x's right child"; //if y's left child is not empty, set "x" to "y's left child's father" x->right = y->left; if (y->left != NULL ) y->left->parent = x; //Set "x's father" to "y's father" y->parent = x->parent; if (x->parent == NULL ) { root = y; //If "father of x" is an empty node, set y as the root node } else { if (x->parent->left == x) x->parent->left = y; //If x is the left child of its parent node, set y to "the left child of the parent node of x " else x->parent->right = y; //if x is the left child of its parent node, then set y to "the left child of the parent node of x" } //Set "x" to "y's left child" y->left = x; //Set the "parent node of x" to "y" x->parent = y; } Copy code

4. Right-handed

/* * Rotate the node (y) of the red-black tree to the right * * Right-handed schematic diagram (left-handed node y): * py py *// * yx *//--(Right rotation) -->//# * x ry lx y *////# * lx rx rx ry * */ template < class T > void RBTree<T>:: rightRotate (RBTNode<T>* &root, RBTNode<T>* y) { //Set x to be the left child of the current node. RBTNode<T> *x = y->left; //Set "x's right child" to "y's left child"; //if "x's right child" is not empty, set "y" to "x's right child's father" y->left = x->right; if (x->right != NULL ) x->right->parent = y; //Set "y's father" to "x's father" x->parent = y->parent; if (y->parent == NULL ) { root = x; //If "father of y" is an empty node, set x as the root node } else { if (y == y->parent->right) y->parent->right = x; //If y is the right child of its parent node, set x to "the right child of y's parent node" else y->parent->left = x; //( y is the left child of its parent node) Set x to "the left child of the parent node of x" } //Set "y" to "x's right child" x->right = y; //Set the "parent node of y" to "x" y->parent = x; } Copy code

5. Insert operation

Internal interface-insert(root, node) is used to insert the "node" node into the red-black tree. Among them, root is the root and node is the inserted node.
External interface-The function of insert(key) is to add "key" to the red-black tree.

/* * Insert the node into the red-black tree * * Parameter Description: * root The root node of the red-black tree * The node inserted by node//corresponds to the node in "Introduction to Algorithms" */ template < class T > void RBTree<T>:: insert (RBTNode<T>* &root, RBTNode<T>* node) { RBTNode<T> *y = NULL ; RBTNode<T> *x = root; //1. Treat the red-black tree as a binary search tree and add nodes to the binary search tree. while (x != NULL ) { y = x; if (node->key <x->key) x = x->left; else x = x->right; } node->parent = y; if (y!= NULL ) { if (node->key <y->key) y->left = node; else y->right = node; } else root = node; //2. Set the color of the node to red node->color = RED; //3. Re-correct it to a binary search tree insertFixUp (root, node); } /* * Insert the node (key is the node key value) into the red-black tree * * Parameter Description: * tree The root node of the red-black tree * key insert the key value of the node */ template < class T > void RBTree<T>:: insert (T key) { RBTNode<T> *z = NULL ; //If the new node fails, return. if ((z = new RBTNode<T>(key,BLACK, NULL , NULL , NULL )) == NULL ) return ; insert (mRoot, z); } Copy code

6. Correction operation

According to the conditions, perform the color change, left-handed, and right-handed operations, and finally set the root node to black.
Whether the uncle node is the left child or the right child of the parent node of the group needs to be discussed separately.
For the specific steps of the operation, you can return to the above comparison to see.
The role of insertFixUp(root, node) is to correspond to "the third step mentioned above". It is an internal interface.

/* * Red-black tree insertion correction function * * After inserting the node into the red-black tree (out of balance), call this function again; * The purpose is to reshape it into a red-black tree. * * Parameter Description: * root the root of the red-black tree * The node inserted by node//corresponds to z in "Introduction to Algorithms" */ template < class T > void RBTree<T>:: insertFixUp (RBTNode<T>* &root, RBTNode<T>* node) { RBTNode<T> *parent, *gparent; //If "the parent node exists, and the color of the parent node is red" while ((parent = rb_parent (node)) && rb_is_red (parent)) { gparent = rb_parent (parent); //If the "parent node" is the "left child of the grandfather node" if (parent == gparent->left) { RBTNode<T> *uncle = gparent->right; //Case 1 condition: the uncle node is red, and the color change is used at this time if (uncle && rb_is_red (uncle)) { rb_set_black (uncle); rb_set_black (parent); rb_set_red (gparent); node = gparent; continue ; } //Case 2 condition: the uncle is black, and the current node is the right child, then use left-handed if (parent->right == node) { RBTNode<T> *tmp; leftRotate (root, parent); tmp = parent; parent = node; node = tmp; } //Case 3 conditions: Uncle is black, and the current node is the left child, then right-handed rb_set_black (parent); rb_set_red (gparent); rightRotate (root, gparent); } else //If "parent node of z" is "right child of grandparent node of z" { RBTNode<T> *uncle = gparent->left; //Case 1 if (uncle && rb_is_red(uncle)) { rb_set_black(uncle); rb_set_black(parent); rb_set_red(gparent); node = gparent; continue; } //Case 2 if (parent->left == node) { RBTNode<T> *tmp; rightRotate(root, parent); tmp = parent; parent = node; node = tmp; } //Case 3 rb_set_black(parent); rb_set_red(gparent); leftRotate(root, gparent); } } // rb_set_black(root); }

7

" "

3

1 - C++
2 leetcode ( B
3 B ,
4
5 leetcode701 450 669 108
6 ( )