C++——红黑树

目录

红黑树介绍

 红黑树实现

节点的插入 

完整代码 

红黑树介绍

 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

最长路径不超过最短路径的二倍

红黑树的性质：
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（树中没有连续的红色节点）
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。（每条路径的黑色节点数量相等）
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点
 

 红黑树实现

节点的插入 

当有新节点要插入时，我们尽量遵守规则4，因此插入新节点时，我们插入红色节点。

情况一: cur为红，p为红，g为黑，u存在且为红

abcde是符合红黑树的子树。

如果u存在且为红，p和u变黑，g变红，继续往上处理或者g变黑

新增可以在ab的任意孩子位置

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑。

 p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色--p变黑，g变红

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑。

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
则转换成了情况2
 

完整代码 

   

    

     

      

     
     

      

       #include<iostream>
      
     
    

     

      

     
     

      

       #include <map>
      
     
    

     

      

     
     

      

       #include <string>
      
     
    

     

      

     
     

      

       #include <algorithm>
      
     
    

     

      

     
     

      

       using 
       namespace std;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       #include<time.h>
      
     
    

     

      

     
     

      

       #include <assert.h>
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       enum 
       Colour
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      

       	RED,
      
     
    

     

      

     
     

      

       	BLACK
      
     
    

     

      

     
     

      

       };
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       template<
       class 
       K, 
       class 
       V>
      
     
    

     

      

     
     

      

       struct 
       RBTreeNode
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      

       	RBTreeNode<K, V>* _left;
      
     
    

     

      

     
     

      

       	RBTreeNode<K, V>* _right;
      
     
    

     

      

     
     

      

       	RBTreeNode<K, V>* _parent;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       	pair<K, V> _kv;
      
     
    

     

      

     
     

      

       	Colour _col;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
       RBTreeNode(
       const pair<K, V>& kv)
      
     
    

     

      

     
     

      

       		:_left(
       nullptr)
      
     
    

     

      

     
     

      

       		, _right(
       nullptr)
      
     
    

     

      

     
     

      

       		, _parent(
       nullptr)
      
     
    

     

      

     
     

      

       		, _kv(kv)
      
     
    

     

      

     
     

      

       	{}
      
     
    

     

      

     
     

      

       };
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       template<
       class 
       K, 
       class 
       V>
      
     
    

     

      

     
     

      

       struct 
       RBTree
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      
	
       typedef RBTreeNode<K, V> Node;
      
     
    

     

      

     
     

      

       public:
      
     
    

     

      

     
     

      
	
       bool Insert(const pair<K, V>& kv)
      
     
    

     

      

     
     

      

       	{
      
     
    

     

      

     
     

      
		
       if (_root == 
       nullptr)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      

       			_root = 
       new 
       Node(kv);
      
     
    

     

      

     
     

      

       			_root->_col = BLACK;
      
     
    

     

      

     
     

      
			
       return 
       true;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		Node* parent = 
       nullptr;
      
     
    

     

      

     
     

      

       		Node* cur = _root;
      
     
    

     

      

     
     

      
		
       while (cur)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      
			
       if (cur->_kv.first < kv.first)
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      

       				parent = cur;
      
     
    

     

      

     
     

      

       				cur = cur->_right;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      
			
       else 
       if (cur->_kv.first > kv.first)
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      

       				parent = cur;
      
     
    

     

      

     
     

      

       				cur = cur->_left;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      
			
       else
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      
				
       return 
       false;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		cur = 
       new 
       Node(kv);
      
     
    

     

      

     
     

      

       		cur->_col = RED;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
		
       if (parent->_kv.first < kv.first)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      

       			parent->_right = cur;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
		
       else
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      

       			parent->_left = cur;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		cur->_parent = parent;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
		
       while (parent && parent->_col == RED)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      

       			Node* grandfater = parent->_parent;
      
     
    

     

      

     
     

      
			
       assert(grandfater);
      
     
    

     

      

     
     

      
			
       assert(grandfater->_col == BLACK);
      
     
    

     

      

     
     

      
			
       // 关键看叔叔
      
     
    

     

      

     
     

      
			
       if (parent == grandfater->_left)
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      

       				Node* uncle = grandfater->_right;
      
     
    

     

      

     
     

      
				
       // 情况一 : uncle存在且为红，变色+继续往上处理
      
     
    

     

      

     
     

      
				
       if (uncle && uncle->_col == RED)
      
     
    

     

      

     
     

      

       				{
      
     
    

     

      

     
     

      

       					parent->_col = uncle->_col = BLACK;
      
     
    

     

      

     
     

      

       					grandfater->_col = RED;
      
     
    

     

      

     
     

      
					
       // 继续往上处理
      
     
    

     

      

     
     

      

       					cur = grandfater;
      
     
    

     

      

     
     

      

       					parent = cur->_parent;
      
     
    

     

      

     
     

      

       				}
       // 情况二+三：uncle不存在 + 存在且为黑
      
     
    

     

      

     
     

      
				
       else
      
     
    

     

      

     
     

      

       				{
      
     
    

     

      

     
     

      
					
       // 情况二：右单旋+变色
      
     
    

     

      

     
     

      
					
       // g 
      
     
    

     

      

     
     

      
					
       // p u
      
     
    

     

      

     
     

      
					
       // c
      
     
    

     

      

     
     

      
					
       if (cur == parent->_left)
      
     
    

     

      

     
     

      

       					{
      
     
    

     

      

     
     

      
						
       RotateR(grandfater);
      
     
    

     

      

     
     

      

       						parent->_col = BLACK;
      
     
    

     

      

     
     

      

       						grandfater->_col = RED;
      
     
    

     

      

     
     

      

       					}
      
     
    

     

      

     
     

      
					
       else
      
     
    

     

      

     
     

      

       					{
      
     
    

     

      

     
     

      
						
       // 情况三：左右单旋+变色
      
     
    

     

      

     
     

      
						
       // g 
      
     
    

     

      

     
     

      
						
       // p u
      
     
    

     

      

     
     

      
						
       // c
      
     
    

     

      

     
     

      
						
       RotateL(parent);
      
     
    

     

      

     
     

      
						
       RotateR(grandfater);
      
     
    

     

      

     
     

      

       						cur->_col = BLACK;
      
     
    

     

      

     
     

      

       						grandfater->_col = RED;
      
     
    

     

      

     
     

      

       					}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
					
       break;
      
     
    

     

      

     
     

      

       				}
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      
			
       else 
       // (parent == grandfater->_right)
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      

       				Node* uncle = grandfater->_left;
      
     
    

     

      

     
     

      
				
       // 情况一
      
     
    

     

      

     
     

      
				
       if (uncle && uncle->_col == RED)
      
     
    

     

      

     
     

      

       				{
      
     
    

     

      

     
     

      

       					parent->_col = uncle->_col = BLACK;
      
     
    

     

      

     
     

      

       					grandfater->_col = RED;
      
     
    

     

      

     
     

      
					
       // 继续往上处理
      
     
    

     

      

     
     

      

       					cur = grandfater;
      
     
    

     

      

     
     

      

       					parent = cur->_parent;
      
     
    

     

      

     
     

      

       				}
      
     
    

     

      

     
     

      
				
       else
      
     
    

     

      

     
     

      

       				{
      
     
    

     

      

     
     

      
					
       // 情况二：左单旋+变色
      
     
    

     

      

     
     

      
					
       // g 
      
     
    

     

      

     
     

      
					
       // u p
      
     
    

     

      

     
     

      
					
       // c
      
     
    

     

      

     
     

      
					
       if (cur == parent->_right)
      
     
    

     

      

     
     

      

       					{
      
     
    

     

      

     
     

      
						
       RotateL(grandfater);
      
     
    

     

      

     
     

      

       						parent->_col = BLACK;
      
     
    

     

      

     
     

      

       						grandfater->_col = RED;
      
     
    

     

      

     
     

      

       					}
      
     
    

     

      

     
     

      
					
       else
      
     
    

     

      

     
     

      

       					{
      
     
    

     

      

     
     

      
						
       // 情况三：右左单旋+变色
      
     
    

     

      

     
     

      
						
       // g 
      
     
    

     

      

     
     

      
						
       // u p
      
     
    

     

      

     
     

      
						
       // c
      
     
    

     

      

     
     

      
						
       RotateR(parent);
      
     
    

     

      

     
     

      
						
       RotateL(grandfater);
      
     
    

     

      

     
     

      

       						cur->_col = BLACK;
      
     
    

     

      

     
     

      

       						grandfater->_col = RED;
      
     
    

     

      

     
     

      

       					}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
					
       break;
      
     
    

     

      

     
     

      

       				}
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		_root->_col = BLACK;
      
     
    

     

      

     
     

      
		
       return 
       true;
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
       void InOrder()
      
     
    

     

      

     
     

      

       	{
      
     
    

     

      

     
     

      

       		_InOrder(_root);
      
     
    

     

      

     
     

      

       		cout << endl;
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
       bool IsBalance()
      
     
    

     

      

     
     

      

       	{
      
     
    

     

      

     
     

      
		
       if (_root == 
       nullptr)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      
			
       return 
       true;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
		
       if (_root->_col == RED)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      

       			cout << 
       "根节点不是黑色" << endl;
      
     
    

     

      

     
     

      
			
       return 
       false;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
		
       // 黑色节点数量基准值
      
     
    

     

      

     
     

      
		
       int benchmark = 
       0;
      
     
    

     

      

     
     

      
		
       /*Node* cur = _root;
      
     
    

     

      

     
     

      

        while (cur)
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      

        if (cur->_col == BLACK)
      
     
    

     

      

     
     

      

        ++benchmark;
      
     
    

     

      

     
     

      

       
      
     
    

     

      

     
     

      

        cur = cur->_left;
      
     
    

     

      

     
     

      

        }*/
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
		
       return 
       PrevCheck(_root, 
       0, benchmark);
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       private:
      
     
    

     

      

     
     

      
	
       bool PrevCheck(Node* root, int blackNum, int& benchmark)
      
     
    

     

      

     
     

      

       	{
      
     
    

     

      

     
     

      
		
       if (root == 
       nullptr)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      
			
       //cout << blackNum << endl;
      
     
    

     

      

     
     

      
			
       //return;
      
     
    

     

      

     
     

      
			
       if (benchmark == 
       0)
       //黑色节点数量的基准值
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      

       				benchmark = blackNum;
      
     
    

     

      

     
     

      
				
       return 
       true;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
			
       if (blackNum != benchmark)
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      

       				cout << 
       "某条黑色节点的数量不相等" << endl;
      
     
    

     

      

     
     

      
				
       return 
       false;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      
			
       else
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      
				
       return 
       true;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
		
       if (root->_col == BLACK)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      

       			++blackNum;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
		
       if (root->_col == RED && root->_parent->_col == RED)
       //如果有连续红色节点，则不是红黑树
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      

       			cout << 
       "存在连续的红色节点" << endl;
      
     
    

     

      

     
     

      
			
       return 
       false;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
		
       return 
       PrevCheck(root->_left, blackNum, benchmark)
      
     
    

     

      

     
     

      

       			&& 
       PrevCheck(root->_right, blackNum, benchmark);
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
       void _InOrder(Node* root)
      
     
    

     

      

     
     

      

       	{
      
     
    

     

      

     
     

      
		
       if (root == 
       nullptr)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      
			
       return;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		_InOrder(root->_left);
      
     
    

     

      

     
     

      

       		cout << root->_kv.first << 
       ":" << root->_kv.second << endl;
      
     
    

     

      

     
     

      

       		_InOrder(root->_right);
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
       void RotateL(Node* parent)
      
     
    

     

      

     
     

      

       	{
      
     
    

     

      

     
     

      

       		Node* subR = parent->_right;
      
     
    

     

      

     
     

      

       		Node* subRL = subR->_left;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		parent->_right = subRL;
      
     
    

     

      

     
     

      
		
       if (subRL)
      
     
    

     

      

     
     

      

       			subRL->_parent = parent;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		Node* ppNode = parent->_parent;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		subR->_left = parent;
      
     
    

     

      

     
     

      

       		parent->_parent = subR;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
		
       if (_root == parent)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      

       			_root = subR;
      
     
    

     

      

     
     

      

       			subR->_parent = 
       nullptr;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
		
       else
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      
			
       if (ppNode->_left == parent)
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      

       				ppNode->_left = subR;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      
			
       else
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      

       				ppNode->_right = subR;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       			subR->_parent = ppNode;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
       void RotateR(Node* parent)
      
     
    

     

      

     
     

      

       	{
      
     
    

     

      

     
     

      

       		Node* subL = parent->_left;
      
     
    

     

      

     
     

      

       		Node* subLR = subL->_right;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		parent->_left = subLR;
      
     
    

     

      

     
     

      
		
       if (subLR)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      

       			subLR->_parent = parent;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		Node* ppNode = parent->_parent;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       		subL->_right = parent;
      
     
    

     

      

     
     

      

       		parent->_parent = subL;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
		
       if (_root == parent)
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      

       			_root = subL;
      
     
    

     

      

     
     

      

       			subL->_parent = 
       nullptr;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
		
       else
      
     
    

     

      

     
     

      

       		{
      
     
    

     

      

     
     

      
			
       if (ppNode->_left == parent)
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      

       				ppNode->_left = subL;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      
			
       else
      
     
    

     

      

     
     

      

       			{
      
     
    

     

      

     
     

      

       				ppNode->_right = subL;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       			subL->_parent = ppNode;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       private:
      
     
    

     

      

     
     

      

       	Node* _root = 
       nullptr;
      
     
    

     

      

     
     

      

       };
      
     
    

     

      

     
     

      

       void TestRBTree1()
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      
	
       size_t N = 
       1000;
      
     
    

     

      

     
     

      
	
       srand(
       time(
       0));
      
     
    

     

      

     
     

      

       	RBTree<
       int, 
       int> t1;
      
     
    

     

      

     
     

      
	
       for (
       size_t i = 
       0; i < N; ++i)
      
     
    

     

      

     
     

      

       	{
      
     
    

     

      

     
     

      
		
       int x = 
       rand();
      
     
    

     

      

     
     

      

       		cout << 
       "Insert:" << x << 
       ":" << i << endl;
      
     
    

     

      

     
     

      

       		t1.
       Insert(
       make_pair(x, i));
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      

       	cout << 
       "IsBalance:" << t1.
       IsBalance() << endl;
      
     
    

     

      

     
     

      

       }
      
     
    

     

      

     
     

      

       int main()
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      
	
       TestRBTree1();
      
     
    

     

      

     
     

      
	
       return 
       0;
      
     
    

     

      

     
     

      

       }