【C++】红黑树的性质以及实现

上篇博客我们了解了AVL树，这篇博客就让我们来看看另外一个二叉树：红黑树

使用的编译器：VS2019

---

博客里面引用了一些百度搜到的图片（自己懒的画了，呜呜）

1.概念

AVL树是一个几乎完全平衡的搜素二叉树，其左右子树的高度差不会超过1。与之相对应的，是每一次插入都有可能需要旋转多次，插入的效率较低。

而红黑树则选择了“相对平衡”，并拥有以下的特性：

• 红黑树可以保证最长路径的小于最短路径的2倍

• 比如最短路径为30，那么最长路径就不能超过60

对于cpu来说，AVL树遍历20次（百万级数据）和红黑树遍历40次的时间差距极小。所以红黑树即保持了相对平衡，又减小了AVL树多次旋转的消耗。

1.1 性质

其通过下面的几点来维持这一性质：

1. 每一个节点不是红色就是黑色
2. 根节点一定是黑色
3. 每一个红节点的左右子树都是黑色
4. 每一个到叶子（空节点NIL）的支路上黑节点数量相同
5. 叶子节点（空节点NIL）视作黑色

为什么满足了这几个情况，就满足了红黑树的最长路径的小于最短路径的2倍的性质呢？

约束4和5，保证了红黑树的大致平衡：根到叶子的所有路径中，最长路径不会超过最短路径的2倍。
这使得红黑树在最坏的情况下，也能有O(logN) 的查找效率

• 黑色高度为3时，最短路径：黑色→ 黑色 →黑色
• 最长路径：黑色→红色 →黑色 →红色 →黑色
• 此时最短路径的长度为2（不算Nil的叶子节点），最长路径为4

这里可以得出一个普遍规律，红黑树最短路径即为全黑路径。而最长路径是一黑一红间隔的情况

---

2.设计一颗红黑树

在设计红黑树的时候，我们需要牢记上面的5点。其中前4点非常重要且不可以被破坏。一旦被破坏，就影响了红黑树的基本性质。

2.1 设计节点

和AVL树一样，我们需要把节点单独成一个类，来存放我们需要的pair

这里就设计到了颜色的初值应该给什么。红色，还是黑色？

来看看性质3和4：

• 红色的左右子树必须是黑色
• 每一个到叶子（空节点NIL）的支路上黑节点数量相同

简单思考，即可发现，插入红节点的时候，更好控制。而插入黑节点极有可能破坏性质4且较难修复。

//枚举，定义颜色
enum Color
{
	RED,//0
	BLACK,//1
};


//节点类
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	//AVL树的平衡因子，在红黑树中为颜色
	Color _col;
	//插入节点的时候，默认为红色
	//因为这个满足性质3且不会破坏性质4
	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv),
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_col(RED)
	{}
};
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

2.2 插入的几种情况

节点设计好了，我们只需要把插入的逻辑搞定，那么红黑树也就完成了！

前半部分的代码和AVL树完全相同，只不过我们需要手动给根节点一个黑色（默认是红色）以维持性质2

	bool Insert(const pair<K, V>& kv)
	{
		//判断root为空，即空树
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;//这里必须要手动给黑色
			return true;
		}
		//kv树的操作
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			//利用key来判断，寻找待插入的位置
			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;
        //调整
        //……
   }
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

2.2.1 情况1：无需旋转

在下面的这种情况中，我们在p的左边插入了一个cur新节点。此时违反了性质3，红节点的孩子必须要是黑节点。

这种情况必须满足p和u都是红节点

随后我们就需要开始向上进行更新，操作如下：

• 把p和u都改成黑节点
• 把g改成红节点

修改之后的结果如下，即不影响性质3；也保证了黑节点的个数不变，维持了性质4

需要注意的是，这里的g不一定是根节点。所以在操作完这一课子树之后，我们需要继续向上进行操作，避免g的父节点是红色的情况。

代码实现如下（以父节点为g的左子树为例）

//插入之后需要向上更新颜色,只有出现连续红色之后才需要更新
while (parent && parent->_col==RED)
{
    //p是g的左
    if (parent == grandpa->_left)
    {
        Node* uncle = grandpa->_right;
        //情况1：插入后p是红，u存在且是红（不需要旋转）
        if (uncle && uncle->_col == RED)
        {
            uncle->_col = BLACK;
            parent->_col = BLACK;
            grandpa->_col = RED;//祖父变成红
            //继续向上调整
            //cur = cur->_parent;
            //parent = parent->_parent;
            cur = grandpa;
            parent = cur->_parent;
        }
    }
    else{
        //....
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

需要注意的是，这种调整会把g改成红节点。如果G是根节点，改成红色之后就不符合性质了。所以我们需要在操作完成之后，统一把根节点改成黑色

//不管是什么情况，最后都把根改成黑，符合条件2
_root->_col = BLACK;
1
2

2.2.2 情况2：需要单旋

当我们插入了一个cur向上更新的时候，就可能会遇到下图中间的情况。p是红节点，违反了性质3，而u是黑节点，不能简单粗暴的通过把p改成红来解决。

这时候我们就需要针对g进行一次单旋（图中是右单旋，可以简单理解为向u旋转）。因为cur和p形成了同侧的连续两个红节点。和AVL树的单旋情况相似，只有这两节点在同侧，才可以执行单旋。

旋转完毕之后，需要把g更新为红节点，p更新为黑节点

2.2.3 情况3：需要双旋

在情况2中，p和cur都是在它们父亲的同一侧。而情况3就是p和cur在父亲的不同侧。

• 比如p是g的左子树，cur是p的右子树
• 同时满足p是红，u是黑

这时候就需要进行一次三旋，操作如下：

• 以p作为基点，向cur的另外一个方向单旋一次（上图中就是左旋）
• 旋转了之后，就会变成情况2
• 这时候再以g为基点，向u的方向旋转一次（上图中为右旋）
• 旋转完成之后，把g设置为红，cur设置为黑即可

一下是完整的三种情况代码（p是g的左子树的情况）

//p是g的左
if (parent == grandpa->_left)
{
    Node* uncle = grandpa->_right;
    //情况1：插入后p是红，u存在且是红（不需要旋转）
    if (uncle && uncle->_col == RED)
    {
        uncle->_col = BLACK;
        parent->_col = BLACK;
        grandpa->_col = RED;//祖父变成红
        //继续向上调整
        //cur = cur->_parent;
        //parent = parent->_parent;
        cur = grandpa;
        parent = cur->_parent;
    }
    else//(uncle && uncle->_col == BLACK)
    {
        //情况2：插入后p为红，u存在且为黑（需要单旋）
        if (cur == parent->_left)
        {
            RotateR(grandpa);//因为p在g的左边，所以右旋
            parent->_col = BLACK;
            grandpa->_col = RED;
        }
        else//cur == parent->_right
        {
            //情况3：不是在同一侧，双旋
            //   g
            // p
            //   c
            RotateL(parent);
            RotateR(grandpa);
            grandpa->_col = RED;//祖父改成红色
            cur->_col = BLACK;//自己成为了这里的根，需要改成黑的
        }
        break;
    }
}
else{
    //....
}
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

由于篇幅限制，p是g右子树的情况就不贴出来了，实际上就是把上面的代码全反过来就行了

完整代码请查看我的gitee仓库

2.3 查找（和AVL树完全相同）

	//因为kvl树我们需要修改value，所以返回节点的指针
	Node* _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return nullptr;

		if (root->_kv.first < key)
		{
			return _FindR(root->_right, key);
		}
		else if (root->_kv.first > key)
		{
			return _FindR(root->_left, key);
		}
		else
		{
			return root;
		}
	}
	//查找是通过key来进行的
	Node* FindR(const K& key)
	{
		return _FindR(_root, key);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.4 判断是否是红黑树

有两种方案，1是可以通过计算最大高度/最小高度进行间接判断，2是以红黑树性质来验证是否满足最上面提到的5点

2.4.1 计算最小最大高度

这里实现递归即可，最小长度其实就是在最后return的判断中，把大于号改成小于号，返回小的那个子树的高度+1

	int maxHeight(){
		return _maxHeight(_root);
	}
	int minHeight() {
		return _minHeight(_root);
	}

	//最大长度
	int _maxHeight(Node* root)
	{
		if (root == nullptr)
			return 0;

		int lh = _maxHeight(root->_left);
		int rh = _maxHeight(root->_right);

		return lh > rh ? lh + 1 : rh + 1;
	}
	//最小长度
	int _minHeight(Node* root)
	{
		if (root == nullptr)
			return 0;

		int lh = _minHeight(root->_left);
		int rh = _minHeight(root->_right);

		return lh < rh ? lh + 1 : rh + 1;
	}
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

只要最大长度小于最小长度的2倍，那么基本规则就是没有破坏的

但这还不够，我们还需要检查它是否满足红黑树的其余性质

2.4.2 递归检查性质

这里再次列出5点性质

1. 每一个节点不是红色就是黑色
2. 根节点一定是黑色
3. 每一个红节点的左右子树都是黑色
4. 每一个到叶子（空节点NIL）的支路上黑节点数量相同
5. 叶子节点（空节点NIL）视作黑色

然后通过两个函数来实现，其中一个函数需要进行递归

bool IsRBTree()
{
    //检查红黑树几条规则
    Node* pRoot = _root;
    //空树也是红黑树
    if (nullptr == pRoot)
        return true;

    //检测根节点是否满足情况2
    if (BLACK != pRoot->_col)
    {
        cout << "违反2：根节点必须为黑色" << endl;
        return false;
    }

    //获取任意一条路径中黑色节点的个数，作为基准值
    size_t blackCount = 0;
    Node* pCur = pRoot;
    while (pCur)
    {
        if (BLACK == pCur->_col)
            blackCount++;

        pCur = pCur->_left;
    }

    //检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
    size_t k = 0;
    return _IsValidRBTree(pRoot, k, blackCount);
}	
//检测是否为RB树
bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
{
    //走到null之后，判断k和black是否相等
    if (nullptr == pRoot)
    {
        if (k != blackCount)
        {
            cout << "违反4：每条路径中黑色节点的个数必须相同" << endl;
            return false;
        }
        return true;
    }

    //统计黑色节点的个数
    if (BLACK == pRoot->_col)
        k++;

    //检测当前节点与其双亲是否都为红色
    if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
    {
        cout << "违反3：存在连在一起的红色节点" << endl;
        return false;
    }

    return _IsValidRBTree(pRoot->_left, k, blackCount) &&
        _IsValidRBTree(pRoot->_right, k, 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

可以看到，不管是随机数还是顺序插入，都通过了检查

3.红黑树的运用

红黑树在很多地方都有使用，在C++中，最为经典的便是map和set这两个容器，它们便使用了红黑树作为底层逻辑

https://gitee.com/ewait/learn_cpp_code/blob/master/STL-Sourcecode/stl_tree.h

在stl源码中，我们可以找到这个tree.h，里面便是一个红黑树的实现。而map和set就是调用了红黑树，只做了一个简单的封装

结语

在下篇博客中，我会记录map和set的基本使用，以及通过红黑树模拟实现map和set

感谢大家支持！