C++_红黑树

红黑树

红黑树的概念

因为AVL树的规则太严格，需要经常旋转，所以引入了红黑树。

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

红黑树的性质

1. 每个节点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则他的两个孩子节点是黑色的(不能出现连续的红节点)
4. 对于每个节点，从该节点到其他后代节点的简单路径上，均包含相同数目的黑色节点
5. 每个叶子节点都是黑色的（此处叶子节点指的是空节点（NIL节点））

满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的二倍，为什么？

跟据以上的性质，一条路径最短就是一条路径上都是黑结点，一条路径最长就是一个黑节点，一个红节点。红节点不能是连续的，黑节点可以连续，每条路径上的黑节点数目必须相同。

上述情况，最短路径的节点个数*2与最长路径节点个数相同

但是，一颗红黑树中，最短，最长不一定是这种情况，

但是，最短只有可能比那种情况长，而最长只有可能比那种情况短

那么最长路径就小于最短路径的二倍

红黑树节点的定义

enum Color
{
	Red,
	Black
};

template<class k,class  v>
struct RBTree_Node
{
	pair<k, v> _data;			//存储的数据
	RBTree_Node<k, v>* _parent;	//节点的双亲
	RBTree_Node<k, v>* _left;	//节点的左孩子
	RBTree_Node<k, v>* _right;	//节点的右孩子
	Color _color;				//节点的颜色

	RBTree_Node(const pair<k, v>& data)
		:_data(data)
		,_parent(nullptr)
		,_left(nullptr)
		,_right(nullptr)
		,_color(Red)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

创建节点默认是红色，是因为插入时，插入红色节点，因为插入红色节点的代价小（插入红色节点不一定要处理），但是插入黑节点一定要处理

红黑树的插入操作

//先按照二叉搜素树的规则进行插入
bool Insert(const pair<k, v>& x)
{
	if (_root == nullptr)
	{
		_root = new Node(x);
		_root->_color = Black;
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (cur->_data.first < x.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_data.first > x.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(x);
	if (parent->_data.first < x.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;

	/插入后，共有三种情况需要处理，
    /在这三种情况中，g一定为黑，cur，p一定为红（因为只有p为红，才可能需要处理）
    /需要处理的情况，cur，p一定为红，g一定为黑，
	//u不一定（可能为红、黑可能没有）

    /先看后面红黑树需要处理的几种情况
    /这里的循环是因为情况1处理后,可能需要向上继续处理
	while (parent&&parent->_color==Red)
	{
		Node* grandfather = parent->_parent;
		assert(grandfather);
		Node* uncle = nullptr;
		if (parent == grandfather->_left)
			uncle = grandfather->_right;
		else
			uncle = grandfather->_left;

        //情况1
		if (uncle&&uncle->_color == Red)
		{
			parent->_color = uncle->_color = Black;
			grandfather->_color = Red;
			cur = grandfather;
			parent = cur->_parent;
		}
		else
		{
			if (grandfather->_left == parent)
			{
                //情况2
				if (cur == parent->_left)
				{
					RotateR(grandfather);
					grandfather->_color = Red;
					parent->_color = Black;
				}
                //情况3
				else
				{
					RotateL(parent);
					RotateR(grandfather);
					cur->_color = Black;
					grandfather->_color = Red;

				}
			}
			else
			{
                //情况2
				if (cur == parent->_right)
				{
					RotateL(grandfather);
					grandfather->_color = Red;
					parent->_color = Black;
				}
                //情况3
				else
				{
					RotateR(parent);
					RotateL(grandfather);
					cur->_color = Black;
						grandfather->_color = Red;
					}
				}
				break;
			}
		}
    _root->_color = Black;	
    /情况1处理后,当前g可能是整棵树的根节点,不能向上处理,那么将根节点置为黑,因为是整棵树的根节点,所有路径的黑节点都加1,依旧满足规则
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

红黑树需要处理的几种情况

情况1（u为红）

情况1中的具体情况1

cur就是新插入的节点,插入后出现连续的红节点,需要处理

情况1中的具体情况2

在新节点插入之前,cur是黑色节点,在cur为根节点的子树中插入新节点,就是具体情况1的情况,经过具体情况1的处理,cur变成了红色,这个cur就是具体情况1中g,也有可能是具体情况2中的g,就是底下还有一层.

• 情况1的处理,只需要变色,不需要旋转就可以符合红黑树的规则

• 因为不需要旋转,所以p和u的位置无论左右,cur无论插入在parent的左右,处理方法都一样

处理方法:

将p和u的颜色变黑,g的颜色变红,使这个树的每条路径的黑节点数目相同,并且没有连续的红节点,但是根节点变红,根节点与它的双亲结点可能出现连续的双亲结点,所以需要向上检查

如果这个根节点的双亲结点为黑, 处理结束(因为红节点不连续,也不影响整棵树每条路径的黑节点数目)

但是如果是红,就违反规则,需要继续处理(就进入可能是情况1/情况2/情况3(情况2和情况3在下面))

情况2（u为空/黑）（parent在右时左旋）

cur在p的子树方向,与p在g的子树方向一致

u为空

cur为新增结点

u为黑

在u为黑的情况中

• 在插入新节点之前,cur一定是黑色的(因为在插入之前,这是一个符合规则的红黑树)

• 在插入新节点之后,经过情况1的处理,cur变为红,情况1的g->cur,进入到情况2(可能是具体情况1->情况2/具体情况1->具体情况2->情况2)

• u为黑这种情况一定是经过情况1的处理

处理方法:

当p在g的左子树,cur在p的左子树时,g树右旋,p变为黑色,g变为红色(上图就是这种情况)

当p在g的右子树,cur在p的右子树时,g树左旋,p变为黑色,g变为红色(这种情况没有画出)

在情况2处理之后,处理结束(没有来连续的红节点,并且根节点为黑色,所以与当前g的双亲结点也不可能是连续的红节点,每条路径的黑结点的数目也没有发生变化)

情况3（u为空/黑）（当parent在右子树时，就是右左双旋）

u为空

cur为新增结点

u为黑

根节点为黑色

• 在插入新节点之前,cur一定是黑色的(因为在插入之前,这是一个符合规则的红黑树)

• 在插入新节点之后,经过情况1的处理,cur变为红,情况1的g->cur,进入到情况2(可能是具体情况1->情况2/具体情况1->具体情况2->情况2)

• u为黑这种情况一定是经过情况1的处理

处理方法:

当p在g的左子树,cur在p的右子树时,p树左旋,g树右旋,cur变为黑色,g变为红色(上图就是这种情况)

当p在g的右子树,cur在p的左子树时,p树右旋,g树左旋,cur变为黑色,g变为红色(这种情况没有画出)

在情况2处理之后,处理结束(没有来连续的红节点,并且根节点为黑色,所以与当前g的双亲结点也不可能是连续的红节点,每条路径的黑结点的数目也没有发生变化)

除了以上三种情况外,其余所有情况都是不需要处理的

红黑树的验证

红黑树的检测分为两步:

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

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

   bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
   	{
   		//走到null之后，判断k和black是否相等
   		if (nullptr == pRoot)
   		{
   			if (k != blackCount)
   			{
   				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
   				return false;
   			}
   			return true;
   		}
   
   		// 统计黑色节点的个数
   		if (Black == pRoot->_color)
   			k++;
   
   		// 检测当前节点与其双亲是否都为红色
   		if (Red == pRoot->_color && pRoot->_parent && pRoot->_parent->_color == Red)
   		{
   			cout << "违反性质三：存在连在一起的红色节点" << endl;
   			return false;
   		}
   
   		return _IsValidRBTree(pRoot->_left, k, blackCount) &&
   			_IsValidRBTree(pRoot->_right, k, blackCount);
   
   	}
   
   bool IsBalanceTree()
   {
   	// 检查红黑树几条规则
   
   	Node* pRoot = _root;
   	// 空树也是红黑树
   	if (nullptr == pRoot)
   		return true;
   
   	// 检测根节点是否满足情况
   	if (Black != pRoot->_color)
   	{
   		cout << "违反红黑树性质二：根节点必须为黑色" << endl;
   		return false;
   	}
   
   	// 获取任意一条路径中黑色节点的个数 -- 比较基准值
   	size_t blackCount = 0;
   	Node* pCur = pRoot;
   	while (pCur)
   	{
   		if (Black == pCur->_color)
   			blackCount++;
   
   		pCur = pCur->_left;
   	}
   
   	// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
   	size_t n = 0;
   	return _IsValidRBTree(pRoot, n, blackCount);
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50
   51
   52
   53
   54
   55
   56
   57
   58
   59
   60

红黑树与AVL树的比较

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