数据结构·红黑树

🕗 发布于 2024-07-26 20:50 数据结构 c++ 开发语言

1. 红黑树的概念

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

红黑树的平衡不像是AVL树那样的绝对平衡，红黑树是一种近似平衡，它避免了处理繁琐的平衡因子，同时它搜索的效率也基本没有影响，不过是最坏情况要搜索 2*logN 但是这从时间复杂度上看，与AVL树的绝对logN是一样的。

2. 红黑树的规则

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

2. 根节点是黑色的

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

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

5. 每个叶子节点下的空节点都是黑色的，我们管这类空节点叫NIL节点，主要是用来统计总路径用的

只要满足前4条规则就可以满足红黑树中：“最长路径中节点个数不会超过最短路径节点个数的两倍” 的原则。在我们写树，或者说对树进行调整的时候都不需要考虑规则5，规则5就是个计数用的

3. 红黑树的节点

红黑树节点的颜色我们默认给红色。

因为如果默认给黑色的话就会导致每新增一个节点时，该路径的黑色节点就会比别的路径多一个，此时不满足规则4，就要对树进行调整。

但是如果插入的是一个红色节点，如果它的父节点是黑色的，则不用对树进行任何调整，只有它的父节点是红色的，才会违背规则3，需要对树进行调整。

4. 红黑树的插入

红黑树的在插入时要一直符合那4个规则，因此在插入之后有两种调整方案。1. 更新节点的颜色，2. 当更新节点颜色的时候也控制不住这个树了的话就对树进行旋转。

经过总结和推到给出的结果就是：当我们在调整树的时候只需要关注4个节点的状态

分别是当前节点cur，父节点(parent) p，祖父节点(grandparent) g，叔叔节点(uncle) u。

具体到选择那种调整方案的时候只需要看 uncle节点的状态，如果是红色就选第一种更新方案，如果是黑色或者不存在就选第二种更新方案

第一种更新方案是只需要进行颜色的更新就可以维持住红黑树的规则。

第二种更新方案是需要旋转才可以。第二种更新方案又分为单旋和双旋两种情况

4.1 当uncle节点为红色时

cur节点是新插入的，或者是调整上来的当前需要调整的节点，它一定是红色的，因为如果是黑色就不必调整了，也不会走到这步。

parent节点也一定是红色的，因为如果parent节点是黑色的话我们就不用继续调整了，可以跳出调整循环了。

grandparent节点一定是黑色的，因为如果它是红色的，说明这棵树之前就该调整了，p和g两个红色节点早就连到一块了，或者说这棵树已经坏了。

那么此时我们假设uncle节点为红色，此时的调整思路如下图

我们将g节点的黑色状态下发给p和u两个节点，再将g节点颜色改为红色，此时没有在任何路径上新增黑色节点，不会破坏规则4，同时也维护住了规则3。

然后我们以g节点为cur，继续向上更新，此时更新分3种情况

如果g节点已经是根了，那我们就不能往上更新了，然后将g节点也就是根节点置黑。

如果g节点的parent存在且是黑色，那就不用继续更新了。

如果g节点的parent存在且是红色，就需要向上更新

4.2 当uncle节点为黑或不存在时

此时的树已经无法通过更新节点颜色控制住的了，因此我们要开始旋转树。

与AVL树判断单双旋的思路是一样的，如果g、p、cur三个节点在同一边就进行单旋；如果一个在left一个在right，也就是说3个节点不在同一边就进行双旋。

4.1 单旋情况

当uncle节点不存在时cur一定是新增的节点，因为如果unlce不存在，也就是说以g为根的路径上只能有g节点一个黑色节点，那a、b、c树如果存在的话它们的节点又应该是什么颜色的呢？都是红色吗？因此a、b、c树一定不存在，也就是说cur一定是新增节点。

那如果uncle不存在的情况能不能通过更新颜色来进行规则控制呢？比如把p节点置黑，g节点置红，然后再向上更新。答案也是不行的。可以想象，如果按照这个方案执行的话，如果插入一个有序的数组，岂不是又变成了一个单支树了。

我们回到单旋的操作，一共分成两步。1. 以g为根进行单旋。2.处理颜色。但是旋完之后我们不需要进行向上更新了，因为旋完的根p是一个黑色的节点。

4.2 双旋情况

当g、p、cur三个节点不在同一边就要进行双旋

先单旋p节点变成上面的单旋情况，然后再单旋，最后更改颜色。

5. 红黑树与AVL树的比较

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

6. 红黑树完整代码

红黑树的删除代码也先欠着

//节点的颜色
enum color{RED,BLACK};
//红黑树节点的定义
template<class K, class V>
struct RBTNode
{

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

pair<K, V> _kv;
RBTNode<K, V>* _left;
RBTNode<K, V>* _right;
RBTNode<K, V>* _parent;
color _col;//节点颜色
};



template<class K, class V>
class RBTree
{
typedef RBTNode<K, V> Node;

public:

//构造
RBTree() = default;
//拷贝构造
RBTree(const RBTree<K, V>& t)
{
_root = Copy(t._root);
}

//赋值运算符重载
void operator=(const RBTree<K, V>& t)
{
RBTree<K, V> new_t(t);
std::swap(new_t._root, _root);
}

//析构
~RBTree()
{
Destroy(_root);
_root = nullptr;
}

void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
Node* Copy(const Node* root)
{
if (root == nullptr)
return nullptr;
Node* newnode = new Node(root->kv);
newnode->_left = Copy(root->_left);
newnode->_right = Copy(root->_right);

return newnode;
}



//插入
bool Insert(const pair<K, V>& kv);

//搜索
Node* Find(const K& x);

//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}

//树的高度
int Height()
{
return _Height(_root);
}

//统计节点总个数(插入时可能会有重复数据)
int Size()
{
return _Size(_root);
}

private:

//左单旋
void RotateL(Node* parent);
//右单旋
void RotateR(Node* parent);


//中序遍历(子函数)
void _InOrder(Node* root)
{
if (root == nullptr)
return;

_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}

//树的高度
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;
}

//统计节点总个数(插入时可能会有重复数据)
int _Size(Node* root)
{
return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}

private:
Node* _root = nullptr;
};





//插入
template<class K, class V>
bool RBTree<K, V>::Insert(const pair<K, V>& kv)
{
//链表为空特殊处理
if (_root == nullptr)
{
_root = new Node(kv, 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;
}
//需要插入一个新的红色节点
cur = new Node(kv);
if (cur->_kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//判断是否需要对树进行调整
while (parent && parent->_col==RED)//如果父节点颜色为红需要调整
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)//叔叔在右
{
Node* uncle = grandparent->_right;

if (uncle && uncle->_col == RED)//当叔叔存在且为红时
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;

cur = grandparent;
parent = grandparent->_parent;
}
else//叔叔为黑或不存在
{
if (cur == parent->_left)//三节点同在左，右单旋
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else//p节点在g左，cue节点在p右，左右双旋
{
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
}
else//叔叔在左
{
Node* uncle = grandparent->_left;

if (uncle && uncle->_col == RED)//当叔叔存在且为红时
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;

cur = grandparent;
parent = grandparent->_parent;
}
else//叔叔为黑或不存在
{
if (cur == parent->_right)//三节点同在右，左单旋
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else//p节点在g右，cue节点在p左，右左双旋
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}


//搜索
template<class K, class V>
RBTNode<K, V>* RBTree<K, V>::Find(const K& x)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < x)
{
cur = cur->_right;
}
else if (cur->_kv.first > x)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}


//左单旋
template<class K, class V>
void RBTree<K, V>::RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;

//修改向下链接内容
parent->_right = subRL;
subR->_left = parent;
//修改向上链接内容
subR->_parent = parent->_parent;
parent->_parent = subR;
if (subRL)//防止该树点为空
{
subRL->_parent = parent;
}

//parent的parent向下链接
Node* parentParent = subR->_parent;
if (parentParent == nullptr)//整棵树的根
{
_root = subR;
}
else
{
if (parent == parentParent->_right)
{
parentParent->_right = subR;
}
else
{
parentParent->_left = subR;
}
}
}

//右单旋
template<class K, class V>
void RBTree<K, V>::RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;

//修改向下链接内容
parent->_left = subLR;
subL->_right = parent;
//修改向上链接属性
subL->_parent = parent->_parent;
parent->_parent = subL;
if (subLR)
{
subLR->_parent = parent;
}
//修改parentParent
Node* parentParent = subL->_parent;
if (parentParent == nullptr)
{
_root = subL;
}
else
{
if (parent == parentParent->_right)
{
parentParent->_right = subL;
}
else
{
parentParent->_left = subL;

}
}
}

原文地址：https://blog.csdn.net/atlanteep/article/details/140656361

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：存储过程及触发器
下一篇：C#高级：枚举（Enum）从索引、值到注释的完整使用技巧

基于SpringBoot的旅游网站的设计与实现
首页：展示网站的核心功能和服务，方便用户快速了解网站。个人中心：提供用户的个人信息管理功能，包括查看和修改资料等。用户管理：对用户进行管理和审核，确保网站的安全性。线路分类管理：对旅游线路进行分类管理
阅读更多2024-10-18
【无标题】
Apache Hive 是一个分布式、容错的数据仓库系统，能够实现大规模的分析。Hive Metastore (HMS) 提供了一个元数据存储库，可以轻松分析这些元数据以做出基于数据的决策，因此它是许
阅读更多2024-10-18
刚刚，ChatGPT推出Windows客户端！
刚刚，ChatGPT推出Windows客户端！
阅读更多2024-10-18
MAC 电脑Office power point编辑的时候，显示“某些字体无法随演示文稿一起保存，仍然要保存演示文稿吗？”
在使用mac电脑的power point打开别人的.ppt文件之后，在保存的时候，弹出““某些字体无法随演示文稿一起保存，仍然要保存演示文稿吗？”，每次只要保存就需要重新嵌入字体很麻烦，如何解决这个问
阅读更多2024-10-18
VMware NSX 4.2.1 发布，新增功能概览
VMware NSX 4.2.1 发布，新增功能概览
阅读更多2024-10-18
【JAVA毕业设计】基于Vue和SpringBoot的课程智能组卷系统
随着教育信息化的推进，越来越多的学校和教育机构开始采用智能组卷系统，市场需求不断增加，为智能组卷系统的发展提供了广阔的市场空间。因此，从技术、教学效果、市场需求等多个方面来看，课程智能组卷系统具有较高
阅读更多2024-10-18
计算机毕业设计hadoop+spark知识图谱中药推荐系统中药材推荐系统中药可视化中药数据分析中药爬虫机器学习深度学习人工智能大数据
计算机毕业设计hadoop+spark知识图谱中药推荐系统中药材推荐系统中药可视化中药数据分析中药爬虫机器学习深度学习人工智能大数据
阅读更多2024-10-18
4.8 大数据发展趋势
我想与大家探讨一个充满潜力和变革的主题——大数据的发展趋势。大数据不仅正在改变我们的工作和生活方式，更是推动社会进步和经济发展的关键因素。
阅读更多2024-10-18
k8s备份恢复工具--velero
k8s的备份和恢复工具主要包括服务端和客户端两部分，服务端运行在k8s集群中，客户端运行在本地的命令行，本地需要配置好k8s的kubeconfig和kubectl客户端工具需要对象存储当做中间备份或存
阅读更多2024-10-18
【Python数据可视化】利用Matplotlib绘制美丽图表！
Matplotlib 是 Python 中一个广泛使用的 2D 图形绘图库，提供了从简单到复杂的各种图表类型。它以简单易用的 API 和丰富的自定义能力为用户所喜爱。无论是科研、工程应用，还是金融数据
阅读更多2024-10-18