# Red black tree

## The concept of red black tree

Red black tree , is a kind of Binary search tree , but Add a storage bit on each node to represent the color of the node, which can be Red or Black . By limiting the coloring method of each node on any path from root to leaf, the red black tree ensures that no path will be two longer than other paths times , therefore Near equilibrium of ## Properties of red black tree

1. Each node is 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 this node to all its descendant leaf nodes contains the same number of black nodes
5. Each leaf node is black ( The leaf node here refers to an empty node )
Thinking: why can the red black tree ensure that the number of nodes in the longest path will not exceed two times the number of nodes in the shortest path Times?
A: suppose the black node of a path is h, then many short paths are h, and the longest path is 2H. The boss is the boss, and I don't know how to think of it.

## Definition of red black tree node

```enum Colour
{
RED,
BLACK
};
template<class K,class V>
class RBTreeNode
{
public:
RBTreeNode(const std::pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(RED)
{

}
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
std::pair<K, V> _kv;
Colour _col;
};```
Think: in the definition of node, why should the default color of node be red?
A: the node is defined in red for convenience.

### Red black tree structure

In order to simplify the subsequent implementation of the associated container, a head node is added in the implementation of the red black tree, because the heel node must be black. In order to distinguish from the root node, the head node is black, and the Parent of the head node is black The domain points to the root node of the red black tree, Left The domain points to the smallest node in the red black tree, Right The domain points to the largest node in the red black tree, as follows: ## Insertion of red black tree

### 1. Insert new nodes according to the tree rules of binary search

```template<class K,class V>
class RBTree
{
public:
typedef RBTreeNode<K, V> Node;
RBTree()
:_root(nullptr)
{

}
bool insert(const std::pair<K,V> &kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//New node
cur = new Node(kv);
cur->_col = RED;
if (kv.first > parent->_kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
}```

### 2. Detect whether the nature of red black tree is damaged after the new node is inserted

because The default color for new nodes is red Therefore: if The color of its parent node is black, which does not violate any property of red black tree , no adjustment is required; However, when the color of the parent node of the newly inserted node is red, it violates property 3 and cannot have connected red nodes At this time, we need to discuss the situation of red and black trees:
appointment :cur Is the current node, p As the parent node, g Is the grandfather node, u For uncle node

### Case 1: cur is red, p is red, g is black, and u exists and is red ### Note: there are two cases of u

1. If u node does not exist, cur must be a newly inserted node. If cur is not a newly inserted node, one of cur and p must be black, which does not meet property 4. The number of black nodes in each path is the same.

2. If the u node exists, it must be black, and the original color of the cur node must also be black. Now we see the reason why it is red, because the cur subtree changes the color of cur from black to red during the adjustment process.

If p is the left child of g and cur is the left child of p, perform right single rotation

If p is the right child of g and cur is the right child of p, carry out left single rotation

p. g discoloration -- P turns black and g turns red.

### Situation 3 Cur is red, p is red, g is black, u does not exist / u is black p by g My left child, cur by p For the right child p Do left single rotation; contrary,
p by g My right child, cur by p For the left child p Right rotation
Then it turns into a situation 2
```//Control balance
while (parent != nullptr && parent->_col == RED)  //If the father exists and the father's node is red
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//Case 1: the uncle node exists and the color of the uncle node is red
if (uncle != nullptr && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;  //The father node and uncle node turn black
grandfather->_col = RED;

//grandfather may not be the root node. Continue to update
cur = grandfather;
parent = cur->_parent;
}
else //Case 2 + 3, uncle does not exist / exists and is black, which may be caused by case 1 - > case 2 / case 3
{
//        g
//      p
//    c
if (cur == parent->_left)
{
//Right single rotation
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
//Trigger left and right double rotation
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
//Case 1: Uncle exists and the color of uncle is red
if (uncle != nullptr && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;  //Uncle and father change color
grandfather->_col = RED;

//grandfather may not be the root node, so it may be updated upward all the time
cur = grandfather;
parent = cur->_parent;
}
else  //Case 2 + 3, uncle does not exist / exists and is black
{
if (cur == parent->_right)  //Trigger left rotation
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
//Trigger right left double rotation
RotateR(parent);
RotateL(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}```

### Rotation code:

```void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentparent = parent->_parent;

parent->_left = subLR;
if (subLR != nullptr)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentparent->_left == parent)
parentparent->_left = subL;
else
parentparent->_right = subL;
subL->_parent = parentparent;
}
}
void RotateL(Node* parent)
{

Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentparent = parent->_parent;

parent->_right = subRL;
if (subRL != nullptr)
subRL->_parent = parent;

subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentparent->_left == parent)
parentparent->_left = subR;
else
parentparent->_right = subR;

subR->_parent = parentparent;
}
}```

## Verification of red black tree

The detection of red black tree is divided into two steps:
1. Check whether it meets the binary search tree ( Whether the middle order traversal is an ordered sequence )
2. Check whether it meets the properties of red black tree
```bool IsBalance()
{
if (_root && _root->_col == RED)
{
std::cout << "The root node is not black" << std::endl;
return false;
}

// The number of black nodes in the leftmost path is used as the reference value
int banchmark = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK)
++banchmark;

left = left->_left;
}

int blackNum = 0;
return _IsBalance(_root, banchmark, blackNum);
}

bool _IsBalance(Node* root, int banchmark, int blackNum)
{
if (root == nullptr)
{
if (banchmark != blackNum)
{
std::cout << "There is an unequal number of black nodes in the path" << std::endl;
return false;
}

return true;
}

if (root->_col == RED && root->_parent->_col == RED)
{
std::cout << "Continuous red nodes appear" << std::endl;
return false;
}

if (root->_col == BLACK)
{
++blackNum;
}

return _IsBalance(root->_left, banchmark, blackNum)
&& _IsBalance(root->_right, banchmark, blackNum);
}```

## Deletion of red black tree

The deletion of red black tree is not explained in this section. Interested students can refer to: introduction to algorithm or< STL Source code analysis
http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html
http://blog.csdn.net/chenhuajie123/article/details/11951777

## Comparison between red black tree and AVL tree

Red black tree and AVL Trees are efficient balanced binary trees, and the time complexity of adding, deleting, modifying and checking is O(log2 N  ) , red and black trees do not pursue absolute balance Just ensure that the longest path does not exceed the length of the shortest path 2 Times, relatively speaking, it reduces the number of insertion and rotation, so in the structure of frequent addition and deletion Neutral energy ratio AVL The tree is better, and the implementation of red black tree is relatively simple, so there are more red black trees in practical application.

## Application of red black tree

1. C++ STL library -- map/set , mutil_map/mutil_set
2. Java library
3. linux kernel
4. Some other libraries
http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html
All codes of red black tree:
RBTree.h
```#pragma once
#include<iostream>
enum Colour
{
RED,
BLACK
};
template<class K,class V>
class RBTreeNode
{
public:
RBTreeNode(const std::pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(RED)
{

}
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
std::pair<K, V> _kv;
Colour _col;
};

template<class K,class V>
class RBTree
{
public:
typedef RBTreeNode<K, V> Node;
RBTree()
:_root(nullptr)
{

}
bool insert(const std::pair<K,V> &kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//New node
cur = new Node(kv);
cur->_col = RED;
if (kv.first > parent->_kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//Control balance
while (parent != nullptr && parent->_col == RED)  //If the father exists and the father's node is red
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//Case 1: the uncle node exists and the color of the uncle node is red
if (uncle != nullptr && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;  //The father node and uncle node turn black
grandfather->_col = RED;

//grandfather may not be the root node. Continue to update
cur = grandfather;
parent = cur->_parent;
}
else //Case 2 + 3, uncle does not exist / exists and is black, which may be caused by case 1 - > case 2 / case 3
{
//        g
//      p
//    c
if (cur == parent->_left)
{
//Right single rotation
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
//Trigger left and right double rotation
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
//Case 1: Uncle exists and the color of uncle is red
if (uncle != nullptr && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;  //Uncle and father change color
grandfather->_col = RED;

//grandfather may not be the root node, so it may be updated upward all the time
cur = grandfather;
parent = cur->_parent;
}
else  //Case 2 + 3, uncle does not exist / exists and is black
{
if (cur == parent->_right)  //Trigger left rotation
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
//Trigger right left double rotation
RotateR(parent);
RotateL(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
private:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentparent = parent->_parent;

parent->_left = subLR;
if (subLR != nullptr)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentparent->_left == parent)
parentparent->_left = subL;
else
parentparent->_right = subL;
subL->_parent = parentparent;
}
}
void RotateL(Node* parent)
{

Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentparent = parent->_parent;

parent->_right = subRL;
if (subRL != nullptr)
subRL->_parent = parent;

subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentparent->_left == parent)
parentparent->_left = subR;
else
parentparent->_right = subR;

subR->_parent = parentparent;
}
}
public:
void inoder()
{
Node* cur = _root;
Node* MostRight = nullptr;
while (cur != nullptr)
{
MostRight = cur->_left;
if (MostRight != nullptr)
{
while (MostRight->_right != nullptr && MostRight->_right != cur)
{
MostRight = MostRight->_right;
}
if (MostRight->_right == nullptr)
{
MostRight->_right = cur;
cur = cur->_left;
continue;
}
else
{
MostRight->_right = nullptr;
}
}
std::cout << cur->_kv.first << ":" << cur->_kv.second << std::endl;
cur = cur->_right;
}
}
bool IsBalance()
{
if (_root && _root->_col == RED)
{
std::cout << "The root node is not black" << std::endl;
return false;
}

// The number of black nodes in the leftmost path is used as the reference value
int banchmark = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK)
++banchmark;

left = left->_left;
}

int blackNum = 0;
return _IsBalance(_root, banchmark, blackNum);
}

bool _IsBalance(Node* root, int banchmark, int blackNum)
{
if (root == nullptr)
{
if (banchmark != blackNum)
{
std::cout << "There is an unequal number of black nodes in the path" << std::endl;
return false;
}

return true;
}

if (root->_col == RED && root->_parent->_col == RED)
{
std::cout << "Continuous red nodes appear" << std::endl;
return false;
}

if (root->_col == BLACK)
{
++blackNum;
}

return _IsBalance(root->_left, banchmark, blackNum)
&& _IsBalance(root->_right, banchmark, blackNum);
}
private:
Node* _root;
};```

test.cpp

```#include"AVL.h"
#include"RBTree.h"

void AVLTreeTest(void)
{
AVLTree<int, int> av;
int array[] = { 9,6,4,3,7,3,2,0,544,43224,23,423,42,4234,2,4242,423,42,7,11,98,5 };
for (const auto& e : array)
{
av.insert(std::pair<int,int>(e,e));
}
av.inoder();
}
void RBTreeTest(void)
{
RBTree<int, int> rb;
int array[] = { 9,6,4,3,7,3,2,0,544,43224,23,423,42,4234,2,4242,423,42,7,11,98,5 };
for (const auto& e : array)
{
rb.insert(std::pair<int, int>(e, e));
std::cout << rb.IsBalance() << std::endl;
}
rb.inoder();
}
int main()
{
//AVLTreeTest();
RBTreeTest();
}```

Tags: Java data structure

Posted by Easter Bunny on Tue, 17 May 2022 02:24:17 +0300