# Red black tree

## The concept of red black tree

## Properties of red black tree

## 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; };

### Red black tree structure

## Insertion of red black tree

### The red black tree is based on the binary search tree with its balance constraints. Therefore, the insertion of red black tree can be divided into two steps:

### 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

### Case 1: cur is red, p is red, g is black, and u exists and is red

### Solution: change P and u to black, G to red, and then take g as cur and continue to adjust upward

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

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

//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

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

## Comparison between red black tree and AVL tree

## Application of red black tree

#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(); }