✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

文章目录

目录

文章目录

前言

一  红黑树的概念

二  红黑树的性质

三  红黑树节点的定义

四  红黑树结构

五  红黑树的插入操作

六  红黑树的验证 

七  红黑树的删除

八  红黑树与AVL树的比较 

九  红黑树的迭代器 

十  红黑树全代码

总结

前言

本篇详细介绍了进一步介绍C++中的红黑树，让使用者对红黑树有更加深刻的认知，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！

一  红黑树的概念

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

二  红黑树的性质

1. 每个结点不是红色就是黑色 

2. 根节点是黑色的 

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 

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

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

三  红黑树节点的定义

<code>// 节点的颜色

enum Color{RED, BLACK};

// 红黑树节点的定义

template<class T>

struct RBTreeNode

{

RBTreeNode(const ValueType& data = ValueType()，Color color = RED)

: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)

, _data(data), _color(color)

{}

RBTreeNode<ValueType>* _pLeft; // 节点的左孩子

RBTreeNode<ValueType>* _pRight; // 节点的右孩子

RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)

T _data; // 节点的值域

Color _color; // 节点的颜色

};

四  红黑树结构

        为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了 与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft 域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下：

五  红黑树的插入操作

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

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

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

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

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

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

         ⊚  cur为红，p为红，g为黑，u不存在/u存在且为黑

         ⊚  情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑（双旋转处理）

 插入代码如下：

<code>bool Insert(const T& data)

{

if (_root == nullptr)

{

_root = new Node(data);

_root->_col = BLACK;

return true;

}

KeyOfT kot;

Node* parent = nullptr;

Node* cur = _root;

while (cur)

{

if (kot(cur->_data) < kot(data))

{

parent = cur;

cur = cur->_right;

}

else if (kot(cur->_data) > kot(data))

{

parent = cur;

cur = cur->_left;

}

else

{

return false;

}

}

cur = new Node(data);

// 新增节点。颜色红色给红色

cur->_col = RED;

if (kot(parent->_data) < kot(data))

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

cur->_parent = parent;

while (parent && parent->_col == RED)

{

Node* grandfather = parent->_parent;

// g

// p u

if (parent == grandfather->_left)

{

Node* uncle = grandfather->_right;

if (uncle && uncle->_col == RED)

{

// u存在且为红 -》变色再继续往上处理

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

cur = grandfather;

parent = cur->_parent;

}

else

{

// u存在且为黑或不存在 -》旋转+变色

if (cur == parent->_left)

{

// g

// p u

//c

//单旋

RotateR(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

// g

// p u

// c

//双旋

RotateL(parent);

RotateR(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

else

{

// g

// u p

Node* uncle = grandfather->_left;

// 叔叔存在且为红，-》变色即可

if (uncle && uncle->_col == RED)

{

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

// 继续往上处理

cur = grandfather;

parent = cur->_parent;

}

else // 叔叔不存在，或者存在且为黑

{

// 情况二：叔叔不存在或者存在且为黑

// 旋转+变色

// g

// u p

// c

if (cur == parent->_right)

{

RotateL(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

//g

// u p

// c

RotateR(parent);

RotateL(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

}

_root->_col = BLACK;

return true;

}

六  红黑树的验证 

红黑树的检测分为两步：

        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 == nullptr)

return true;

if (_root->_col == RED) //检测根是否为黑色

{

cout << "异常：根为红色" << endl;

return false;

}

// 预先求出某条路径的黑色节点数量

size_t blackcount = 0;

Node *cur = _root;

while (cur)

{

if (cur->_col == BLACK)

blackcount++;

cur = cur->_left;

}

size_t k = 0; //作为参数传入，用于统计路径的黑色节点数量

return _IsBalance(_root, k, blackcount);

}

bool _IsBalance(Node *root, size_t k, size_t blackcount)

{

if (root == nullptr) //走到路径结尾

{

if (k != blackcount)

{

cout << "异常：路径黑节点数目不同" << endl;

return false;

}

return true;

}

if (root->_col == RED && root->_parent->_col == RED) //判断是否有连续红节点

{

cout << "异常：出现连续红节点" << endl;

return false;

}

if (root->_col == BLACK) //统计黑色节点数量

k++;

return _IsBalance(root->_left, k, blackcount)

&& _IsBalance(root->_right, k, blackcount); //进行递归

}

七  红黑树的删除

红黑树的删除本节不做讲解，参考《算法导论》或者《STL源码剖析》

红黑树 - _Never_ - 博客园 (cnblogs.com)

八  红黑树与AVL树的比较 

        红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追 求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。 

九  红黑树的迭代器 

        迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代 器，需要考虑以前问题： 

        ⊚  begin()与end() ：

        STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后， 可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？ 能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：

        ⊚  operator++()与operator--() 

 operator++()：

<code>//typedef RBTreeIterator<T> Self;

Self& operator++()

{

if (_node->_right)

{

// 右不为空，右子树最左节点就是中序下一个

Node* leftMost = _node->_right;

while (leftMost->_left)

{

leftMost = leftMost->_left;

}

_node = leftMost;

}

else

{

Node* cur = _node;

Node* parent = cur->_parent;

while (parent && cur == parent->_right)

{

cur = parent;

parent = cur->_parent;

}

_node = parent;

}

return *this;

}

  operator--()：

<code>Self& operator--()

{

//分三种情况讨论：_pNode 在head的位置，_pNode 左子树存在，_pNode 左子树不

//存在

// 1. _pNode 在head的位置，--应该将_pNode放在红黑树中最大节点的位置

if (_node->_parent->_parent == _node && _node->_col == RED)

_node = _node->_right;

else if (_node->_left)

{

// 2. _pNode的左子树存在,在左子树中找最大的节点，即左子树中最右侧节点

_node = _node->_left;

while (_node->_right)

_node = _node->_right;

}

else

{

// _pNode的左子树不存在，只能向上找

Node pParent = _node->_parent;

while (_node == pParent->_left)

{

_node = pParent;

pParent = _node->_parent;

}

_node = pParent;

}

}

迭代器全代码：

template<class T>

struct RBTreeIterator

{

typedef RBTreeNode<T> Node;

typedef RBTreeIterator<T> Self;

Node* _node;

RBTreeIterator(Node* node)

:_node(node)

{}

Self& operator++()

{

if (_node->_right)

{

// 右不为空，右子树最左节点就是中序下一个

Node* leftMost = _node->_right;

while (leftMost->_left)

{

leftMost = leftMost->_left;

}

_node = leftMost;

}

else

{

Node* cur = _node;

Node* parent = cur->_parent;

while (parent && cur == parent->_right)

{

cur = parent;

parent = cur->_parent;

}

_node = parent;

}

return *this;

}

Self& operator--()

{

//分三种情况讨论：_pNode 在head的位置，_pNode 左子树存在，_pNode 左子树不

//存在

// 1. _pNode 在head的位置，--应该将_pNode放在红黑树中最大节点的位置

if (_node->_parent->_parent == _node && _node->_col == RED)

_node = _node->_right;

else if (_node->_left)

{

// 2. _pNode的左子树存在,在左子树中找最大的节点，即左子树中最右侧节点

_node = _node->_left;

while (_node->_right)

_node = _node->_right;

}

else

{

// _pNode的左子树不存在，只能向上找

Node pParent = _node->_parent;

while (_node == pParent->_left)

{

_node = pParent;

pParent = _node->_parent;

}

_node = pParent;

}

}

T& operator*()

{

return _node->_data;

}

bool operator!= (const Self& s)

{

return _node != s._node;

}

};

十  红黑树全代码

#pragma once

#include<iostream>

#include<vector>

#include<assert.h>

using namespace std;

enum Colour

{

RED,

BLACK

};

template<class T>

struct RBTreeNode

{

T _data;

RBTreeNode<T>* _left;

RBTreeNode<T>* _right;

RBTreeNode<T>* _parent;

Colour _col;

RBTreeNode(const T& data)

: _data(data)

, _left(nullptr)

, _right(nullptr)

, _parent(nullptr)

{}

};

template<class T>

struct RBTreeIterator

{

typedef RBTreeNode<T> Node;

typedef RBTreeIterator<T> Self;

Node* _node;

RBTreeIterator(Node* node)

:_node(node)

{}

Self& operator++()

{

if (_node->_right)

{

// 右不为空，右子树最左节点就是中序下一个

Node* leftMost = _node->_right;

while (leftMost->_left)

{

leftMost = leftMost->_left;

}

_node = leftMost;

}

else

{

Node* cur = _node;

Node* parent = cur->_parent;

while (parent && cur == parent->_right)

{

cur = parent;

parent = cur->_parent;

}

_node = parent;

}

return *this;

}

Self& operator--()

{

//分三种情况讨论：_pNode 在head的位置，_pNode 左子树存在，_pNode 左子树不

//存在

// 1. _pNode 在head的位置，--应该将_pNode放在红黑树中最大节点的位置

if (_node->_parent->_parent == _node && _node->_col == RED)

_node = _node->_right;

else if (_node->_left)

{

// 2. _pNode的左子树存在,在左子树中找最大的节点，即左子树中最右侧节点

_node = _node->_left;

while (_node->_right)

_node = _node->_right;

}

else

{

// _pNode的左子树不存在，只能向上找

Node pParent = _node->_parent;

while (_node == pParent->_left)

{

_node = pParent;

pParent = _node->_parent;

}

_node = pParent;

}

}

T& operator*()

{

return _node->_data;

}

bool operator!= (const Self& s)

{

return _node != s._node;

}

};

template<class K, class T, class KeyOfT>

class RBTree

{

typedef RBTreeNode<T> Node;

public:

typedef RBTreeIterator<T> Iterator;

Iterator Begin()

{

Node* leftMost = _root;

while (leftMost && leftMost->_left)

{

leftMost = leftMost->_left;

}

return Iterator(leftMost);

}

Iterator End()

{

return Iterator(nullptr);

}

RBTree() = default;

RBTree(const RBTree& t)

{

_root = Copy(t._root);

}

RBTree& operator=(RBTree t)

{

swap(_root, t._root);

return *this;

}

~RBTree()

{

Destroy(_root);

_root = nullptr;

}

bool Insert(const T& data)

{

if (_root == nullptr)

{

_root = new Node(data);

_root->_col = BLACK;

return true;

}

KeyOfT kot;

Node* parent = nullptr;

Node* cur = _root;

while (cur)

{

if (kot(cur->_data) < kot(data))

{

parent = cur;

cur = cur->_right;

}

else if (kot(cur->_data) > kot(data))

{

parent = cur;

cur = cur->_left;

}

else

{

return false;

}

}

cur = new Node(data);

// 新增节点。颜色红色给红色

cur->_col = RED;

if (kot(parent->_data) < kot(data))

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

cur->_parent = parent;

while (parent && parent->_col == RED)

{

Node* grandfather = parent->_parent;

// g

// p u

if (parent == grandfather->_left)

{

Node* uncle = grandfather->_right;

if (uncle && uncle->_col == RED)

{

// u存在且为红 -》变色再继续往上处理

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

cur = grandfather;

parent = cur->_parent;

}

else

{

// u存在且为黑或不存在 -》旋转+变色

if (cur == parent->_left)

{

// g

// p u

//c

//单旋

RotateR(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

// g

// p u

// c

//双旋

RotateL(parent);

RotateR(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

else

{

// g

// u p

Node* uncle = grandfather->_left;

// 叔叔存在且为红，-》变色即可

if (uncle && uncle->_col == RED)

{

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

// 继续往上处理

cur = grandfather;

parent = cur->_parent;

}

else // 叔叔不存在，或者存在且为黑

{

// 情况二：叔叔不存在或者存在且为黑

// 旋转+变色

// g

// u p

// c

if (cur == parent->_right)

{

RotateL(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

//g

// u p

// c

RotateR(parent);

RotateL(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

}

_root->_col = BLACK;

return true;

}

void InOrder()

{

_InOrder(_root);

cout << endl;

}

int Height()

{

return _Height(_root);

}

int Size()

{

return _Size(_root);

}

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

}

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;

}

private:

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

}

int _Size(Node* root)

{

return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;

}

int _Height(Node* root)

{

if (root == nullptr)

return 0;

int leftHeight = _Height(root->_left);

int rightHeight = _Height(root->_right);

return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

}

void _InOrder(Node* root)

{

if (root == nullptr)

{

return;

}

_InOrder(root->_left);

cout << root->_kv.first << ":" << root->_kv.second << endl;

_InOrder(root->_right);

}

void RotateL(Node* parent)

{

_rotateNum++;

Node* subR = parent->_right;

Node* subRL = subR->_left;

parent->_right = subRL;

if (subRL)

subRL->_parent = parent;

Node* parentParent = parent->_parent;

subR->_left = parent;

parent->_parent = subR;

if (parentParent == nullptr)

{

_root = subR;

subR->_parent = nullptr;

}

else

{

if (parent == parentParent->_left)

{

parentParent->_left = subR;

}

else

{

parentParent->_right = subR;

}

subR->_parent = parentParent;

}

}

void RotateR(Node* parent)

{

_rotateNum++;

Node* subL = parent->_left;

Node* subLR = subL->_right;

parent->_left = subLR;

if (subLR)

subLR->_parent = parent;

Node* parentParent = parent->_parent;

subL->_right = parent;

parent->_parent = subL;

if (parentParent == nullptr)

{

_root = subL;

subL->_parent = nullptr;

}

else

{

if (parent == parentParent->_left)

{

parentParent->_left = subL;

}

else

{

parentParent->_right = subL;

}

subL->_parent = parentParent;

}

}

void Destroy(Node* root)

{

if (root == nullptr)

return;

Destroy(root->_left);

Destroy(root->_right);

delete root;

}

Node* Copy(Node* root)

{

if (root == nullptr)

return nullptr;

Node* newRoot = new Node(root->_kv);

newRoot->_left = Copy(root->_left);

newRoot->_right = Copy(root->_right);

return newRoot;

}

private:

Node* _root = nullptr;

public:

int _rotateNum = 0; //旋转次数

};

总结

✨✨✨各位读友，本篇分享到内容是否更好的让你理解红黑树，如果对你有帮助给个👍赞鼓励一下吧！！

🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。

感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！