Red-Black Tree

高阶数据结构
发布日期:   2022-09-03

BingWallpaper27

[toc]

RB-tree

image-20220520090154798

0.Intro

红黑树是一种自平衡二叉搜索树。每个节点存储一个表示“颜色”（“红色”或“黑色”）的额外位，用于确保树在插入和删除期间保持平衡。当树被修改时，新树被重新排列并“重新绘制”以恢复限制树在最坏情况下可能变得多么不平衡的着色属性。这些属性被设计成可以有效地执行这种重新排列和重新着色。

From https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

image-20220504210510276

1. Red-Black Tree

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，==红黑树确保没有一条路径会比其他路径长出两倍==，因而是接近平衡的。接近平衡其实比平衡更好一点，因为相对平衡对于计算机来说实际上差别不大（对计算机来说其实logN和2logN差别不是很大），但是严格平衡是通过不断旋转来提高效率的，基于这样的原因，红黑树效率不必AVL差，但是反而旋转更少，因此总体效率更优，因此现在使用红黑树更多一点，而不是AVL树

1.1 红黑树的性质

🍁 每个结点不是红色就是黑色
🍁 根节点是黑色的
🍁 如果一个节点是红色的，则它的两个孩子结点是黑色的(没有连续的红色节点)
🍁 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（每条路上包含相同数量黑色节点）

每个叶子结点都是黑色的(==此处的叶子结点指的是空结点/NIL==)

image-20220505123105834

1.2 红黑树推论

🐉 路径：
⚡最短路径：全部由黑色节点构成
⚡最长路径：一黑一红，黑色节点数量等于红色节点
🐉 假设黑色节点有N个：
⚡最短路径长度：logN
⚡最长路径长度：2logN

2. 实现红黑树

2.0 红黑树节点结构

enum Color
{
    RED,
    BLACK,
};

template<class K,class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    pair<K, V> _kv;
    Color _col;

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

这时候我们有一个问题，为什么要将节点的默认颜色给成红色的？

黑的好还是红的好?

插入红的会破坏规则：

🍁 如果一个节点是红色的，则它的两个孩子结点是黑色的(没有连续的红色节点)

插入黑的会破坏规则：

🍁 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（每条路上包含相同数量黑色节点）

我们选择消耗低的，还是插入默认红的比较好

2.1 构造函数

RBTree()
:_root(nullptr)
	{}

2.2 Insert

2.2.0 处理搜索部分

搜索树部分类似于AVL和BSTree的插入逻辑

//空树
if (_root==nullptr)
{
    _root = new Node(data);
    _root->_col = BLACK;//根必须是黑的
    return make_pair(_root, true);
} 

Node* parent = nullptr;
Node* cur = _root;

//1. 找适当的空位置
while (cur)
{
    if (cur->_kv.first<data.first)
    {
        parent = cur;
        cur = cur->_right;
    }
    else if (cur->_kv.first<data.first)
    {
        parent = cur;
        cur = cur->_left;
    }
    else
    {//重复
        return make_pair(cur, false);
    }
}

//2. cur走到空 可以链接
Node* newnode = new Node(data);
newnode->_col = RED;

if (parent->_kv.first <data.first)
{
    parent->_right = newnode;
    newnode->_parent = parent;
}
else
{
    parent->_left = newnode;
    newnode->_parent = parent;
}
cur = newnode;
//处理
    
    return make_pair(kv, true);
}

关键是处理红黑节点

2.2.1 处理红黑节点

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不
需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此
时需要对红黑树分情况来讨论：

parent.color 条件 处理
BLACK 不需要调整 插入完成
RED 违反规则3 需要处理

如果parent节点是红的，那么就会出现多种情况，需要处理，情况1可以通变色处理，但是情况2+3则因为最长路径已经超过最短路径的两倍所以无法变色解决，需要旋转

下面的图中我们约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况 cur parent grandparent uncle 处理方案
情况一：
叔叔存在且为红		 RED RED BLACK exist && RED pu变黑，g变红，继续往上走
情况二:
叔叔不存在或为黑（直线）		 RED RED BLACK !exist ||
exist && BLACK		 单旋转+变色
情况三;
叔叔不存在或为黑（折线）		 RED RED BLACK !exist ||
exist && BLACK		 双旋转+变色

2.2.2 Situation1

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

image-20220505132556579

具象图 描述 操作
具象图1： g已经到顶了 pu变黑，g变红
具象图2： 符合具象图1但是修改完其他节点不符合 不断执行情况1，直到parent为空时，p存在且为黑，或者p不存在停止（把根变黑）

image-20220505132610350

image-20220505135120634

2.2.3 Situation2

🍁 情况二: cur为红，p为红，g为黑，u不存在/u为黑
情况二中，无非是还会出现一种情况是左旋，但是说到底都是单旋转中的一种,关键在于

parent/grandparent/cur关系 旋转操作 变色操作
p为g的左孩子，cur为p的左孩子 右单旋转 p、g变色–p变黑，g变红
p为g的右孩子，cur为p的右孩子 左单旋转 p、g变色–p变黑，g变红

⚡ 为什么不能直接染色?

看到下图可能会有一些疑问：为什么我不能把p变黑，g变红，简单来就可以了，还要搞什么旋转呢？这是因为首先原来插入之前是一棵红黑树，那么右路如果有uncle就是需要整一条右路上要两个黑节点才能满足规则五，如果没有uncle节点就要满足至少有一个黑，所以说如果直接改变颜色，那么会导致要么右路只有一个黑节点，要么就是右路干脆没有黑节点，所以说一定要采取旋转方式，才能满足规则五

具象图（以右单旋为例） 描述 操作
具象图1： `uncle !exist
具象图2： 符合情况一且处理之后产生情况二 处理情况一+右单旋+p变黑，g变红

image-20220506095327691

image-20220506103556352

2.2.4 Situation3

🍁 情况三: cur为红，p为红，g为黑，u不存在/u为黑

情况三看上去好像和情况二很像，其实差别在于情况三的结构，同时他是一个双旋

parent/grandparent/cur关系 旋转操作1 旋转操作2 变色操作
p为g的左孩子，cur为p的右孩子 左单旋转 右单旋转 cur、g变色–cur变黑，g变红
p为g的右孩子，cur为p的左孩子 右单旋转 左单旋转 cur、g变色–cur变黑，g变红

image-20220507140351911

具象图（以右单旋为例） 描述 操作
具象图1： `uncle !exist
具象图2： 符合情况一且处理之后产生情况三 处理情况一+左单旋+右单旋+cur变黑，g变红

image-20220506103931331

image-20220506110459705

2.2.5 分类讨论总结

插入一个新节点，新节点必是红的

image-20220507210143404

2.2.6 实现插入

2.2.6.1 插入本体
//插入
pair<Node*, bool> Insert(const pair<K, V>& data)
{
    //空树
    if (_root==nullptr)
    {
        _root = new Node(data);
        _root->_col = BLACK;//根必须是黑的
        return make_pair(_root, true);
    } 

    Node* parent = nullptr;
    Node* cur = _root;

    //1. 找适当的空位置
    while (cur)
    {
        if (cur->_kv.first<data.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first>data.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {//重复
            return make_pair(cur, false);
        }
    }

    //2. cur走到空 可以链接
    Node* newnode = new Node(data);
    newnode->_col = RED;

    if (parent->_kv.first <data.first)
    {
        parent->_right = newnode;
        newnode->_parent = parent;
    }
    else
    {
        parent->_left = newnode;
        newnode->_parent = parent;
    }
    cur = newnode;

    //3.判断处理条件
    //如果父亲存在，且颜色为红色就需要处理
    while (parent && parent->_col == RED)
    {	
        //抓住叔叔是关键
        Node* grandfather = parent->_parent;
    //a. 首先父亲在祖父左边的情况
        if (parent==grandfather->_left)
        {
            Node* uncle = grandfather->_right;
            //情况1：uncle 存在且为红
            if (uncle && uncle->_col ==RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                //继续往上处理
                cur = grandfather;
                parent = cur->_parent;
            }

            //情况2+3 uncle不存在或者uncle存在且为黑
            else//此时变色无法处理
            {
                //情况2：单旋
                if (cur==parent->_left)
                {   //1. 右单旋
                    _Rotate_R(grandfather);
                    //2. 变色
                    grandfather->_col = RED;
                    parent->_col = BLACK;
                } 
                else//情况3：双旋
                {
                    _Rotate_L(parent);
                    _Rotate_R(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;//根是黑的了，不会往上影响直接break
            }
        } 

        //b. 首先父亲在祖父左边的情况
        else//parent == grandfather->_right
        {
            Node* uncle = grandfather->_left;
            //情况1：uncle 存在且为红 
            if (uncle && uncle->_col==RED)
            {
                uncle->_col=parent->_col = BLACK;
                grandfather->_col = RED;
                //继续往上递归
                cur = grandfather;
                parent = cur->_parent;//这个肯定有父亲
            } 
            //情况 2+3： uncle不存在或为黑
            else
            {
                if (parent->_right==cur)
                {
                    _Rotate_L(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } 
                else
                {
                    _Rotate_R(parent);
                    _Rotate_L(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }
    //默认修改根节点为黑色
    _root->_col = BLACK;
    return make_pair(newnode, true);
}
2.2.6.2 旋转函数
void _Rotate_R(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			//1.旋转
			parent->_left = subLR;
			if (subLR)
			{
				subLR->_parent=parent;
			}
			subL->_right = parent;
			Node* grandparent = parent->_parent;//记录爷爷
			parent->_parent = subL;

			//2. 修改父子关系
			if (parent == _root)
			{//原来的父亲做了根节点
				_root = subL;
				_root->_parent = nullptr;
			}
			else
			{//修改爷爷和父亲链接
				if (grandparent->_left==parent)
					grandparent->_left = subL;
				else
					grandparent->_right = subL;
				subL->_parent = grandparent;
			}
		}

		void _Rotate_L(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			//1. 旋转
			parent->_right = subRL;
			if (subRL)
			{
				subRL->_parent = parent;
			}
			subR->_left = parent;
			Node* grandparent = parent->_parent;
			parent->_parent = subR;

			//2. 修改父子关系
			if (_root==parent)
			{
				_root = subR;
				_root->_parent = nullptr;
			} 
			else
			{
				if (grandparent->_left == parent)
					grandparent->_left = subR;
				else
					grandparent->_right = subR;
				subR->_parent = grandparent;
			}
		}

2.3 Erase

和AVL树类似，红黑树的删除只谈谈思想

  • 删除节点一定是左为空或者右为空，然后让父亲链接自己的孩子

    • 删除的是红色节点，直接就没有什么问题

    • 删除的是黑色节点，可能导致连续的红节点，或者一条路径上少了一个黑节点

      • 后继还有红节点，变色成黑的

      • 后继没有红节点可能还要旋转

具体有很多种情况可以参照https://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html

2.4 Find

和搜索树如出一辙

Node* Find(const K& key)
{
    Node* cur = _root;
    while (cur)
    {
        if (cur->_kv.first>key)
        {
            cur = cur->_left;
        }
        else if (cur->_kv.first<key)
        {
            cur = cur->_right;
        }
        else
        {
            return cur;
        }
    }
    return nullptr;
}

2.5 析构函数

void _Destroy(Node* root)
{
    if (root==nullptr)
    {
        return;
    }
    _Destroy(root->_left);
    _Destroy(root->_right);
    delete root;
}

//析构
~AVLTree()
{
    _Destroy(_root);
    _root = nullptr;
}

2.6 拷贝构造和赋值运算符

可以参考搜索二叉树，和之前的如出一辙

https://blog.csdn.net/Allen9012/article/details/124435568

image-20220507145354216

2.7 CheckBalance

我们需要写一个树来查一下我们的插入操作正不正确，是否插入形成了一个红黑树

为了验证是否是红黑树，我们还是利用几点原则

2.7.1 黑色的根

if (_root==nullptr)
{
    return true;
}
//1.黑根
if (_root->_col==false)
{
    cout<<"root是红色"
    return false;
}

2.7.2 没有连续的红色节点

方法就是遍历，然后找到红色节点，去查找父亲是不是红色节点，如果是红色就返回false

2.7.3 每条路径上的黑色节点数量相等

前序遍历，从根节点走到每一个NIL节点，只要是黑色就count++，如果走到了NIL节点就return，然后此时上一层栈帧的++不影响其他层的count，于是可以实现

  1. 用一个vector去记录每个路径的黑色接点数量，如果最后都是相等的，那么就是说明是红黑树
  2. 不想要走完每条路线才最后比较，可不可以找一条路径作为标准，只要其他路和这条路线不相等就说明不是红黑树，可以找最左路径做黑色节点的参考值
    bool _CheckBalance(Node*root,int black_num,int count)
{
    if (root ==nullptr)
    {
        if (count != black_num)
        {//3.路径黑节点数相等
            cout << "路径上黑色节点的数量不相等" << endl;
            return false;
        }
        return true;
    }

    //2.遍历红节点，查父亲是不是红的，不要查孩子因为孩子可能没有
    if (root->_col==RED && root->_parent->_col==RED)
    {
        cout << "存在连续的红色节点" << endl;
        return false;
    }

    if (root->_col==BLACK)
    {
        count++;
    }
    return _CheckBalance(root->_left,black_num,count)
                && _CheckBalance(root->_right,black_num,count);
}

bool  CheckBalance()
{
    if (_root==nullptr)
    {
        return true;
    }
    //1.黑根
    if (_root->_col==false)
    {
        cout<<"root是红色"<<endl;
        return false;
    }
    //2. 每条路径走到NIL节点，遇到黑++，找最左路径做黑色节点的参考值
    int black_num = 0;
    Node* left = _root;
    while (left)
    {
        if (left->_col==BLACK)
        {
            black_num++;
        }
        left = left->_left;
    }
    int count = 0;//count计算该条路的值
    //3. 用子函数来递归遍历
    return _CheckBalance(_root,black_num,count);
}

3. 红黑树 V.S. AVL树

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是
$$
O(log_2N)
$$

，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树的应用

  1. C++ STL库 – map/set、mutil_map/mutil_set
  2. Java 库
  3. linux内核
  4. 其他一些库

相关代码放在了我的GitHub仓库https://github.com/Allen9012/cpp/tree/main/C%2B%2B%E8%BF%9B%E9%98%B6/RBTree

Test

关于AVL树和红黑树的区别说法不正确的是（）

A.AVL树和红黑树保证平衡性的方式不同

B.AVL树和红黑树都是平衡树，因此查找的时间复杂度都是O(log_2N)

C.AVL树和红黑树的性质遭到破坏时，都需要进行旋转

D.AVL树和红黑树中序遍历都可以得到有序序列，因为它们都是二叉搜索树

A：正确，AVL树通过节点的平衡因子保证，红黑树通过节点的颜色以及红黑树的特性保证

B：正确，AVL树是严格平衡的，红黑树虽然是近似平衡，但其性能往往比AVL树好，而且实现简 单，因此他们的查找 效率都是O(logN)

C：错误，AVL树是一定需要旋转，红黑树不一定，红黑树有时只需要改变节点的颜色即可

D：正确，参考概念

因此：选择C

关于红黑树以下说法正确的是（）

A.空树不是红黑树，因为红黑树要求根节点必须为黑色，而空树中没有根节点

B.红黑树也是二叉搜索树，因此其按照前序遍历可以得到有序序列

C.红黑树是一棵真正平衡的二叉树

D.红黑树最长路径中节点个数可能会等于最短路径中节点个数的两倍

A：错误，空树也是红黑树，性质5中规定树中的空指针域为叶子节点，因此空树也是有节点的

B：错误，红黑树也是二叉搜索树，按照中序遍历才可以得到有序序列

C：红黑树不像AVL树那么严格，是一棵近似平衡的二叉搜索树

D：正确，比如红黑树中只有两个节点

因此：选择D

文章作者: Allen
文章链接: https://allen9012.github.io/BlogNet/BlogNet/2022/09/03/Red-Black-Tree/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Allen !
高阶数据结构
赏
  目录