【数据结构】6.5 红黑树（C++）_红黑树 中序遍历

【数据结构】——6.5 红黑树

没有学过二叉搜索树（也叫二叉排序树或二叉查找树）的小伙伴们建议先学习一下，这样阅读会更轻松哦 点我学习二叉搜索树

一、红黑树的概念和性质

红黑树是一种近似平衡的二叉搜索树，它有以下特点：

1. 每个节点只能是红色或黑色
2. 根节点为黑色
3. 红色节点的两个孩子必须是黑色
4. 对于每个节点，到所有叶子节点的路径中，经过的黑色节点数目是相同的。
5. 叶子节点的两个空指针孩子当作黑节点来看，它被称为NIL节点，在使用时我们也可以忽略它的存在。

红黑树这些规则有什么用呢？

1. 因为红色节点的孩子必须是黑色的，所以不可能存在2个连续的红色节点
2. 因为每个节点到低的每条路径黑色数目相同，且不存在2个连续的的红色节点，所以一条路径最短的情况是每个节点都是黑色节点，最长的情况是一黑一红相间的路径。
3. 因此最长的路径一定不会超过最短路径节点数的2倍，这保证了红黑树不会出现单支树的问题，在一定程度上确保了二叉搜索树的平衡性。

红黑树的最优情况：全为黑色节点或每条路径都是一黑一红

红黑树的最差情况：左子树全黑，右子树一黑一红

红黑树是一个近似平衡的搜索二叉树，它确保了没有一条路径会比其他路径长出2倍，解决了普通二叉搜索树因不平衡导致查找效率低的问题。

AVL树也是一颗近似平衡的二叉搜索树，它们有什么区别？

1. AVL树中左子树与右子树的高度差不能超过1，红黑树中最长路径不会超过最短路径的2倍。所以从平衡性来讲，AVL树比红黑树更加接近平衡，AVL树的查找效率比红黑树更高
2. 当插入节点时，AVL树中平衡因子超过2就要进行旋转，而红黑树中出现连续红色节点时才会旋转。这是红黑树的旋转次数比AVL树少，因此红黑树的插入效率比AVL树更高。同理，删除效率也比AVL树更高

虽然选择二叉搜索树作为数据结构去使用是因为它高效率的查找效率，但是在我们经常使用的一些容器中，插入和删除也是我们频繁使用的接口，因此在实际应用中，红黑树的应用比AVL树更广泛。但是对于一些特定场合，使用AVL树也是更不错的选择。

二、红黑树的存储结构和声明

1. 红黑树的结构依然使用三叉链表来实现
2. 我们使用enum枚举类型来定义节点的红色和黑色
3. 我们只实现红黑树的插入，查找和中序遍历，并且提供一个函数检测我们的红黑树是否满足规则

namespace Name
{
    // 颜色定义
    enum Color
	{
		RED,
		BLACK
	};
    
    // 节点声明
    template <class K>
    struct RBTreeNode
    {
        K& _key;					// 键
        RBTreeNode<K> *_left;
        RBTreeNode<K> *_right;
        RBTreeNode<K> *_parent;
        Color _col;					// 颜色

        // 构造函数
        RBTreeNode(const K& key)
            : _key(key)
            , _left(nullptr)
            , _right(nullptr)
            , _parent(nullptr)
            , _col(RED)
        {
            ;
        }
    };
    
    // 红黑树的声明
    template <class K>
	class RBTree
	{
		typedef RBTreeNode<K> Node;		// 将节点类型重命名为Node
        
	public:
        bool Insert(const K& key);		// 插入
        bool Find(const K& key);		// 查找
        void InOrder(void);				// 中序遍历
        bool IsBalance(void);			// 检测是否满足红黑树规则
        
    private:
        Node* _root;	// 根节点指针
    };
}
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

三、红黑树的构建过程

红黑树通过不断插入元素，构成二叉搜索树，若是破坏了红黑树的规则，则对树进行调整，直到构成红黑树

插入的新节点该是什么颜色呢？

新创建的节点一定是红色，因为新节点是黑色会导致本条路径的黑色节点数量多出一个，破坏红黑树的规则。

插入步骤：

1. 按照二叉搜索树的规则，将新节点插入对应的位置，新节点为红色
2. 当父亲节点是黑色时，没有破坏红黑树的规则，插入结束
3. 当父亲节点是红色时，出现连续的红色，需要对红黑树进行调整，使之重新构成红黑树

当出现连续的红色节点时，当前节点为红色，父节点为红色，祖父节点一定为黑色，所以我们通过叔叔节点来判断当前红黑树的状况。

当新节点插入，父亲节点为红色时，叔叔节点只有2种情况：叔叔节点为红色或不存在

（1）叔叔节点为红色

当叔叔节点为红色时，需要将父亲节点和叔叔节点变成黑色，祖父节点变成红色，此时整颗子树每条路径的黑色节点仍然是一个，与其他路径的黑色节点数量一致。

当叔叔节点不存在时插入新节点，我们通过变色的方式调整为红黑树，此时子树的顶端被我们修改为了红色。

1. 若是子树的父节点为红色，那么就会出现连续的红色节点，我们需要继续向上调整
2. 若是子树的顶端就是根节点，那么根节点不能被修改为红色

对于根节点问题，我们可以判断子树顶端是否为根节点，如果是则不改变根节点的颜色。也可以在插入完成时将根节点的颜色改为黑色。我们采用第二种方案，因为不需要判断，写起来方便

向上调整时，叔叔节点一定存在，若是叔叔节点还是红色，则继续变色，直到调整到根节点或叔叔节点为黑色

红色方框的意思是，该节点为红色或不存在

（2）叔叔节点为黑色或不存在

当叔叔节点为黑色或者不存在时，需要对树的形状进行调整，调整的方式就是旋转。

根据此时树的形状，将旋转分为4类，分别是左单旋，右单旋，左右双旋，右左双旋

当旋转完毕后要对对应的节点进行变色

黑色方框代表节点为黑色或不存在

<1>右单旋：

1. p是g的左孩子，c是p的左孩子时，进行右单旋
2. 当旋转完毕后，将父节点变成黑色，当前节点和叔叔节点均为红色

右单旋的过程：

1. 让祖父节点g成为父节点p的右孩子
2. 若是父节点p有右孩子，则将其交给祖父节点p领养，成为p的左孩子。（图中p没有右孩子）
3. 此时父节点p在子树的最顶端，将其改为黑色。祖父节点g改为红色

代码实现

以下代码的实现与AVL树中的代码一样，只是没有平衡因子的更新。还有一个区别是这里的参数传递的是祖父节点，但是操作和AVL树中的父节点一样，可以理解成红黑树中的当前节点比AVL树中的矮一层

// 右单旋
void RotateR(Node* grandpa)
{
    Node* grandpa_p = grandpa->_parent;		// 祖父节点的父节点，用来连接旋转后的子树
    Node* parent = grandpa->_left;			// 父节点
    Node* rightSun = parent->_right;		// 父节点的右孩子

    // 链接孩子节点
    parent->_right = grandpa;
    grandpa->_left = rightSun;
    if (grandpa_p != nullptr)
    {
        // 祖父节点不为根节点
        if (grandpa_p->_left == grandpa)
        {
            grandpa_p->_left = parent;
        }
        else
        {
            grandpa_p->_right = parent;
        }
    }
    else
    {
        // 祖父节点为根节点
        _root = parent;
    }

    // 更新父节点
    parent->_parent = grandpa_p;
    grandpa->_parent = parent;
    if (rightSun != nullptr)
    {
        rightSun->_parent = grandpa;
    }
}
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

<2>左单旋

1. p是g的右孩子，c是p的右孩子时，进行左单旋
2. 当旋转完毕后，将父节点变成黑色，当前节点和叔叔节点均为红色

右单旋的过程：

1. 让祖父节点g成为父节点p的左孩子
2. 若是父节点p有左孩子，则将其交给祖父节点p领养，成为p的右孩子。（图中p没有左孩子）
3. 此时父节点p在子树的最顶端，将其改为黑色。祖父节点g改为红色

代码实现：

// 左单旋
void RotateL(Node* grandpa)
{
    Node* grandpa_p = grandpa->_parent;
    Node* parent = grandpa->_right;
    Node* leftSub = grandpa->_left;

    // 链接孩子节点
    grandpa->_left = grandpa;
    grandpa->_right = leftSub;
    if (grandpa_p != nullptr)
    {
        if (grandpa_p->_left == grandpa)
        {
            grandpa_p->_left = grandpa;
        }
        else
        {
            grandpa_p->_right = grandpa;
        }
    }
    else
    {
        _root = grandpa;
    }

    // 更新父节点
    grandpa->_parent = grandpa_p;
    grandpa->_parent = grandpa;
    if (leftSub != nullptr)
    {
        leftSub->_parent = grandpa;
    }
}
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

<3>左右双旋

1. p是g的左孩子，c是p的右孩子时，进行左右双旋。
2. 先以c节点为轴进行左单旋，再以旋转后的c节点为轴进行右单旋
3. 当旋转完毕后，将父节点变成黑色，当前节点和叔叔节点均为红色

由于红黑树的左右双旋和右左双旋可以直接调用左单旋和右单旋，并且最后只需要更新节点颜色，不需要多余的操作，我们就不将这两个封装成为一个单独的函数了，使用时直接展开书写即可。

<4>右左双旋

1. p是g的右孩子，c是p的左孩子时，进行右左双旋。
2. 先以c节点为轴进行右单旋，再以旋转后的c节点为轴进行左单旋
3. 当旋转完毕后，将父节点变成黑色，当前节点和叔叔节点均为红色

这4种旋转方式得到的结果都有一个共同点：

子树的顶端一定是黑色节点，不可能再出现两个连续的红色节点，不需要再向上调整了

四、红黑树的实现

1. 默认成员函数

（1）构造函数

根节点指针_root初始化为空指针即可

RBTree(void)
    : _root(nullptr)
{
    ;
}
1
2
3
4
5

（2）析构函数

后序遍历依次释放每个节点，由于要使用递归，参数要传递节点指针，因此我们将递归过程单独封装成为一个函数，让析构函数调用它

// 析构函数
~RBTree(void)
{
    _Destroy(_root);
    _root = nullptr;
}

private:
// 后序遍历释放节点
void _Destroy(Node* root)
{
    if (root == nullptr)
    {
        return;
    }

    _Destroy(root->_left);
    _Destroy(root->_right);
    delete root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（3）拷贝构造

先序遍历依次拷贝每个节点，也将递归过程单独封装为一个函数

// 拷贝构造
RBTree(const AVLTree& t)
{
    _root = _Copy(_root, t._root);
}

private:
// 先序遍历递归拷贝节点
Node* _Copy(Node* root, const Node* src)
{
    if (src == nullptr)
    {
        return nullptr;
    }

    root = new Node(src->_key);
    root->_left = _Copy(root->_left, src->_left);
    root->_right = _Copy(root->_right, src->_right);
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（4）赋值重载

创建临时对象拷贝用来赋值的对象，然后交换自己和它的根节点指针内容，获取临时对象的数据。

// 赋值重载函数
RTree& operator=(const AVLTree& t)
{
    if (this != &t)
    {
        BSTree temp(t);
        std::swap(temp._root, _root);
    }
    return *this;
}
1
2
3
4
5
6
7
8
9
10

2. 插入Insert

红黑树插入元素的步骤：

1. 根据二叉搜索树规则将新节点插入到对应的位置
2. 判断新节点的父节点为黑色，则插入完毕
3. 如果新节点的父节点为红色，则根据它的叔叔节点做出相应的调整

bool Insert(const pair<K, V>& kv)
{
    // 1.以二叉搜索树的方式插入新节点
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;		// 根节点为黑色
        return true;
    }

    Node *cur = _root, *parent = nullptr;
    while (cur != nullptr)
    {
        if (kv.first < cur->_kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (kv.first > cur->_kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return false;
        }
    }

    cur = new Node(kv);
    if (kv.first < parent->_kv.first)
    {
        parent->_left = cur;
        cur->_parent = parent;
    }
    else
    {
        parent->_right = cur;
        cur->_parent = parent;
    }
    
    // 2.调整为红黑树
    while (parent != nullptr && parent->_col == RED)
    {
        Node* grandpa = parent->_parent;	// 红色节点一定有父亲，所以不用担心空指针
        Node* uncle = grandpa->_left;		// 获取叔叔节点
        if (parent == uncle)
        {
            uncle = grandpa->_right;
        }

        if (uncle != nullptr && uncle->_col == RED)
        {
            // 叔叔节点为红：变色
            parent->_col = BLACK;
            uncle->_col = BLACK;
            grandpa->_col = RED;

            cur = grandpa;
            parent = cur->_parent;
        }
        else
        {
            // 叔叔节点为黑或不存在：旋转+变色
            if (parent == grandpa->_left && cur == parent->_left)
            {
                // 右单旋
                RotateR(grandpa);
                // 变色
                parent->_col = BLACK;
                grandpa->_col = RED;
            }
            else if (parent == grandpa->_right && cur == parent->_right)
            {
                // 左单旋
                RotateL(grandpa);
                // 变色
                parent->_col = BLACK;
                grandpa->_col = RED;
            }
            else if (parent == grandpa->_left && cur == parent->_right)
            {
                // 左右双旋
                RotateL(parent);
                RotateR(grandpa);
                // 变色
                cur->_col = BLACK;
                grandpa->_col = RED;
            }
            else if (parent == grandpa->_right && cur == parent->_left)
            {
                // 右左双旋
                RotateR(parent);
                RotateL(grandpa);
                // 变色
                cur->_col = BLACK;
                grandpa->_col = RED;
            }
            else
            {
                assert(false);		// 不会出现的情况，使用断言处理
            }

            break;	// 旋转之后，顶一定是黑，不需要再判断连续红节点了
        }
    }
    
    _root->_col = BLACK;	// 将根节点置为黑色
    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

3. 查找Find

就是二叉搜索树的查找方式进行查找

bool Find(const K& key)
{
    Node* cur = _root;
    while (cur != nullptr)
    {
        if (key < cur->_key)
        {
            // 比当前节点小，往左走
            cur = cur->_left;
        }
        else if (key > cur->_key)
        {
            // 比当前节点大，往右走
            cur = cur->_right;
        }
        else
        {
            // 与当前节点相等，返回true
            return true;
        }
    }

    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4. 中序遍历

递归实现中序遍历

// 中序遍历
void InOrder(void)
{
    _InOrder(_root);
    std::cout << std::endl;
}

// 中序遍历的递归过程
void _InOrder(Node* root)
{
    if (root == nullptr)
    {
        return;
    }

    _InOrder(root->_left);
    std::cout << root->_key << " ";
    _InOrder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5. 检查是否构成红黑树

1. 先检查空树是红黑树，再判断根节点是否为红色
2. 为了对比每条路径上的黑色节点数量，我们先获取最左边路径的黑色根节点数量作为参考。若是每条路径的黑色根节点数量与黑色根节点数量一样，则满足红黑树的规则
3. 使用递归遍历每个节点，并判断是否存在连续的节点

bool IsBalance(void)
{
    // 空树是红黑树
    if (_root == nullptr)
    {
        return true;
    }

    // 根节点为红色不是红黑树
    if (_root->_col != BLACK)
    {
        return false;
    }

    // 获取最左边路径的黑色节点数目
    int ref = 0;
    Node* left = _root;
    while (left != nullptr)
    {
        if (left->_col == BLACK)
        {
            ++ref;
        }
        left = left->_left;
    }

    return _IsBalance(_root, 0, ref);
}

private:
// 递归遍历节点，并判断是否满足红黑树的规则
bool _IsBalance(const Node* root, int blackNum, const int ref) const
{
    if (root == nullptr)
    {
        if (blackNum != ref)
        {
            cout << "路径黑色节点数跟最左路径不相等" << endl;
            return false;
        }
        return true;
    }

    // 判断是否有连续红色节点
    if (root->_col == RED && root->_parent->_col == RED)	// 红色节点一定有父亲，不担心空指针问题
    {
        cout << "error : " << root->_kv.first << " and " << root->_parent->_kv.first << endl;
        return false;
    }

    if (root->_col == BLACK)
    {
        ++blackNum;
    }

    return _isBalance(root->_left, blackNum, ref) 
        && _isBalance(root->_right, blackNum, ref);
}
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