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

This article mainly introduces the example analysis of the simulation implementation of the red-black tree in the C++ STL container, which has a certain reference value, and interested friends can refer to it. I hope you can learn a lot after reading this article.

I. the concept of red-black tree

Red-black tree (Red Black Tree), a data structure used in computer science, 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. By limiting the way nodes are colored on any path from root to leaf, the red-black tree ensures that no path is twice as long as the others, so it is nearly balanced.

Second, the nature of the red-black tree

1. Every node is either red or black.

two。 The root node is black

3. If a node is red, its two children are black.

4. For each node, the simple path from this node to all its descendant leaf nodes contains the same number of black nodes.

5. Each leaf node is black (here the leaf node refers to the empty node)

If the above properties are satisfied, the red-black tree can guarantee that the number of nodes in the longest path will not exceed twice that of the shortest path.

III. Definition of red-black tree enum Colour / / Red-black tree color enumeration {RED, BLACK,}; templatestruct RBTreeNode / / node structure {RBTreeNode* _ left; / / left subtree RBTreeNode* _ right; / / right subtree RBTreeNode* _ parent / / parent node pair _ kv; Colour _ col; RBTreeNode (const pair& kv) / / constructor: _ left (nullptr), _ right (nullptr), _ parent (nullptr), _ kv (kv), _ col (RED) {}}

When inserting, the default is red, because red may break rule 3, and black must break rule 4, so it defaults to red.

IV. Red-black tree structure

In order to make the correlation container simple, a header node is added in the implementation of the red-black tree, because the following node must be black. In order to distinguish it from the root node, give the header node black, and let the parent domain of the header node point to the root node of the red-black tree, the left domain points to the smallest node in the red-black tree, and the Rightfield points to the largest node in the red-black tree, as shown below:

Fifth, the insertion operation of red-black tree

The red-black tree adds its balance constraint to the binary search tree, so the insertion of the red-black tree can be divided into two steps:

1. Insert a new node according to the tree rule of binary search:

Pair Insert (const pair& kv) {if (_ root = = nullptr) {_ root = new Node (kv); _ root- > _ col = BLACK; return make_pair (_ root, true);} Node* parent = nullptr Node* cur = _ root; while (cur) {if (cur- > _ kv.first > kv.first) {parent = cur; cur = cur- > _ left } else if (cur- > _ kv.first)

< kv.first) { parent = cur; cur = cur->

< key) { cur = cur->

_ right;} else {return cur;}} return nullptr } pair Insert (const pair& kv) {if (_ root = = nullptr) {_ root = new Node (kv); _ root- > _ col = BLACK; return make_pair (_ root, true) } Node* parent = nullptr; Node* cur = _ root; while (cur) {if (cur- > _ kv.first > kv.first) {parent = cur Cur = cur- > _ left;} else if (cur- > _ kv.first

< kv.first) { parent = cur; cur = cur->

_ right;} else {return make_pair (cur, false);}} Node* newNode = newNode (kv); newNode- > _ col = RED If (parent- > _ kv.first > kv.first) {parent- > _ left = newNode; newNode- > _ parent = parent;} else {parent- > _ right = newNode NewNode- > _ parent = parent;} cur = newNode; while (parent & & parent- > _ col = = RED) / / violation of rule three {Node* grandfather = parent- > _ parent If (parent = = grandfather- > _ left) / / left side {Node* uncle = parent- > _ right If (uncle & & uncle- > _ col = = red) / / case 1 {uncle- > _ col = BLACK; grandfather- > _ col = RED Parent- > _ col = BLACK; cur = grandfather; / / iterative parent = cur- > _ parent } else / / case 2.3 {if (cur = = parent- > _ left) / / unilateral {RotateR (grandfather) Grandfather- > _ col = RED; parent- > _ col = BLACK } else / / fold {RotateL (parent) RotateR (grandfather); cur- > _ col = BLACK; grandfather- > _ col = RED } break / / No change in the number of black, no need to go up}} else / / parent = = grandfather- > _ right {Node* uncle = parent- > _ left If (uncle & & uncle- > _ col = = red) / / case 1 {uncle- > _ col = BLACK; grandfather- > _ col = RED Parent- > _ col = BLACK; cur = grandfather; / / iterative parent = cur- > _ parent } else / / case 2.3 {if (cur = = parent- > _ right) / / unilateral {RotateL (grandfather) Grandfather- > _ col = RED; parent- > _ col = BLACK } else / / fold {RotateR (parent) RotateL (grandfather); cur- > _ col = BLACK; grandfather- > _ col = RED } break;}} _ root- > _ col = BLACK / / change the root to black return make_pair (newNode, true) again at the end of insertion;}} Thank you for reading this article carefully. I hope the article "sample Analysis of partial Simulation of Red and Black trees in C++ STL Container" shared by the editor will be helpful to you. At the same time, I also hope you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

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.