Shulou(Shulou.com)06/01 Report--

This article is to share with you the content of the example analysis of the red-black tree of C++ 's data structure. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Concept and nature

The concept of red-black tree: red-black tree is a binary search tree, but a storage bit is added to each node to represent the color of the node, which can be Red or Black. It controls the relative balance of the tree by controlling the node color, ensuring that no path is twice as long as the others.

The nature of the red-black tree:

The node is red or black.

The root node is black.

All the leaves are black. (leaves are empty nodes)

The two sub-nodes 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 leaf contain the same number of black nodes.

The above five properties can also be described in more popular language as three sentences:

The root node is black

There are no consecutive red nodes

Each path has the same number of black nodes (each path refers to the empty black node from the root node)

Think about it: why is the length of the longest path in a red-black tree not more than twice the number of shortest path nodes?

Longest path: the node distribution on this path is one red and one black.

Shortest path: the node distribution on this path is all black

Assuming that the number of black nodes in each path is N, the longest path is 2N and the shortest path is N, so it is inferred that the length of the longest path in the red-black tree will not exceed twice the number of shortest path nodes.

Implementation of red-black tree definition of red-black tree node

Here is also a trigeminal chain, in which each node contains elements of color:

Enum Color {RED, BLACK}; templatestruct RBTreeNode {RBTreeNode* _ left; RBTreeNode* _ right; RBTreeNode* _ parent; pair _ kv; Color _ color RBTreeNode (const pair& kv, Color color = RED): _ left (nullptr), _ right (nullptr), _ parent (nullptr), _ kv (kv), _ color (color) {}}; Definition of red-black tree structure

It contains only one member variable of the root node, which is not much different from the structural definition of the previous two trees. The difference lies in the definition of the node:

Templateclass RBTree {typedef RBTreeNode Node;public:private: Node* _ root = nullptr;}; Overview of insertion methods for red-black trees

Step 1: let's insert the node according to the binary search tree.

Step 2: in order not to break the rules of the red-black tree, we need to adjust the red-black tree after we insert the node.

Think about it: should we insert nodes by default, red nodes or black nodes? The answer is the red node. Why? We have to consider which way is more destructive to the red-black tree. If it is black, black causes the path to have one more black node than any other path, so the step of adjusting the red-black tree seems to be a little expensive. If it is red, it will not break rule 5, but rule 4, and continuous red nodes may appear, so we only need to adjust the color of the node and its nearby nodes, which is not as expensive as the former way, so we choose the second way.

Adjust node color

The first case: if the father of the inserted node is a black node, it can end directly without further adjustment.

The second case: if the father of the inserted node is a red node, you need to make corresponding adjustments. The following discusses several situations in which the father node is the left child of the grandfather node (in the case of the right child and this type, you can deduce it yourself. Here we call the father node p (parent), grandfather g (grandfather) and uncle node u (uncle):

Case 1: P is red (g must exist and black), u exists and is red

Operation: change p and u to black, g to red, and if g is the root node, change the color of g to black and then end. If g is not the root node and the father of g is black, you need to iteratively adjust upward if it is red. Judge what the situation is at this time with the image:

If g's father is red, iterate upward: cur = grandfather,grandfather = grandfather- > parent

Abstract diagram: the cur in the abstract diagram may be a newly inserted node or an iteratively adjusted node, where g the subtree has the same number of black nodes per path, and the adjusted g subtree has the same number of black nodes per path as before. The left child of cur is the same as the right child of parent, because the color is controlled here, regardless of direction.

Case 2: P is red (g must exist and black), u does not exist

Operation: when cur is the left child of parent, spin g to the right, then change the color of p to black and the color of g to red When cur is the right child of parent, first perform left single spin on p, then right single spin on g, then change the color of cur to black, and the color of g to red: at this time, cur must be a new node, because the right subtree of g has no black node, so it is impossible for cur to have a straight line when the black node cur is the left child of parent.

When cur is the left child of parent, there is a broken line, and there is a double rotation between left and right.

In the second case above, you can first do a left-hand spin, then swap cur and p, change the broken line into a straight line, and finally execute the straight line.

Case 3: P is red (g must exist and black), u exists and is black

Operation: if cur is the left child of parent, spin g to the right, then change the color of p to black and the color of g to red; if cur is the right child of parent, first rotate p and g, then change the color of cur to black and the color of g to red

Explanation: suppose that at this time the number of black nodes in an and b is also the number of black nodes in a cur d and e, that is, the number of black nodes in the abstract graph of an and g is a, and the whole is equal. Abstract diagram: at this time, cur must be the adjusted node, because if it is a new node, then the original g this subtree has a different number of black nodes, so cur must be the adjusted node. Cur is a straight line for the left child of parent, and you can do a right single spin.

Cur is a broken line for the right child of parent, and it rotates left and right at this time.

As in case 2, the second case above can start with a left single spin, then swap cur and p, change the broken line into a straight line, and finally execute the straight line.

Conclusion: the above is all the cases of the left child of p is g, and the right child of g is similar to this. Also note that the root node must eventually be changed to black.

Insert code implementation

The rotation code is as follows: here is the rotation code of the previous blog, as follows

/ / left-handed void RotateL (Node* parent) {Node* subR = parent- > _ right; Node* subRL = subR- > _ left; / / parent right points to subR's left parent- > _ right = subRL; if (subRL) subRL- > _ parent = parent; Node* ppNode = parent- > _ parent; parent- > _ parent = subR; subR- > _ left = parent If (ppNode = = nullptr) {_ root = subR; subR- > _ parent = nullptr;} else {if (ppNode- > _ left = = parent) ppNode- > _ left = subR; else ppNode- > _ right = subR SubR- > _ parent = ppNode;}} / / right-handed void RotateR (Node* parent) {Node* subL = parent- > _ left; Node* subLR = subL- > _ right; / / parent to the right parent- of subL > _ left = subLR; if (subLR) subLR- > _ parent = parent; Node* ppNode = parent- > _ parent; parent- > _ parent = subL SubL- > _ right = parent; if (ppNode = = nullptr) {_ root = subL; subL- > _ parent = nullptr;} else {if (ppNode- > _ left = = parent) ppNode- > _ left = subL Else ppNode- > _ right = subL; subL- > _ parent = ppNode;}}

The insertion code is implemented as follows:

Pair Insert (const pair& kv) {if (_ root = = nullptr) {_ root = new Node (kv, BLACK); / / default to black return make_pair (_ root, true);} Node* cur = _ root; Node* parent = nullptr; while (cur) {parent = cur If (kv.first

_ kv.first) cur = cur- > _ left; else if (kv.first > cur- > _ kv.first) cur = cur- > _ right; else return make_pair (nullptr, false) } / / Node defaults to the red node, resulting in less impact / / the same rule cur = new Node (kv); if (cur- > _ kv.first) will affect the black node of each path

_ kv.first) {parent- > _ left = cur; cur- > _ parent = parent;} else {parent- > _ right = cur; cur- > _ parent = parent } / / adjust color / / case 1: P is red, g is black, u exists and is red / / several cases after adjustment: / / 1. If g is the root node, change the color of g to black, end; / / 2. If g is not the root node and / / a.g 's parent node is black, end / / b.g parent node is red, iteratively adjust upwards, and continue to determine which case (one and three) / / cur = grandfather; / / father = cur- > father / / whether the cur is on the left or right of p, it is the same, concerned about the color rather than the position / / case 2: P is red, g is black, u is black / u is black three are a straight line / / adjustment method (left as an example): 1. Right single spin 2. Change p to black, g to red / a. U does not exist, cur must be a new node / b. U exists, cur must be updated node / / case 3: P is red, g is black, u is black cur p g three is a broken line / / adjustment method (for example on the left): 1.p left single spin 2.g right single spin 3. / / left if (grandfather- > _ left = = parent) {/ / Red and black conditions depend on Uncle Node* uncle = grandfather- > _ right / / u exists and is red if (uncle & & uncle- > _ color = = RED) {/ / adjust p and u to black, g to red parent- > _ color = uncle- > _ color = BLACK Grandfather- > _ color = RED; / / iterative upward adjustment cur = grandfather; parent = cur- > _ parent } else// u is black / u there is no {/ / broken line with a left-handed processing 1.p left-handed 2.g right-handed 3. Change cur to black, g to red cur p g three is a broken line if (cur = = parent- > _ right) {RotateL (parent); swap (parent, cur) } / / straight line cur p g changes p to black, g to red / / right-handed single spin may be the third case RotateR (grandfather); parent- > _ color = BLACK Grandfather- > _ color = RED;}} / / uncle is on the left else {Node* uncle = grandfather- > _ left If (uncle & & uncle- > _ color = = RED) {parent- > _ color = uncle- > _ color = BLACK; grandfather- > _ color = RED / / iterative upward adjustment cur = grandfather; parent = cur- > _ parent } else {/ / broken line uses a right-hand single spin to deal with g p cur g turning red p-edge black if (cur = = parent- > _ left) {RotateR (parent) Swap (parent, cur);} / straight line g p cur changes p to black, g to red / / left-handed single spin may be the third case RotateL (grandfather) Parent- > _ color = BLACK; grandfather- > _ color = RED;} _ root- > _ color = BLACK; return Find (kv.first); Overview of deletion methods for red-black trees

Step 1: first find the node to be deleted (or an alternative node) according to the binary search tree to delete the node.

Step 2: then, in order not to break several rules of the red-black tree, adjust the color of the nodes accordingly

Adjust the color

The first case: delete the node (or it may be an alternative node) (later called delNode). If the node is red, you can delete and exit directly. If delNode can't find it, you can exit directly.

The second case: delNode is black (there is only one child and red at most, because the replacement node has at most one child). When delNode has one child, delete the delNode node, and then change the color of the child node to black, or you can end directly.

The third situation: when delNode is black and has no children, there are the following situations (brother node is called b (brother), father node is called p (parent)) (below is the case of the left child of parent, and the situation of the right child is similar to it, not introduced):

Case 1: P is black, b is red, two children exist and must be black

Operation: make a left single spin on p, then change the color of p to red, and the color of b to black

Analysis: before the adjustment, the black nodes of the abstract triangle are all a, because there is a node under the cur to be deleted, so a black node is missing under the cur, that is, a black node is missing on the left side of p, and the number of black nodes on both sides of the adjusted b remains unchanged. The number of black nodes under the cur is still missing, but its brother is a black node, which can be retrieved later by cur. Use other situations to solve this problem.

Abstract diagram:

Case 2: P is red, b is black, and the two children of b exist and must be black

Operation: change the color of p to black and b to red

Analysis: before adjustment, a black node is missing on the left side of p. After adjustment, a black node is added on the left side of p, and the number of black nodes on the right side of p remains the same. It can end here.

Abstract diagram:

Case 3: P is black and b is black, and b's two children are black

Operation: change the color of b to red

Analysis: before adjustment, there is a lack of a black node on the left side of p. After adjustment, the number of black nodes on both sides is the same, but at this time, the right side of p is also missing a black node. At this time, the right side of p's father, GMagee g, has one more black node than the left, so you need to iteratively adjust upwards to change cur into p, and continue to search cur.

Abstract diagram:

Case 4: P is any color, b is black, and the right child of b is red.

Operation: make a left single spin on p, then exchange the colors of p and b, and change the color of b to black

Analysis: before the adjustment, the number of black nodes of both an and b is xquo1, that is, there is a black node missing on the left side of p, after adjustment, the black nodes on both sides of p are xtransi1, and the black nodes on both sides of b are xtransi2, so it can end here.

Abstract diagram:

Case 5: P is any color, b is black, and b's left child is red.

Operation: first right single spin b, then change b to red, bL to black, then left single spin to p, then exchange the colors of p and b, and change the color of b to black (case 4)

Analysis: it is the same as case 4. The b and bR of case 4 are straight lines, and here is the broken line, which is transformed into a straight line by right-hand single rotation, and then converted to case 4.

Abstract diagram:

Summary: deletion is the above cases, generally, one black node is missing on the left, one is added on the right, the end, or one is reduced on the right, and then one is missing on both sides as a whole, and the father node is searched.

Delete code implementation

The code is implemented as follows:

Bool Erase (const K & key) {/ / if the tree is empty, delete failed if (_ root = = nullptr) return false; Node* parent = nullptr; Node* cur = _ root; Node* delNode = nullptr; Node* delNodeParent = nullptr; while (cur) {/ / less than if to the left (key)

_ kv.first) {cur = cur- > _ left;} / / greater than going right else if (key > cur- > _ kv.first) {cur = cur- > _ right } else {/ / found return true;}} return false;} verification of red-black tree

Here, we compare the number of nodes in each path by recursively calculating the number of nodes in each path, and verify whether other properties match, so as to verify whether it is a red-black tree:

Bool IsValidRBTree () {/ / empty tree is also a red-black tree if (_ root = = nullptr) return true; / / determine whether the root node is black if (_ root- > _ color! = BLACK) {cout _ left } / / check whether the number of black nodes in each path is the same. The second parameter records the number of black nodes in the path return _ IsValidRBTree (_ root, 0, blackCount). } bool _ IsValidRBTree (Node* root, size_t k, size_t blackCount) {/ / go empty to determine whether the black node of the path is equal to blackCount if (root = = nullptr) {if (k! = blackCount) {cout _ parent If (parent & & root- > _ color = = RED & parent- > _ color = = RED) {cout _ right, k, blackCount);}

Example demonstration:

Void TestRBTree () {/ / srand ((size_t) time (nullptr)); RBTree rbt; / / int a [] = {1, 2, 4, 4, 5, 5, 5, 7, 10, 5, 5, 10, 5, 5, 10, 5, 5, 10, 5, 5, 10, 5, 5, 10, 10, 5, 10, 10, 10, 5, 5, 10, 10, 10, 10, 5, 5, 10, 10, 5, 5, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 6, 6, 6, 7, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 7, 6, 6, 6, 6, 7, 6, 6, 6, 7, 6, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 10, 14, 14, 14, 14, 10, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, For (size_t I = 0; I < 13; + + I) {/ / a.push_back (rand ()); a.push_back (I);} / / int a [] = {4 vector 2, 6, 7, 3, 5}; / * vector v; v.reserve (100000); for (size_t I = 1; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.