[Data Structure] Red Black Tree

The red-black tree is a binary search tree. It adds a storage bit to each node to indicate the color of the node, which can be red or It can be black. By constraining the color of any simple path from the root to the leaf, the red-black tree ensures that the longest path does not exceed twice the shortest path, so it is approximately balanced.

The red-black tree meets the following properties

1. Each node, either red or black
2. The root node is black
3. If a node is red, its two child nodes are black
4. For each node, the simple path from the node to all its descendant leaf nodes contains the same number
5. Each leaf node is black (the leaf node here refers to the NULL node (empty node) )

Insertion analysis of red-black tree

cur represents the current node, P is the parent node, g is the grandfather node, and u is the uncle node

1 , The first case

cur is red, p is red, g is black, u exists and is red
then p, u are changed to black, g is changed to red, and then g is regarded as cur, and continue to adjust upwards.

2 , The second case

cur is red, p is red, g is black, u does not exist/u is black
If p is the left child of g, and cur is the left child of p, then a single right rotation is performed; on the contrary, if p is the right child of g and cur is the right child of p, then a single left rotation is performed

< p>p, g change color–p turns black, g turns red

3 . The third case
cur is red, p is red, g is black, u does not exist/u is black
p is the left child of g, and cur is the right child of p, then do a left order for p Rotation; On the contrary, if p is the right child of g and cur is the left child of p, then a right single rotation is performed for p, which is converted to case 2

Another

Code

RBtree.h

#include#includeusing namespace std;enum Colour{ RED , BLACK,};templatestruct RBtreeNode{ RBtreeNode* _left; RBtreeNode* _right; RBtreeNode* _parent; K _key; V _value; Colour _col; RBtreeNode(const K& key,const V& value) :_left(NULL) ,_right(NULL) ,_parent(NULL) ,_key(key) ,_value(value) ,_col(RED) ());templateclass RBtree{ typedef RBtreeNode Node;public: RBtree() :_root(NULL) {} ~RBtree() {} bool Insert(const K& key,const V& vlaue) {if(_root==NULL) {_root=new Node(key,vlaue); _root->_col=BLACK; return true;} Node* cur=_root; Node * parent=NULL; while (cur) {if(cur->_key>key) {parent=cur; cur=cur->_left;} else if(cur->_key_right;} else return false;} cur=new Node(key,vlaue); if (parent->_key>key) {parent->_left=cur; cur->_parent=parent;} else {parent-> _right=cur; cur->_parent=parent;} while (cur!=_root&&parent->_col==RED) {Node* grandfather=parent->_parent; if(parent==grandfather->_left)//1, parent The node is the left child of the grandparent node {Node* uncle=grandfather->_right; if (uncle&&uncle->_col==RED) {//In the first case, the current node cur is red, and the parent node is red, //There is an uncle The node is red, and the grandfather node is red parent->_col=uncle->_col=BLACK; grandfather->_col=RED; cur=grandfather; parent=cur->_parent;} //else if(uncle==NULL| |uncle->_col==BLACK) else {//In the second case, the uncle node does not exist //In the third case, the uncle node exists and is black if(c ur==parent->_right) {_RotatoL(parent); swap(parent,cur);} _RotatoR(grandfather); parent->_col=BLACK; grandfather->_col=RED; cur=parent; parent=cur-> _parent;}} else if (parent==grandfather->_right)//2, the parent node is the right child of the grandfather node {Node* uncle=grandfather->_left; if (uncle&&uncle->_col==RED) {// In the first case, the current node cur is red, the parent node is red, //there is an uncle node and it is red, and the grandfather node is red parent->_col=uncle->_col=BLACK; grandfather->_col=RED; /* grandfather=cur; cur->_parent=parent;*/ cur=grandfather; parent=cur->_parent;} //else if(uncle==NULL||uncle->_col==BLACK) else {//Second In this case, the uncle node does not exist //The third case, the uncle node exists and is black if(cur==parent->_left) {_RotatoR(parent); swap(cur,parent);} _RotatoL(grandfather); parent ->_col=BLACK; grandfather->_col=RED; cur=parent; parent=cur->_parent;}}} _root->_col=BLACK; return true;} void Inorder() {_Inorder(_root);} bool IsBalance() {if( _root==NULL) return true; int count=0;//Define the black node tree on a road as the number of black nodes to determine the number Node* cur=_root; while(cur) {if(cur->_col==BLACK) count++ ; cur=cur->_left;} int BlackCount=0; return _IsBlance(_root,count,BlackCount);//Recursively judge whether the number of black nodes on each path is correct }protected: void _RotatoL(Node* parent) {Node* subR=parent->_right; Node* subRL=subR->_left; Node* ppNode=parent->_parent; parent->_right=subRL; if(subRL) subRL->_parent=parent; subR->_left=parent; if(ppNode==NULL) {_root=subR; subR->_parent=NULL;} else if(ppNode->_left==parent) {ppNode->_left=subR; subR->_parent=ppNode;} else {ppNode ->_right=subR; subR->_parent=ppNode;}} void _RotatoR(Node* parent) {Node* subL=parent->_left; Node* subLR=subL->_right; Node* ppNode=parent->_parent; parent->_left=subLR; if(subLR) subLR->_parent=parent; subL->_right=parent; if(ppNode==NULL) {_root=subL; subL->_parent=NULL;} else if(ppNode- >_left==parent) {ppNode->_left=subL; subL->_parent=ppNo de;} else {ppNode->_right=subL; subL->_parent=ppNode;}} void _Inorder(Node* root) {if(root==NULL) return; _Inorder(root->_left); cout<_key<<" "<_value<<" "; if(root->_col==0) {cout<<"Red"<_right);} bool _IsBlance(Node* root,int count,int BlackCount) //Use the number of black nodes on each path on the left and right //Compare with the judgment number, the same is the balance, the difference is Unbalance {if (root==NULL) {return count==BlackCount;} Node* parent=root->_parent; if(parent&&(parent->_col==RED&&root->_col==RED)) return false; if (root->_col==BLACK) BlackCount++; return _IsBlance(root->_left,count,BlackCount) &&_IsBlance(root->_right,count,BlackCount); }private: Node* _root;};void TestRBtree(){ RBtree  rb; rb.Insert(0,1); rb.Insert(1,1); rb.Insert(2,1); rb.Insert(3,1); rb.Insert(4,1 ); rb.Insert(5,1); rb.Insert(6,1); rb.Insert(7,1); rb.Insert(8,1); rb.Insert(9,1); rb.Inorder (); if (rb.IsBalance()) {cout<<"Balance"<
test.cpp 


#include "RBtree.h"int main(){ TestRBtree(); system("pause"); return 0;}
 Test results