C++之红黑树认识与实现-EW帮帮网

一.红黑树的概念

红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍，因⽽是接近平衡的。

红黑树的结构

// 枚举值表⽰颜⾊ 

enum Colour
{
	 RED,
	 BLACK
};

template<class K, class V>

struct RBTreeNode

{
 // 这⾥更新控制平衡也要加⼊parent指针 
	 pair<K, V> _kv;
	 RBTreeNode<K, V>* _left;
	 RBTreeNode<K, V>* _right;
	 RBTreeNode<K, V>* _parent;
	 Colour _col;
	 RBTreeNode(const pair<K, V>& kv)
		 :_kv(kv)
		 , _left(nullptr)
		 , _right(nullptr)
	 	, _parent(nullptr)
	 {}
};

template<class K, class V>

class RBTree{
	 typedef RBTreeNode<K, V> Node;	
public:

private:
 Node* _root = nullptr;
};

二.红黑树的定义与特性

红黑树是一种自平衡的二叉查找树，它满足以下五条基本性质：

节点是红色或黑色：每个节点都有一个颜色属性，红色或黑色。
根节点是黑色：树的根节点必须是黑色。
叶子节点是黑色：叶子节点（即空节点或NULL节点）是黑色。
红色节点的子节点是黑色：如果一个节点是红色，则它的两个子节点都是黑色。
从任意节点到其每个叶子的所有路径都包含相同数量的黑色节点：这确保了树的平衡性。

这些性质保证了红黑树在插入和删除操作后能够保持大致平衡，从而使得查找、插入和删除操作的时间复杂度都能保持在(O(log n))。
在这里插入图片描述

一.红黑树的插入操作

插入操作是红黑树中最复杂的部分之一。插入一个新节点后，可能会破坏红黑树的性质，因此需要通过一系列的调整来恢复这些性质。插入操作可以分为以下几个步骤：

1. 插入节点

首先，将新节点插入到红黑树中，就像在普通二叉查找树中插入一样。新插入的节点会被标记为红色，因为插入红色节点比插入黑色节点更容易保持树的平衡。

2. 修复红黑树

插入红色节点后，可能会违反红黑树的性质4（红色节点的子节点是黑色）。因此，需要通过以下几种情况进行调整：

情况1：新节点的父节点是黑色
这种情况下，插入的红色节点不会破坏红黑树的性质，无需进行任何调整。
情况2：新节点的父节点和叔叔节点都是红色
这种情况下，将父节点和叔叔节点变为黑色，祖父节点变为红色。然后，将祖父节点作为新的当前节点，继续向上调整。
情况3：新节点的父节点是红色，叔叔节点是黑色或为空
这种情况下，不仅仅需要变色，还需要进行旋转来调整。

插入操作的步骤

1. 插入新节点

如果树为空（_root == nullptr），直接创建一个黑色节点作为根节点并返回。
如果树不为空，从根节点开始，通过比较键值来找到插入位置。如果键值已经存在，则返回false，表示插入失败。
找到插入位置后，创建一个红色节点（新节点默认为红色），并将其插入到合适的位置（作为某个节点的左子节点或右子节点）。

2. 修复红黑树的性质

插入红色节点后，可能会违反红黑树的性质（尤其是第4条性质：不能有两个连续的红色节点）。因此需要通过旋转和变色操作来修复。

修复逻辑

循环条件：只要当前节点的父节点是红色，就需要进行修复。
祖父节点和叔叔节点：
- 祖父节点是当前节点的父节点的父节点。
- 叔叔节点是祖父节点的另一个子节点（与父节点不同）。

修复情况

叔叔节点存在且为红色：
- 父节点和叔叔节点都变色为黑色。
- 祖父节点变色为红色。
- 将当前节点更新为祖父节点，继续向上检查。
叔叔节点不存在或者为黑色：
- 如果父节点是祖父节点的左子节点：
  - 如果当前节点是父节点的左子节点：
    - 右旋祖父节点。
    - 父节点变色为黑色，祖父节点变色为红色。
  - 如果当前节点是父节点的右子节点：
    - 左旋父节点。
    - 右旋祖父节点。
    - 当前节点变色为黑色，祖父节点变色为红色。
- 如果父节点是祖父节点的右子节点：
  - 如果当前节点是父节点的右子节点：
    - 左旋祖父节点。
    - 父节点变色为黑色，祖父节点变色为红色。
  - 如果当前节点是父节点的左子节点：
    - 右旋父节点。
    - 左旋祖父节点。
    - 当前节点变色为黑色，祖父节点变色为红色。
      单旋：
      
      双旋：

3. 根节点的颜色

最后，确保根节点是黑色。

代码逻辑解析

插入新节点：

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

从根节点开始，通过比较键值找到插入位置。如果键值已存在，返回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;
```

二.红黑树的删除操作（作为了解即可）

删除操作比插入操作更为复杂，因为它可能会破坏红黑树的平衡。删除操作可以分为以下几个步骤：

1. 删除节点

首先，找到需要删除的节点。如果该节点有两个子节点，则需要找到它的后继节点（右子树中的最小节点）来替换它。然后，将该节点的值替换为后继节点的值，并将后继节点删除。

2. 修复红黑树

删除节点后，可能会违反红黑树的性质。需要通过以下几种情况进行调整：

情况1：被删除的节点是红色
这种情况下，直接删除该节点不会破坏红黑树的性质。
情况2：被删除的节点是黑色，且其子节点是红色
这种情况下，将子节点变为黑色，然后删除该节点。
情况3：被删除的节点是黑色，且其子节点是黑色
这种情况下，需要通过一系列复杂的调整来恢复红黑树的性质，包括颜色调整和旋转操作。

三.红黑树的查找操作

按⼆叉搜索树逻辑实现即可，搜索效率为O(logN)

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

四.红黑树的验证

每个节点是红色或黑色。
根节点是黑色。
所有叶子节点（空节点）是黑色。
如果一个节点是红色，则它的两个子节点都是黑色（不能有两个连续的红色节点）。
从任何节点到其每个叶子的所有路径都包含相同数量的黑色节点。

代码中的检查逻辑

1. `IsBalance`函数

这个函数是入口函数，用于初始化检查过程。

bool IsBalance()
{
    if (_root == nullptr)
        return true; // 如果树为空，直接返回true，空树满足红黑树的性质
    if (_root->_col == RED)
        return false; // 根节点必须是黑色，否则直接返回false

    // 计算从根节点到最左边叶子节点的黑色节点数量作为参考值
    int refNum = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK)
            ++refNum; // 如果当前节点是黑色，增加黑色节点计数
        cur = cur->_left; // 沿着左子树向下遍历
    }

    // 使用参考值调用Check函数检查整棵树
    return Check(_root, 0, refNum);
}

检查根节点颜色：如果根节点是红色，直接返回false，因为红黑树的根节点必须是黑色。
计算参考值refNum：从根节点开始，沿着左子树一直向下，统计路径上的黑色节点数量。这个值将作为后续路径检查的参考值。
调用Check函数：使用计算出的refNum，从根节点开始递归检查整棵树。

2. `Check`函数

这个函数是递归函数，用于检查树的每个路径是否满足红黑树的性质。

bool Check(Node* root, int blackNum, const int refNum)
{
    if (root == nullptr)
    {
        // 前序遍历走到空节点，意味着一条路径走完了
        if (refNum != blackNum)
        {
            cout << "存在黑色节点的数量不相等的路径" << endl;
            return false; // 如果当前路径的黑色节点数量与参考值不同，返回false
        }
        return true;
    }

    // 检查是否存在连续的红色节点
    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << root->_kv.first << "存在连续的红色节点" << endl;
        return false; // 如果当前节点和父节点都是红色，返回false
    }

    if (root->_col == BLACK)
    {
        blackNum++; // 如果当前节点是黑色，增加黑色节点计数
    }

    // 递归检查左右子树
    return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}

检查路径结束：如果当前节点是空节点（root == nullptr），说明已经到达路径的末端。此时检查当前路径的黑色节点数量blackNum是否与参考值refNum相等。如果不相等，说明违反了红黑树的第5条性质。
检查连续红色节点：如果当前节点是红色，并且它的父节点也是红色，直接返回false，因为这违反了红黑树的第4条性质。
统计黑色节点：如果当前节点是黑色，将blackNum加1。
递归检查子树：递归调用Check函数，分别检查当前节点的左子树和右子树。只有当左右子树都满足红黑树的性质时，当前节点才满足性质。

bool Check(Node* root, int blackNum, const int refNum)
{
 if (root == nullptr)
 {
	 // 前序遍历⾛到空时，意味着⼀条路径⾛完了 
 	//cout << blackNum << endl;

	 if (refNum != blackNum)
	 {
		 cout << "存在⿊⾊结点的数量不相等的路径" << endl;
		 return false;
	 }
 return true;
 }
 
 // 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了 
 if (root->_col == RED && root->_parent->_col == RED)
	 {
		 cout << root->_kv.first << "存在连续的红⾊结点" << endl;
		 return false;
 	}
 if (root->_col == BLACK)
	 {
		 blackNum++;
	 }
 	return Check(root->_left, blackNum, refNum)
		 && Check(root->_right, blackNum, refNum);
}
 

bool IsBalance()
{
	 if (_root == nullptr)
	 	return true;
 	if (_root->_col == RED)
 		return false;
 
 // 参考值 
	 int refNum = 0;
 	Node* cur = _root;
	 while (cur)
	 {
		 if (cur->_col == BLACK)
 	 {
		 ++refNum;
	 }
		 cur = cur->_left;
	 }
	 return Check(_root, 0, refNum);
}

红黑树 vs AVL树

特性	红黑树	AVL树
平衡严格度	宽松（最长路径≤2×最短）	严格（高度差≤1）
插入/删除	更快（平均更少旋转）	较慢（旋转次数多）
查找效率	稍慢（高度略高）	更快（高度最小化）
适用场景	频繁修改的关联容器（如map）	查询密集型场景

在这里插入图片描述

C++之红黑树认识与实现

RBTree

一.红黑树的概念

红黑树的结构

二.红黑树的定义与特性

一.红黑树的插入操作

1. 插入节点

2. 修复红黑树

插入操作的步骤

1. 插入新节点

2. 修复红黑树的性质

修复逻辑

修复情况

3. 根节点的颜色

代码逻辑解析

二.红黑树的删除操作（作为了解即可）

1. 删除节点

2. 修复红黑树

三.红黑树的查找操作

四.红黑树的验证

代码中的检查逻辑

1. `IsBalance`函数

2. `Check`函数

红黑树 vs AVL树

网站公告

今日签到

热门文章

最新发布

C++之红黑树认识与实现

RBTree

一.红黑树的概念

红黑树的结构

二.红黑树的定义与特性

一.红黑树的插入操作

1. 插入节点

2. 修复红黑树

插入操作的步骤

1. 插入新节点

2. 修复红黑树的性质

修复逻辑

修复情况

3. 根节点的颜色

代码逻辑解析

二.红黑树的删除操作（作为了解即可）

1. 删除节点

2. 修复红黑树

三.红黑树的查找操作

四.红黑树的验证

代码中的检查逻辑

1. IsBalance函数

2. Check函数

红黑树 vs AVL树

网站公告

今日签到

热门文章

最新发布

1. `IsBalance`函数

2. `Check`函数