红黑树详解：概念、性质与实现

红黑树详解：概念、性质与实现

引用

CSDN

1.

https://blog.csdn.net/woods12351/article/details/140091439

红黑树是一种自平衡二叉查找树，在计算机科学中被广泛应用于各种数据结构的实现，如C++标准模板库中的map和set。本文将详细介绍红黑树的基本概念、性质、插入操作、验证方法以及与AVL树的比较。

1.红黑树概念

红黑树，是一种二叉搜索树，但每个节点上增加了一个存储位表示结点的颜色，可以是RED或BLACK。通过任何一条根到叶子节点的途径上各个节点的着色方式的限制，红黑树确保没有一条路径会超过其他路径的二倍，因而是接近平衡的。

2.红黑树性质

1.每个节点不是红色就i是黑色
2.根节点是黑色的
3.如果一个节点是红色的，则它的两个孩子节点是黑色的
4.对于每个节点，从该节点到其所有后代的简单途径上，均包含相同个数的黑色节点
5.每个叶子节点都是黑色的（此处的叶子节点指的是空节点）

3.红黑树节点定义

// 节点颜色
enum Color
{
    RED, 
    BLACK
};
// 红黑树节点定义
template<class K, class V>
struct RBTreeNode
{
    RBTreeNode(pair<K, V> kv)
        :_kv(kv)
    {}
    RBTreeNode* _left = nullptr;    // 节点的左孩子
    RBTreeNode* _right = nullptr;   // 节点的右孩子
    RBTreeNode* _parent = nullptr;  // 节点的双亲（红黑树需要旋转）
    Color _col = RED;               // 节点的颜色
    pair<K, V> _kv;                 // 节点的值
};  

将节点默认为红色，可以保证任条简单路径的黑色简单的个数相同

4.红黑树的插入操作

红黑树实在二叉搜索树的基础上加上其平衡条件，因此红黑树的插入可以分为两步：

1. 按照二叉搜索树的规则插上新节点

class RBTRee
{
    typedef RBTreeNode<K, V> Node;
public:
    bool Insert(const pair<K, V> kv)
    {
        Node* newnode = new Node(kv);
        if (_root == nullptr)
        {
            _root = newnode;
        }
        else
        {
            Node* parent = nullptr;
            Node* cur = _root;
            //寻找插入位置
            while (cur)
            {
                if (kv.first > cur->_kv.first) cur = cur->_right;
                else if (kv.first < cur->_kv.first) cur = cur->_left;
                else return false;
            }
            if (kv.first > cur->_kv.first) parent->_right = newnode;
            else parent->_left = newnode;
            //调整节点颜色
        }
        // 节点的颜色可能被修改，将其改为黑色
   
        _root->_col = BLACK;
        return true;
    }
private:
    Node* _root = nullptr;
};  

2. 检测新节点插入后，红黑树的性质是否遭到破坏

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

cur:为当前节点，p为父节点，g为祖父节点,u为叔叔节点

a. cur为红，p为红，g为黑，u存在且为红

注意：此处的树可能是一颗完整的树，也有可能是一颗子树

如果g是根节点，需要将g改为黑色

如果g是子树，g一定有父节点，且g的父节点如果为红色，则需要继续向上调整

cur与p节点均为红色，将p，u改为黑，g改为红，继续向上调整

将grandparent节点改为红色，uncle和parent改为黑色，继续向上调整

Node* uncle = grandparent->_right;
// uncle存在且为红色
if (uncle && uncle->_col == RED)
{
    parent->_col = BLACK;
    uncle->_col = BLACK;
    grandparent->_col = RED;
    // 继续向上调整
    cur = grandparent;
    parent = cur->_parent;
}  

b.cur为红，p为红，g为黑，u不存在或u存在且为黑（cur与parent同侧）

1. 如果u节点不存在，则cur一定是新插入的节点，因为cur如果不是新插入的节点，则cur与p一定有一个节点是黑色，就不满足每条路径黑色节点相同

2.如果u节点存在，则其一定是黑色的，那么cur位置原来的节点一定是黑色的，是由于cur子树在调整过程中将cur的颜色变成了红色

直接经行右旋操作，再调整颜色

if (parent == grandparent->_left)
{
    if (parent->_left == cur)
    {
        _RotateR(grandparent);
        parent->_col = BLACK;
        grandparent->_col = RED;
    }
}  

c. cur为红，p为红，g为黑，u不存在或u存在且为黑（cur与parent异侧）

先对parent经行左旋将其变为b情况，再经行一次右旋。

if (uncle || uncle->_col == BLACK)
{
    if (parent == grandparent->_left)
    {
        Node* uncle = grandparent->_right;
        if (parent->_right == cur)
        {
            _RotateL(parent);
            _RotateR(grandparent);
            cur->_col = BLACK;
            grandparent->_col = RED;
        }
        break;
    }
}  

旋转操作

void _RotateR(Node* parent)
{
    Node* grandparent = parent->_parent;
    Node* LSub = parent->_left;
    Node* LSubR = LSub->_right;
    parent->_left = LSubR;
    if (LSubR) LSubR->_parent = parent;
    LSub->_right = parent;
    parent->_parent = LSub;
    LSub->_parent = grandparent;
    if (parent == _root) _root = LSub;
    else
    {
        if (grandparent->_left == parent) grandparent->_left = LSub;
        else grandparent->_right = LSub;
    }
}
void _RotateL(Node* parent)
{
    Node* grandparent = parent->_parent;
    Node* RSub = parent->_right;
    Node* RSubL = RSub->_left;
    parent->_right = RSubL;
    if (RSubL) RSubL->_parent = parent;
    RSub->_left = parent;
    parent->_parent = RSub;
    RSub->_parent = grandparent;
    if (parent == _root) _root = RSub;
    else
    {
        if (grandparent->_left == parent) grandparent->_left = RSub;
        else grandparent->_right = RSub;
    }
}  

5.红黑树的验证

红黑树的检测分为两步

1.检测其是否满足二叉搜索树的性质

中序遍历结果是否有序

void _InOrder(Node* root)
{
    if (root == nullptr) return;
    _InOrder(root->_left);
    cout << root->_kv.first << " " << root->_kv.second << endl;
    _InOrder(root->_right);
}  

2.检测其是否满足红黑树的性质。

bool IsBalance()
{
    if (_root->_col == RED) return false;
    int SumOfBlack = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK) SumOfBlack++;
        else
        {
            if (cur->_parent && cur->_parent->_col == RED) return false;
        }
        cur = cur->_left;
    }
    return _check(_root, SumOfBlack, 0);
}
bool _check(Node* root, int sum, int path)
{
    if (root == nullptr)
    {
        return sum == path;
    }
    return _check(root->_left, sum, path + 1) && _check(root->_right, sum, path + 1);
}  

6.红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是O(log N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的二倍，相对而言，降低了旋转的次数，所以经行增删的性能比AVL树更优，且红黑树的事项比较简单。