数据结构：红黑树

目录

1.红黑树概念        

 2.红黑树的性质

3. 红黑树实现

3.1 红黑树节点定义

3.2 红黑树的插入操作

3.3 红黑树的验证

3.4 红黑树的删除

 3.5 红黑树与AVL树的比较

4.完整代码

---

1.红黑树概念        

        红黑树，是一种搜索二叉树，但在每个节点上增加一个存储为表示节点的颜色，可以时Red或者Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径路径长出两倍，因而接近平衡。

下面为红黑树的图示：

 2.红黑树的性质

        a.每个节点并不是黑色就是红色

        b.根节点是黑色

        c.一个节点为红色，那么它的孩子节点一定都为黑色

        d.对于每个节点，从该节点到其所有后代叶子节点的路径上，均包含相同数目的黑色节点

        e.每个叶子节点都是黑色的(这里的叶子节点指的是空节点)

那为什么满足上述的特征，红黑树就能保证其最长的路径不超过最短路径的二倍呢？

        原因是这样的，假设有一颗全是黑色节点的红黑树，为了满足性质d，这棵树一定为一颗满二叉树。现在插入红色节点，由于性质b,c，每两个黑色节点之间最多只能有一个红色节点，那么，对于任意一条路径，最多只能插入树的深度个红色节点，如下图所示(为了方便起见，下图没有画出空节点):

3. 红黑树实现

3.1 红黑树节点定义

        节点颜色 使用枚举的形式

        以三叉链的形式建立树，节点中存储颜色和一个pair类型的变量

enum Color{BLACK, RED};
 
template <class K, class V>
struct RBTreeNode
{
    //有参构造函数
    RBTreeNode*(const pair<K, V>& kv)
        :_kv(kv)
        ,_col(RED)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
    {}
    
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    //存储节点颜色
    Color _col;
    pair<K, V> _kv;
};

 为什么将节点的默认颜色给为红色？

        在插入节点时，不论是给红色还是黑色，都有可能会违反红黑树的五个性质。若默认颜色给黑色，则每次插入都会违反性质d，所付出的代价是大的，而插入红色节点，也可能不会违反性质，所以我破门选择把每次插入的新节点设为红色。

3.2 红黑树的插入操作

        (1).按照二叉搜索树的规则插入新节点

        (2).检测插入节点后红黑树的性质是否被破坏，若被破坏则进行调整

因为新插入的节点默认颜色是红色的，因此，如果其双亲节点的颜色是黑色的，没有违反红黑树的性质，则不需要调整；但当插入节点的双亲节点为红色的时候，就违反了性质c，树中不能有两个连续的红色节点，此时需要对红黑树进行分情况讨论。

我们这里将红黑树的插入分为三种情况

• 情况一 ：cur为红，parent为红，grandparent为黑，uncle存在且为红  

注意：此时的树可能是一颗完整的树，也可能是一棵子树。

如果grandparent是树的根节点，为了满足性质b，需要将根节点调整为黑色。

如果grandparent不是根节点，若grandparent的根4父节点是红色的话，需要继续向上调整。

这里能否将cur直接变为黑色呢?

        答案肯定是不行的，若将cur直接变为黑色，则不满足性质d了。

        解决方案：parent、uncle变黑，grandparent变红，然后把grandparent当cur继续向上调整

• 情况二：cur为红，parent为红，grandparent为黑，uncle不存在/为黑(三个节点为直线)

        (1) uncle不存在时  解决方案：向把13进行右旋操作，parent变黑，grandparent变红

         uncle不存在时cur一定为新增的节点，若cur不为新增的节点，那么它的孩子中一定存在黑色的节点，而这使得以grandparent为根的 树/子树不满足性质d。所以cur一定为新增的节点。

        (2) uncle存在且为黑色时 解决方案：把13右旋，parent变黑，grandparent变红

         如果uncle存在且为黑，那么cur一定不是新增的节点，cur原来是黑色，是由于cur的子树调节而变红的。

        parent为grandparent的左孩子，cur为parent的左孩子，先右旋再变色；

        parent为grandparent的右孩子，cur为parent的右孩子，先左旋再变色。

        这两种情况我只画了第一种，第二种也一个道理，可以自行尝试。

• 情况三：cur为红，parent为红，grandparent为黑，uncle不存在/为黑(三个节点为折线)

        (1) uncle不存在 解决方案：8左旋，13右旋，parent变黑，grandparent变红

       (2) u存在且为黑色 解决方案：8左旋，13右旋，parent变黑，grandparent变红

        parent为grandparent的左孩子，cur为parent的右孩子，对parent进行左旋

        parent为grandparent的右孩子，cur为parent的左孩子，对parent进行右旋

        此时，转变为了情况二。

        这两种情况只花了第一种，第二种情况可自己尝试。

那么，上述就为红黑树插入的三种情况了！下面实现红黑树插入的代码。

template <class K, class V>
typedef RBtreeNode<K, V> Node;
 
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);
    if (parent->_kv.first < kv.first)
	    parent->_right = cur;
    else
    	parent->_left = cur;
    cur->_parent = parent;
    //新增节点给红色
    cur->_col = RED;
    
    //可能为连续调节 parent为黑色时不用处理
    while (parent && parent->_col == RED)
    {
	    //红黑树的调节关键看叔叔节点(uncle节点)
	    Node* grandfather = parent->_parent;
	    if (grandfather->_left == parent)
	    {
		    Node* uncle = grandfather->_right;
            //情况一
            //uncle存在，且为红色
            if(uncle && uncle->_col == RED)
            {
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;
 
                //继续向上处理
                cur = grandfather;
                parent = cur->_parent;
            }
            //情况二、三
            //uncle不存在或者为黑色
            else
            {
                if(cur == parent->_right)
                {
                    //parent左旋
                    RotateL(parent);
                    //交换parent和cur 转换为情况二
                    swap(parent, cur);
                }
                //情况二
                //grandfather右旋，然后节点变色
                RotateR(grandfather);
                grandfather->_col = RED;
                parent->_col = BLACK;
                break;
            }
	    }
	    //方向相反的情况
	    else
    	{
		    Node* uncle = grandfather->_left;
	        //情况一
            //uncle 存在 且为红色
            if (uncle && uncle->_col == RED)
            {
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
 
				//继续向上处理
				cur = grandfather;
				parent = grandfather->_parent;
            }
            //第二 第三种情况 uncle 不存在或者为黑色 需要旋转
            else
            {
  				//情况三 uncle为存在且为黑色 折线 需要双旋
				if (cur == parent->_left)
				{
					//先把parent右旋
					RotateR(parent);
					//把两个节点指针只想交换 成为第二种情况
					swap(parent, cur);
				}
 
				//第二种情况
				//将grandfather左旋
				RotateL(grandfather);
				grandfather->_col = RED;
				//因为parent与cur交换了 所以这里是将parent的颜色改变
				parent->_col = BLACK;
				break;
            }
	    }
    }
    _root->_col = BLACK;
    return true;
}

下面为左旋还有右旋的代码

//左旋
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 (parent == _root)
	{
		_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;
	subL->_right = parent;
	Node* ppNode = parent->_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;
	}
}

3.3 红黑树的验证

红黑树的检测分为两步：

        1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

        2. 检测其是否满足红黑树的性质 

//验证子函数
bool _IsValidRBTree(Node* pRoot, size_t k, size_t countBlack)
{    
    //当pNode走到nullptr时，判断此条路径的黑色节点个数与countBlack是否相同
    if(pRoot == bullptr)
    {    
        if(k != countBlack)
        {
            cout<<"不满足性质d"<<endl;
            return false;
        }
        return true;
    }
    
    //统计黑色节点个数
    if(pRoot->_col == BLACK)
        k++;
    
    //检测当前节点与双亲是否都为红色
    if(pRoot->_parent && pRoot->_col == RED && pRoot->_parent->_col == RED)
    {
        cout<<"违反了性质c"<<endl;
        return false;
    }
    //左右子树都要满足红黑树性质
    return _IsValidRBTree(pRoot->_left, k, countBlack) && _ISValidRBTree(pRoot->_right, k, countBlack);
}
 
bool IsValidRBTree()
{
    //获取根节点
    Node* pRoot = _root;
    //空树为红黑树
    if(pRoot == nullptr)
    {
        return true;
    }
    //检查根节点是否满足情况
    if(pRoot->_col != BLACK)
    {
        cout<<"不满足性质b"<<endl;
        returnv false;
    }
    //获取任意路径中的黑色节点个数
    size_t countBlack = 0;
    Node* cur = pRoot;
    while(cur)
    {
        if(cur->_col == BLACK)
            countBlack++;
        cur = cur->_left;
    }
    //检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
    return _IsValidRBTree(pRoot, k, countBlack);
}

3.4 红黑树的删除

本文不对红黑树的删除进行详细的讲解，其与二叉搜索树的删除规则相同。

删除后，再判断是否满足红黑树的性质。

删除红色节点时，是不会出现问题的，按照二叉搜索树的规则删除即可。

删除黑色节点时，如果能找到红色节点代替，则用红节点代替，在变为黑色节点，若找不到，则要进行旋转。感兴趣的可以自己看下面的两个链接：

https://blog.csdn.net/chenhuajie123/article/details/11951777

https://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html

 3.5 红黑树与AVL树的比较

        红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( )，红黑树不追求绝对平衡，其 只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构 中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

STL容器map和set底层就是用红黑树实现的，后续会出模拟实现map和set的文章。

4.完整代码

#include<iostream>
using namespace std;
#include<utility>
 
enum Colour
{
	BLACK,
	RED,
};
 
template<class K,class V>
class RBTreeNode
{
public:
	RBTreeNode<K, V>(const pair<K,V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_col(RED)
	{}
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _parent;
	RBTreeNode<K, V>* _right;
 
	pair<K, V> _kv;
	Colour _col;
};
 
template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
 
	bool Insert(const pair<K, V>& kv)
	{
		//...
	}
 
	//左旋
	void RotateL(Node* parent)
	{
		//...
	}
 
	//右旋
	void RotateR(Node* parent)
	{
		//...
	}
 
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
 
	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
	}
 
	//获取根节点
	Node* GetRoot()
	{
		return _root;
	}
 
	//检测是否满足红黑树性质
	bool IsValidRBTree()
	{
		//...
	}
 
	bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
	{
		//...
	}
 
	//删除
 
private:
	Node* _root = nullptr;
};
 
void testRBTree()
{
	int a[] = { 4,2,6,1,3,5,15,7,16,14 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOrder();
	cout << t.IsValidRBTree() << endl;
}
 
int main()
{
    testRBTree();
    return 0;
}