[C++](20)红黑树，调整规则图解，插入功能代码实现

文章目录

概念
框架
插入
- 按搜索树规则插入
- 调整
总结
测试
完整代码

概念

在计算机科学中，红黑树是一种自平衡的二叉搜索树。每个结点都增加了一个代表 “颜色”（"红色 "或 “黑色”）的额外存储位，用于确保树在插入和删除时保持平衡。

通过对各个结点着色方式的限制，红黑树确保从根到空结点（NIL结点）的最长的可能路径长度不多于最短的可能路径的两倍。所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低，其平均统计性能要强于 AVL 。

红黑树的性质：

每个结点不是红色就是黑色
根结点是黑色
如果一个结点是红色，则它的两个孩子结点是黑色（没有连续的红色结点）
从一个给定的节点到其任何一个后代 NIL 结点的每条路径都要经过相同数量的黑色结点。
NIL 结点都是黑色

为什么满足上面的性质，就能保证从根到叶子的最长路径长度不会超过最短路径的 2 倍？

是性质 3 和性质 4 确保了这个结果，一棵红黑树从根到 NIL 结点的所有路径上的黑色结点数是相等的，其中一条最短可能路径一定都是黑色，最长路径要保证尽可能长，在性质3的前提下只能在中间间隔式地插入红色结点，其最长的可能长度也不会超过最短可能长度的 2 倍。

框架

enum Colour
{
	RED,
	BLACK
};

template
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	pair _kv;

	Colour _col;

    RBTreeNode(const pair& kv)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _col(RED)
    {}
};

template
struct RBTree
{
	typedef RBTreeNode Node;
public:

private:
	Node* _root;
};

插入按搜索树规则插入

bool Insert(const pair& 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);
    cur->_col = RED; // 新结点初始颜色为红，易于维护
    if (parent->_kv.first < kv.first)
        parent->_right = cur;
    else
        parent->_left = cur;
    cur->_parent = parent;
    
    //...
    
    return true;
}

我们的新结点先染为红色，因为插入红色对性质 3 可能有影响，对性质 4 没有影响，且性质 3 比性质 4 易于维护。

调整

当通过搜索树规则找到要插入的位置时，该位置的父结点有可能是红，也可能是黑。如果是黑，即未破坏性质 3 ，不用调整。

如果父结点是红，则需要调整：

父结点是红，红结点一定不是根，所以一定还有祖父结点，且祖父结点一定是黑，所以这三个结点的情况是固定的。那么关键看叔叔结点。

下面 cur 为当前结点，p 为父结点，g 为祖父结点，u 为叔叔结点

情况一：cur 为红，p 为红，g 为黑，u 存在且为红

解决方案：p 和 u 设为黑，g 设为红。如果 g 是根结点，那么 g 直接设为黑，否则 g 设为 cur 继续向上调整。

因为要保持一条路径的黑色结点个数不变，所以最好把 p 改成红色，g 改成黑色，同时 u 要改成黑色，调整完看 g 是不是根结点，如果不是还要继续向上调，因为上面可能还有连续红色结点。

小三角表示子树，表示 cur 可能是新插入的结点（子树高度为 0），也可能是从下面调整上来的。

上图仅为p左u右的情况，其镜像同理：

//...

// 有父亲，且父亲为红才处理
while (parent && parent->_col == RED)
{
    Node* grandfather = parent->_parent;
    if (parent == grandfather->_left)
    {
        Node* uncle = grandfather->_right;
        // 情况一
        if (uncle && uncle->_col == RED)
        {
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            // 继续向上处理
            cur = grandfather;
            parent = cur->_parent;
        }
        else
        {
			//...
            
        }
    }
    else
    {
        Node* uncle = grandfather->_left;
        // 情况一
        if (uncle && uncle->_col == RED)
        {
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            // 继续向上处理
            cur = grandfather;
            parent = cur->_parent;
        }
        else
        {
			//...
        }
    }
}
_root->_col = BLACK; // 不废话，根直接设为黑色

//...

情况二：cur 为红，p 为红，g 为黑，u 不存在/u 存在且为黑，cur 在 p 的外侧

如图，因为插入新结点前就应该满足红黑树，所以如果 u 不存在，那么 g 到 NIL 的每条路径的黑色结点个数一定是 2，所以插入前 g 的左路径只可能是 g-p-NIL，要获得连续红结点，cur 只能是新插入的结点。因为没有子树，所以没画小三角。

如果 u 存在且为黑，那么 g 到 NIL 的每条路径至少有 3 个黑色结点，如果 cur 是新插入的结点，那么插入前 g-p-NIL 路径只有 2 个黑色结点，与插入前满足红黑树的条件矛盾，所以 cur 一定是下面的子树新增结点之后通过情况一调整上来的。

解决方案：旋转 + 变色：以 g 为旋转点进行旋转，然后 p 变为黑色，g 变为红色。结束后 p 作为该子树的根结点，为黑色，不需要再向上调整。

此时仅仅通过变色无法满足要求了，所以要先旋转，旋转后，p 是新的根结点，但是 p 的左路径少了一个黑色，所以我们将 p 变黑，这样一来 p 的右路径又多了一个黑色，所以我们将 g 变红，最后保证了各路径的黑色结点数不变。

上图仅为 p 在 g 左边的情况，如果 p 在右边则需要右旋，注意旋转方向，旋转的处理和AVL树一样，具体参见博文：AVL树插入，旋转，详细图解与代码

//...父亲在左，叔叔在右

else // 情况二：叔叔不存在或叔叔存在且为黑
{
    if (cur == parent->_left)
    {
        RotateR(grandfather);
        parent->_col = BLACK;
        grandfather->_col = RED;
    }
    break;
}

//...叔叔在左，父亲在右

else // 情况二：叔叔不存在或叔叔存在且为黑
{
    if (cur == parent->_right)
    {
        RotateL(grandfather);
        parent->_col = BLACK;
        grandfather->_col = RED;
    }
    break;
}

//...

private:
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL) subRL->_parent = parent; // subRL有可能是空树，需要if判断

        Node* ppNode = parent->_parent; // 提前记录祖先，后面用来连接新的parent
        subR->_left = parent;
        parent->_parent = subR;

        if (parent == _root) // 如果parent就是根结点，那么新的根是subR
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else // 否则需要祖先来连接新的parent(即subR)，注意判断左右
        {
            if (parent == ppNode->_left)
            {
                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;

        Node* ppNode = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;

        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (parent == ppNode->_left)
            {
                ppNode->_left = subL;
            }
            else
            {
                ppNode->_right = subL;
            }
            subL->_parent = ppNode;
        }
    }

情况三：cur 为红，p 为红，g 为黑，u 不存在/u 存在且为黑，cur 在 p 的内侧

解决方案：和情况二类似，不同点是要进行双旋+变色：先对 p 左/右旋，然后对 g 右/左旋，最后 cur 和 g 变色

第一次旋转对性质 4 没有造成影响，不用变色，第二次旋转和情况二的旋转一样，需要对 g 和 cur 这两个旋转点变色。

//...父亲在左，叔叔在右

else // 情况二：叔叔不存在或叔叔存在且为黑
{
    if (cur == parent->_left) // 左左：右旋
    {
        RotateR(grandfather);
        parent->_col = BLACK;
        grandfather->_col = RED;
    }
    else // 左右：左右双旋
    {
        RotateL(parent);
        RotateR(grandfather);
        cur->_col = BLACK;
        grandfather->_col = RED;
    }
    break;
}

//...叔叔在左，父亲在右

else // 情况二：叔叔不存在或叔叔存在且为黑
{
    if (cur == parent->_right) // 右右：左旋
    {
        RotateL(grandfather);
        parent->_col = BLACK;
        grandfather->_col = RED;
    }
    else // 右左：右左双旋
    {
        RotateR(parent);
        RotateL(grandfather);
        cur->_col = BLACK;
        grandfather->_col = RED;
    }
    break;
}

//...

总结

关键看叔叔：

叔叔存在且为红，情况一，只需要变色。但仍需向上调整
叔叔不存在或存在且为黑，旋转+变色，旋转变色完成，符合红黑树性质，不再影响上层，处理结束。
- 旋转遵循AVL树的规则：左左：右旋，右右：左旋，左右：左右双旋，右左：右左双旋
- 单旋与双旋分别为情况二和情况三

测试

通过层序遍历和中序遍历直观感受：

public:
	void LevelOrder()
    {
        queue que;
        if (_root != NULL) que.push(_root);
        while (!que.empty())
        {
            int size = que.size();
            for (int i = 0; i < size; i++)
            {
                Node* node = que.front();
                que.pop();
                cout << node->_kv.first << ' ';
                if (node->_left) que.push(node->_left);
                if (node->_right) que.push(node->_right);
            }
            cout << endl;
        }
    }

    void Inorder()
    {
        _Inorder(_root);
        cout << endl;
    }

private:
    void _Inorder(Node* root)
    {
        if (root == nullptr) return;
        _Inorder(root->_left);
        cout << root->_kv.first << ' ';
        _Inorder(root->_right);
    }

顺序插入0-99：

void testRBTree1()
{
	const int N = 100;
	RBTree t{};
	for (int i = 0; i < N; ++i)
	{
		t.Insert(make_pair(i, 0));
	}
	t.LevelOrder();
	t.Inorder();
}

计算最长路径和最短路径

public:
	void Height()
    {
        cout << "最长路径：" << _MaxHeight(_root) << endl;
        cout << "最短路径：" << _MinHeight(_root) << endl;
    }
private:
    int _MaxHeight(Node* root)
    {
        if (root == nullptr) return 0;
        int leftHeight = _MaxHeight(root->_left);
        int rightHeight = _MaxHeight(root->_right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    int _MinHeight(Node* root)
    {
        if (root == nullptr) return 0;
        int leftHeight = _MinHeight(root->_left);
        int rightHeight = _MinHeight(root->_right);
        return leftHeight < rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

插入随机值：

void testRBTree2()
{
	const int N = 100;
	vector v;
	v.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		v.push_back(rand());
	}
	RBTree t{};
	for (auto e : v)
	{
		t.Insert(make_pair(e, 0));
	}
	t.LevelOrder();
	cout << endl;
	t.Inorder();
	cout << endl;
	t.Height();
}

结果没问题。

但是这还不足以说明我们写的就是红黑树，下面写一个验证规则：

public:
	bool IsRBTree()
    {
        if (_root == nullptr) return true; // 空树也是红黑树

        if (_root->_col != BLACK) // 检查根结点
        {
            cout << "错误：根结点不为黑色" << endl;
            return false;
        }

        // 获取任一条路径的黑色结点的个数，作为比较的基准值
        size_t blackCount = 0;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_col == BLACK) ++blackCount;
            cur = cur->_left;
        }

        // 检查是否满足红黑树的性质，k用来记录路径中黑色结点的个数
        size_t k = 0;
        return _IsRBTree(_root, k, blackCount);
    }

private:
    bool _IsRBTree(Node* root, size_t k, const size_t blackCount)
    {
        // 走到空，判断黑色结点个数和基准值是否相等
        if (root == nullptr)
        {
            if (k != blackCount)
            {
                cout << "错误：每条路径中黑色结点的个数不同" << endl;
                return false;
            }
            return true;
        }

        if (root->_col == BLACK) ++k;
        
        // 检查是否有连续的红色结点
        Node* parent = root->_parent;
        if (parent && parent->_col == RED && root->_col == RED)
        {
            cout << "错误：有连续的红结点" << endl;
            return false;
        }

        return _IsRBTree(root->_left, k, blackCount) && _IsRBTree(root->_right, k, blackCount);
    }

插入1000000个随机数：

void testRBTree3()
{
	const int N = 1000000;
	vector v;
	v.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		v.push_back(rand());
	}
	RBTree t{};
	for (auto e : v)
	{
		t.Insert(make_pair(e, 0));
	}
	//t.LevelOrder();
	//cout << endl;
	//t.Inorder();
	//cout << endl;
	t.Height();
	cout << t.IsRBTree();
}

完整代码

#pragma once
#include 
#include 
using namespace std;

enum Colour
{
	RED,
	BLACK
};

template
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	pair _kv;

	Colour _col;

    RBTreeNode(const pair& kv)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _col(RED)
    {}
};

template
struct RBTree
{
	typedef RBTreeNode Node;
public:
    bool Insert(const pair& 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);
        cur->_col = RED; // 新结点初始颜色为红，易于维护
        if (parent->_kv.first < kv.first)
            parent->_right = cur;
        else
            parent->_left = cur;
        cur->_parent = parent;

        // 有父亲，且父亲为红才处理
        while (parent && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            if (parent == grandfather->_left) // 父亲在左，叔叔在右
            {
                Node* uncle = grandfather->_right;
                // 情况一
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    // 继续向上处理
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else // 情况二：叔叔不存在或叔叔存在且为黑
                {
                    if (cur == parent->_left) // 左左：右旋
                    {
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else // 左右：左右双旋
                    {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
            else // 叔叔在左，父亲在右
            {
                Node* uncle = grandfather->_left;
                // 情况一：叔叔存在且为红
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    // 继续向上处理
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else // 情况二：叔叔不存在或叔叔存在且为黑
                {
                    if (cur == parent->_right) // 右右：左旋
                    {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else // 右左：右左双旋
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }

        _root->_col = BLACK; // 不废话，根直接设为黑色
        return true;
    }

    void LevelOrder()
    {
        queue que;
        if (_root != NULL) que.push(_root);
        while (!que.empty())
        {
            int size = que.size();
            for (int i = 0; i < size; i++)
            {
                Node* node = que.front();
                que.pop();
                cout << node->_kv.first << ' ';
                if (node->_left) que.push(node->_left);
                if (node->_right) que.push(node->_right);
            }
            cout << endl;
        }
    }

    void Inorder()
    {
        _Inorder(_root);
        cout << endl;
    }

    void Height()
    {
        cout << "最长路径：" << _MaxHeight(_root) << endl;
        cout << "最短路径：" << _MinHeight(_root) << endl;
    }

    bool IsRBTree()
    {
        if (_root == nullptr) return true; // 空树也是红黑树

        if (_root->_col != BLACK) // 检查根结点
        {
            cout << "错误：根结点不为黑色" << endl;
            return false;
        }

        // 获取任一条路径的黑色结点的个数，作为比较的基准值
        size_t blackCount = 0;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_col == BLACK) ++blackCount;
            cur = cur->_left;
        }

        // 检查是否满足红黑树的性质，k用来记录路径中黑色结点的个数
        size_t k = 0;
        return _IsRBTree(_root, k, blackCount);
    }

private:
    bool _IsRBTree(Node* root, size_t k, const size_t blackCount)
    {
        // 走到空，判断黑色结点个数和基准值是否相等
        if (root == nullptr)
        {
            if (k != blackCount)
            {
                cout << "错误：每条路径中黑色结点的个数不同" << endl;
                return false;
            }
            return true;
        }

        if (root->_col == BLACK) ++k;
        
        // 检查是否有连续的红色结点
        Node* parent = root->_parent;
        if (parent && parent->_col == RED && root->_col == RED)
        {
            cout << "错误：有连续的红结点" << endl;
            return false;
        }

        return _IsRBTree(root->_left, k, blackCount) && _IsRBTree(root->_right, k, blackCount);
    }

    void _Inorder(Node* root)
    {
        if (root == nullptr) return;
        _Inorder(root->_left);
        cout << root->_kv.first << ' ';
        _Inorder(root->_right);
    }

    int _MaxHeight(Node* root)
    {
        if (root == nullptr) return 0;
        int leftHeight = _MaxHeight(root->_left);
        int rightHeight = _MaxHeight(root->_right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    int _MinHeight(Node* root)
    {
        if (root == nullptr) return 0;
        int leftHeight = _MinHeight(root->_left);
        int rightHeight = _MinHeight(root->_right);
        return leftHeight < rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL) subRL->_parent = parent; // subRL有可能是空树，需要if判断

        Node* ppNode = parent->_parent; // 提前记录祖先，后面用来连接新的parent
        subR->_left = parent;
        parent->_parent = subR;

        if (parent == _root) // 如果parent就是根结点，那么新的根是subR
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else // 否则需要祖先来连接新的parent(即subR)，注意判断左右
        {
            if (parent == ppNode->_left)
            {
                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;

        Node* ppNode = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;

        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (parent == ppNode->_left)
            {
                ppNode->_left = subL;
            }
            else
            {
                ppNode->_right = subL;
            }
            subL->_parent = ppNode;
        }
    }

private:
	Node* _root;
};

[C++](20)红黑树，调整规则图解，插入功能代码实现

C/C++/C#相关栏目本月热门文章