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

This article will explain in detail the example analysis of the red-black tree in C++. The editor thinks it is very practical, so I share it with you for reference. I hope you can get something after reading this article.

The concept of red-black tree

The concept of a red-black tree a 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. 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.

Red-black tree and AVL tree are both efficient balanced binary trees, and the time complexity of adding, deleting and checking is O (). Red-black trees do not pursue absolute balance, they only need to ensure that the longest path does not exceed 2 times of the shortest path, relatively speaking, it reduces the number of insertions and rotations, so the performance is better than AVL trees in the structure of frequent additions and deletions, and the realization of red-black trees is relatively simple, so there are more red-black trees in practical application.

The properties of red-black trees

Every node is either red or black.

The root node is black

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

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

Each leaf node is black (the leaf node here refers to the empty node, as in the figure above, the number of paths is 11)

Definition of red-black tree node enum Color {BLACK, RED}; templatestruct RBTreeNode {RBTreeNode* _ left; RBTreeNode* _ right; RBTreeNode* _ parent; Color _ col; T _ data RBTreeNode (const T & data): _ left (nullptr), _ right (nullptr), _ parent (nullptr), _ col (RED), _ data (data) {}}; insert operation of red-black tree

Convention: cur is the current node, p is the parent node, g is the grandfather node, u is the uncle node

Situation one

Case 1: cur is red, p is red, g is black, u exists and is red Note: the tree seen here may be a complete tree or a subtree

Solution: change pforce u to black, g to red, and then treat g as cur and continue to adjust upward

If g is the root node, you need to change g to black after the adjustment is completed.

If g is a subtree, g must have parents, and if g's parents are red, they need to continue to adjust upward.

Case two

Case 2: cur is red, p is red, g is black, u does not exist / u is black

The solution: the left child of p is g, the left child of cur is p, the right child of p is g, and the right child of cur is p, then do left single rotation.

P turns black and g turns red.

1. If the u node does not exist, then cur must be a newly inserted node, because if cur is not a newly inserted node, then one node of cur and p must be black, which does not satisfy property 4: there are the same number of black nodes in each path.

two。 If the u node exists, it must be black, and cur must not be a new node, then the original color of the cur node must be black, which is changed from the first situation as the grandfather of the subtree.

Situation three

Case 3: cur is red, p is red, g is black, u does not exist / u is black (broken line)

If p is the left child of g and cur is the right child of p, then make a single left rotation for p.

If p is the right child of g and cur is the left child of p, then make a right single rotation for p.

That is, it is converted to case two. And then do it to g for rotation. That is, double rotation.

/ / T-> K set// T-> pair maptemplateclass RBTree {typedef RBTreeNode Node;public: typedef RBTreeIterator iterator; typedef RBTreeIterator const_iterator; iterator begin (); iterator end (); RBTree (): _ root (nullptr) {} / / copy construction and assignment overload / / destruct Node* Find (const K & key) Pair Insert (const T & data) {if (_ root = = nullptr) {_ root = new Node (data); _ root- > _ col = BLACK; return make_pair (iterator (_ root), true);} Node* parent = nullptr Node* cur = _ root; KeyOfT kot; while (cur) {if (kot (cur- > _ data))

< kot(data)) { parent = cur; cur = cur->

_ right;} else if (kot (cur- > _ data) > kot (data)) {parent = cur; cur = cur- > _ left } else {return make_pair (iterator (cur), false) }} / / A new node with a red color may break rule 3, resulting in a continuous red node cur = new Node (data); Node* newnode = cur; cur- > _ col = RED; if (kot (parent- > _ data)

< kot(data)) { parent->

_ right = cur; cur- > _ parent = parent;} else {parent- > _ left = cur; cur- > _ parent = parent } / / Control approximate equilibrium while (parent & & parent- > _ col = = RED) {Node* grandfather = parent- > _ parent If (parent = = grandfather- > _ left) {Node* uncle = grandfather- > _ right / / case 1: uncle exists and is red, perform discoloration processing, and continue to update the processing if (uncle & & uncle- > _ col = = RED) {parent- > _ col = uncle- > _ col = BLACK Grandfather- > _ col = RED; cur = grandfather; parent = cur- > _ parent } / / case 2 + 3: uncle does not exist, or exists and is black Need rotation + discoloration processing else {/ / case 2: single spin + discoloration if (cur = = parent- > _ left) {RotateR (grandfather) Parent- > _ col = BLACK; grandfather- > _ col = RED } else / / case 3: double spin + discoloration {RotateL (parent) RotateR (grandfather); cur- > _ col = BLACK; grandfather- > _ col = RED } break }} else / / (parent = = grandfather- > _ right) {Node* uncle = grandfather- > _ left If (uncle & & uncle- > _ col = = RED) {parent- > _ col = uncle- > _ col = BLACK; grandfather- > _ col = RED; cur = grandfather Parent = cur- > _ parent } else {if (parent- > _ right = = cur) {RotateL (grandfather) Parent- > _ col = BLACK; grandfather- > _ col = RED } else {RotateR (parent); RotateL (grandfather) Cur- > _ col = BLACK; grandfather- > _ col = RED;} break }} _ root- > _ col = BLACK; return make_pair (iterator (newnode), true);} void RotateR (Node* parent); void RotateL (Node* parent); private: Node* _ root;}; Verification of red and black trees

The detection of red-black trees is divided into two steps:

Check whether it satisfies the binary search tree (whether the mid-order traversal is an ordered sequence)

Test whether it satisfies the properties of a red-black tree.

Unmodified red-black trees are used here.

Templatestruct RBTreeNode {RBTreeNode* _ left; RBTreeNode* _ right; RBTreeNode* _ parent; Colour _ col; pair _ kv RBTreeNode (const pair& kv): _ left (nullptr), _ right (nullptr), _ parent (nullptr), _ col (RED), _ kv (kv) {}}; templateclass RBTree {typedef RBTreeNode Node Public: RBTree (): _ root (nullptr) {} bool Insert (const pair& kv); void RotateR (Node* parent); void RotateL (Node* parent); void _ InOrder (Node* root) {if (root = = nullptr) {return } _ InOrder (root- > _ left); cout_ kv.first _ right);} void InOrder () {_ InOrder (_ root); cout_parent- > _ col = = RED) {cout_ right) } / / check the number of black nodes in each path bool CheckBlackNum (Node* cur, int blackNum, int benchmark) {if (cur = = nullptr) {if (blackNum! = benchmark) {cout _ left, blackNum, benchmark) & & CheckBlackNum (cur- > _ right, blackNum, benchmark) } bool IsBalance () {if (_ root = = nullptr) {return true;} if (_ root- > _ col = = RED) {cout _ left;} int blackNum = 0 Return CheckRED_RED (_ root) & & CheckBlackNum (_ root, blackNum, benchmark);} private: Node* _ root;}; void TestRBTree1 () {const int n = 1000000; vector a; a.reserve (n); srand (time (0)); for (size_t I = 0; I

< n; ++i) { a.push_back(rand()); } RBTree t1; for (auto e : a) { t1.Insert(make_pair(e, e)); } cout _left; } //return left return iterator(left); } iterator end() { return iterator(nullptr); } 操作符重载 templatestruct RBTreeIterator{ typedef RBTreeNode Node; typedef RBTreeIterator Self; Node* _node; RBTreeIterator(Node* node = nullptr) :_node(node) {} Ref operator*() { return _node->

_ data;} Ptr operator- > () {return & _ node- > _ data;} Self& operator-- () {/ / with + + is basically the other way around return * this } Self& operator++ () {if (_ node- > _ right) {/ / the first node in the right subtree, that is, the leftmost node of the right subtree Node* subLeft = _ node- > _ right While (subLeft- > _ left) {subLeft = subLeft- > _ left;} _ node = subLeft } else {/ / the current subtree has been visited. To find the ancestor to visit, go up the path to the root node, / / find the father node whose child is the father's left Node* cur = _ node Node* parent = cur- > _ parent; while (parent & & parent- > _ right = = cur) {cur = parent; parent = parent- > _ parent } _ node = parent;} return * this;} bool operators = (const Self& s) const {return _ node! = s._node } bool operator== (const Self& s) const {return _ node = = s.roomnode;}}; encapsulate map#pragma once#include "RBTree.h" namespace MyMap {template

< class K, class V>

Class map {struct MapKeyOfT {const K & operator () (const pair& kv) {return kv.first;}}; public: typedef typename RBTree::iterator iterator Iterator begin () {return _ t.begin ();} iterator end () {return _ t.end () } pair insert (const pair& kv) {return _ t.Insert (kv);} V & operator [] (const K & key) {pair ret = _ t.Insert (make_pair (key, V () Return ret.first- > second;} private: RBTree _ t;}; void test_map () {map dict; dict.insert (make_pair ("sort", "sort")) Dict.insert (make_pair ("string", "string"); dict.insert (make_pair ("debug", "finding bugs"); dict.insert (make_pair ("set", "set")); map::iterator it = dict.begin () While (it! = dict.end ()) {cout first

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.