【C++】红黑树的性质和实现
慕雪年华
  2022-09-04 18:50:46 2022-09-04 18:50   2023-04-03 09:23:39    3k 字  

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

使用的编译器：VS2019

[TOC]

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

1.概念

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

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

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

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

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

image

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且较难修复。

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
//枚举，定义颜色
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)
	{}
};

2.2 插入的几种情况

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

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

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
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;
       //调整
       //……
  }

2.2.1 情况1：无需旋转

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

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

image

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

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

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

image

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

image

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//插入之后需要向上更新颜色,只有出现连续红色之后才需要更新
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{
        //....
    }
}

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

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

2.2.2 情况2：需要单旋

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

image

这时候我们就需要针对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设置为黑即可

image

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

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的左
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{
    //....
}

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//因为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);
}

2.4 判断是否是红黑树

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

2.4.1 计算最小最大高度

这里实现递归即可，最小长度其实就是在最后return的判断中，把大于号改成小于号，返回小的那个子树的高度+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
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;
}

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

image

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

2.4.2 递归检查性质

这里再次列出5点性质

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

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

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

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

image

3.红黑树的运用

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

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

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

结语

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

感谢大家支持！

  • 本文标题：【C++】红黑树的性质和实现
  • 本文作者：慕雪年华
  • 创建时间：2022-09-04 18:50:46
  • 本文链接：posts/3503649261/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
  1. 1.概念
    1. 1.1 性质
  2. 2.设计一颗红黑树
    1. 2.1 设计节点
    2. 2.2 插入的几种情况
      1. 2.2.1 情况1：无需旋转
      2. 2.2.2 情况2：需要单旋
      3. 2.2.3 情况3：需要双旋
    3. 2.3 查找（和AVL树完全相同）
    4. 2.4 判断是否是红黑树
      1. 2.4.1 计算最小最大高度
      2. 2.4.2 递归检查性质
    5. 3.红黑树的运用
    6. 结语