网站导航
> 文章列表 > 【C++进阶】四、红黑树（三）

【C++进阶】四、红黑树（三）

网友: 文章列表 2024-03-21 16:13:37

【C++进阶】四、红黑树（三）

目录

一、红黑树的概念

二、红黑树的性质

三、红黑树节点的定义

四、红黑树的插入

五、红黑树的验证

六、红黑树与AVL树的比较

七、完整代码

一、红黑树的概念

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

如下图就是一棵红黑树：

二、红黑树的性质

红黑树有以下性质：

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的，即没有连续红色节点
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，如上图的NIL节点)
  •  红黑树最优情况（左右平衡）：全黑或每条路径都是一黑一红相间的满二叉树，搜索高度 logN
  • 红黑树最差情况（左右极不平衡）：每颗子树左子树全黑，右子树一黑一红，搜索高度 2*logN

        红黑树不追求极致的平衡，AVL树则是追求极致的平衡，红黑树是近似平衡；红黑树这种近似平衡的结构大大减少了大量的旋转，红黑树的综合性能优于 AVL树

为什么红黑树满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

  • 红黑树的最短路径：全黑，一条路径上的全是黑色节点
  • 红黑树的最长路径：一黑一红相间的路径

比如：

三、红黑树节点的定义

        红黑树也是使用键值对，即KV模型，也是为了方便后序操作，红黑树的结构也是三叉链，即增加了指向父节点的 parent指针，还增加了一个成员变量，用于标识节点的颜色（red or black）

enum Colour
{RED,BLACK,
};//K:key, V:value
template<class K, class V>
struct RBTreeNode
{//构造函数RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}//成员变量pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:private:Node* _root = nullptr;//缺省值
};

注：这里使用了枚举来列举颜色

为什么构造红黑树结点时，默认将结点的颜色设置为红色？

  • 插入结点如果是黑色的，一定破坏红黑树的性质4，无论如何都必须对红黑树进行调整。
  • 插入结点如果是红色的，可能破坏红黑树的性质3，可能需要对红黑树进行调整 或者不需要调整

所以将节点颜色默认设置为红色

四、红黑树的插入

红黑树的插入分两步：

  1. 按照二叉搜索树的方式插入新节点
  2. 判断是否需要对红黑树进行调整

（1）插入节点

因为红黑树本身就是一棵二叉搜索树，因此寻找结点的插入位置是非常简单的，按照二叉搜索树的插入规则：

  1. 待插入结点的key值比当前结点小就插入到该结点的左子树
  2. 待插入结点的key值比当前结点大就插入到该结点的右子树
  3. 待插入结点的key值与当前结点的 key 值相等就插入失败

（2）判断是否需要对红黑树进行调整

判断：插入节点的父亲 parent 存在且为红色，则需要进行调整，否则不需要

然后分两种情况：

  • （A）parent在 grandfather 的左边
  • （B）parent在 grandfather 的右边

注：进行调整的关键是 uncle 

（A）parent在 grandfather 的左边有三种情况：

  1. 情况1：uncle存在且为红，uncle和parent的颜色需要修改为黑，granfather 修改为红，如果满足循环条件继续往上更新
  2. 情况2：uncle存在且为黑，需要对红黑树进行旋转
  3. 情况3：uncle不存在，需要对红黑树进行旋转

情况1，图如下：

注：情况2和情况3是一起处理的

情况2 + 情况3：

  1. cur，parent，grandfather 三个节点在一条直线上，单旋处理即可，对 grandfater 进行右单旋，然后 parent 的颜色改为黑，grandfater 的颜色改为红
  2. cur，parent，grandfather 三个节点是折线，需要双旋处理，对 parent 进行左单旋，然后对 grandfater 进行右单旋，然后 cur 的颜色改为黑，grandfater 的颜色改为红

情况2，图如下：

cur，parent，grandfather 三个节点在一条直线上

调颜色 

 cur，parent，grandfather 三个节点是折线

 调颜色

 情况3，图如下：

cur，parent，grandfather 三个节点在一条直线上

调颜色

  cur，parent，grandfather 三个节点是折线

 调颜色

（B）parent在 grandfater 的右边也有三种情况：（与左边情况完全一致，只是旋转不同）

  1. 情况1：uncle存在且为红，uncle和parent的颜色需要修改为黑，grandfater修改为红，如果满足循环条件继续往上更新
  2. 情况2：uncle存在且为黑，需要对红黑树进行旋转，对 grandfather 进行右单旋
  3. 情况3：uncle不存在，需要对红黑树进行双旋转，对 parent 进行左单旋，然后对 grandfather 进行右单旋

注：情况2和情况3是一起处理的

情况2 + 情况3：

  1. cur，parent，grandfather 三个节点在一条直线上，单旋处理即可，对 grandfather 进行左单旋，然后 parent 的颜色改为黑，grandfater 的颜色改为红
  2. cur，parent，grandfather 三个节点是折线，需要双旋处理，对 parent 进行右单旋，然后对 grandfather 进行左单旋，然后 cur 的颜色改为黑，grandfather 的颜色改为红

图就不画了，左边的图反过来就是右边的图，旋转在 AVL树有解释，这里就不再解释

经调整后，保持了红黑树的特性

插入代码如下：

//插入
bool Insert(const pair<K, V>& 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->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else//cur->kv.first == kv.first要插入值已经存在，插入失败{return false;}}cur = new Node(kv);cur->_col = RED;//新节点默认为红//插入if (parent->_kv.first < kv.first)//插入到parent左边{parent->_right = cur;cur->_parent = parent;}else//插入到parent右边{parent->_left = cur;cur->_parent = parent;}//进行调平衡 && 保持红黑树的特性，即插入节点的父亲是红色，需要对红黑树进行调整while (parent && parent->_col == RED)//parent存在且为红 进行调整{Node* grandfather = parent->_parent;//（1）parent在grandfater的左边//（2）parent在grandfater的右边if (parent == grandfather->_left)//parent在grandfater的左边{//情况1：uncle存在且为红，uncle和parent的颜色需要修改为黑，grandfater修改为红，如果满足循环条件继续往上更新//情况2：uncle存在且为黑，需要对红黑树进行旋转//情况3：uncle不存在，需要对红黑树进行旋转//注：情况2和情况3是一起处理的Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//情况1{//修改颜色uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//迭代往上更新cur = grandfather;parent = cur->_parent;}else//情况2 + 情况3{if (cur == parent->_left)//cur，parent，grandfater三个节点在一条直线上，单旋处理即可{RotateR(grandfather);//右单旋parent->_col = BLACK;grandfather->_col = RED;}else//cur，parent，grandfater三个节点是折线，需要双旋处理{RotateL(parent);//左单旋RotateR(grandfather);//右单旋cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后，该子树的根变成了黑色，符合红黑树的特性，无需继续往上处理}}else//parent在grandfater的右边{//在右边 也是上面左边的三种情况Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//情况1{//修改颜色uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//迭代往上更新cur = grandfather;parent = cur->_parent;}else//情况2 + 情况3{if (cur == parent->_right)//cur，parent，grandfater三个节点在一条直线上，单旋处理即可{RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//cur，parent，grandfater三个节点是折线，需要双旋处理{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后，该子树的根变成了黑色，符合红黑树的特性，无需继续往上处理}}}_root->_col = BLACK;//根的颜色需要变为黑（原因是可能情况1会把根节点变红）return true;
}

注：红黑树其他接口就不实现了，在面试考的花也是考查红黑树的插入，即红黑树如何调平衡

五、红黑树的验证

红黑树的检测分为两步：

  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
  2. 检测其是否满足红黑树的性质

（1）中序检查

//中序遍历
void InOrder()
{_InOrder(_root);
}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 != BLACK){cout << "违反规则：根节点不为黑色" << endl;return false;}Node* left = _root;int ref = 0;//用于一条路径上记录黑色节点的数量while (left)//求一条路径的黑色节点{if (left->_col == BLACK){++ref;}left = left->_left;}return Check(_root, 0, ref);
}//检查每条路径的黑色节点是否相等 && 是否出现连续红色节点
bool Check(Node* root, int blackNum, int ref)
{if (root == nullptr){if (blackNum != ref){cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "违反规则：出现连续红色节点" << endl;return false;}if (root->_col == BLACK){++blackNum;}return Check(root->_left, blackNum, ref)&& Check(root->_right, blackNum, ref);
}

六、红黑树与AVL树的比较

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

红黑树的应用：

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

七、完整代码

RBTree.h

#pragma onceenum Colour
{RED,BLACK,
};//K:key, V:value
template<class K, class V>
struct RBTreeNode
{//构造函数RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}//成员变量pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://插入bool Insert(const pair<K, V>& 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->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else//cur->kv.first == kv.first要插入值已经存在，插入失败{return false;}}cur = new Node(kv);cur->_col = RED;//新节点默认为红//插入if (parent->_kv.first < kv.first)//插入到parent左边{parent->_right = cur;cur->_parent = parent;}else//插入到parent右边{parent->_left = cur;cur->_parent = parent;}//进行调平衡 && 保持红黑树的特性，即插入节点的父亲是红色，需要对红黑树进行调整while (parent && parent->_col == RED)//parent存在且为红 进行调整{Node* grandfather = parent->_parent;//（1）parent在grandfater的左边//（2）parent在grandfater的右边if (parent == grandfather->_left)//parent在grandfater的左边{//情况1：uncle存在且为红，uncle和parent的颜色需要修改为黑，grandfater修改为红，如果满足循环条件继续往上更新//情况2：uncle存在且为黑，需要对红黑树进行旋转//情况3：uncle不存在，需要对红黑树进行旋转//注：情况2和情况3是一起处理的Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//情况1{//修改颜色uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//迭代往上更新cur = grandfather;parent = cur->_parent;}else//情况2 + 情况3{if (cur == parent->_left)//cur，parent，grandfater三个节点在一条直线上，单旋处理即可{RotateR(grandfather);//右单旋parent->_col = BLACK;grandfather->_col = RED;}else//cur，parent，grandfater三个节点是折线，需要双旋处理{RotateL(parent);//左单旋RotateR(grandfather);//右单旋cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后，该子树的根变成了黑色，符合红黑树的特性，无需继续往上处理}}else//parent在grandfater的右边{//在右边 也是上面左边的三种情况Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//情况1{//修改颜色uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//迭代往上更新cur = grandfather;parent = cur->_parent;}else//情况2 + 情况3{if (cur == parent->_right)//cur，parent，grandfater三个节点在一条直线上，单旋处理即可{RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//cur，parent，grandfater三个节点是折线，需要双旋处理{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后，该子树的根变成了黑色，符合红黑树的特性，无需继续往上处理}}}_root->_col = BLACK;//根的颜色需要变为黑（原因是可能情况1会把根节点变红）return true;}//中序遍历void InOrder(){_InOrder(_root);}//检查红黑树特性bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col != BLACK){cout << "违反规则：根节点不为黑色" << endl;return false;}Node* left = _root;int ref = 0;//用于一条路径上记录黑色节点的数量while (left)//求一条路径的黑色节点{if (left->_col == BLACK){++ref;}left = left->_left;}return Check(_root, 0, ref);}
private://检查每条路径的黑色节点是否相等 && 是否出现连续红色节点bool Check(Node* root, int blackNum, int ref){if (root == nullptr){if (blackNum != ref){cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "违反规则：出现连续红色节点" << endl;return false;}if (root->_col == BLACK){++blackNum;}return Check(root->_left, blackNum, ref)&& Check(root->_right, blackNum, ref);}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){Node* subR = parent->_right;Node* subRL = subR->_left;//进行链接parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;//记录parent节点的前一个节点subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr)//即subR已经是根节点{_root = subR;_root->_parent = nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode->_left == parent)//parent原本在 ppNode 的左边{ppNode->_left = subR;}else//parent原本在 ppNode 的右边{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;//记录parent节点的前一个节点subL->_right = parent;parent->_parent = subL;if (ppNode == nullptr)//即subL已经是根节点{_root = subL;subL->_parent = nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode->_left == parent)//parent原本在 ppNode 的左边{ppNode->_left = subL;}else//parent原本在 ppNode 的右边{ppNode->_right = subL;}subL->_parent = ppNode;}}
private:Node* _root = nullptr;//缺省值
};

 Test.cpp

#include <iostream>
using namespace std;
#include "RBTree.h"void TestRBTree1()
{//int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree<int, int> t;for (auto e : arr){t.Insert(make_pair(e, e));}t.InOrder();
}void TestRBTree2()
{srand(time(0));//随机数种子const size_t N = 100000;RBTree<int, int> t;for (size_t i = 0; i < N; ++i){size_t x = rand();t.Insert(make_pair(x, x));//cout << t.IsBalance() << endl;}cout << t.IsBalance() << endl;
}int main()
{TestRBTree2();return 0;
}

----------------我是分割线---------------

文章到这里就结束了，下一篇即将更新

网络标签：

相关问题