我要评论
❀红黑树
前言： 在数据结构的浩瀚星空中，红黑树犹如一颗璀璨的明珠，以其独特的自平衡特性和高效的搜索能力，成为了计算机科学领域中不可或缺的一部分。红黑树，作为二叉搜索树的一种变体，通过引入节点颜色的概念和一系列复杂的旋转操作，巧妙地解决了传统二叉搜索树在极端情况下退化为链表的问题
本篇文章，将带您一起揭开红黑树的神秘面纱。我们将从红黑树的基本概念出发，逐步深入到其内部结构、性质、操作原理以及实际应用等多个方面。通过生动的图解、详细的步骤解析和丰富的实例代码，帮助您全面理解红黑树的精髓和魅力
让我们一起踏上学习 红黑树 的旅程，探索它带来的无尽可能！
📒1. 红黑树的概念
红黑树由rudolf bayer在1972年发明，最初被称为平衡二叉b树（symmetric binary b-trees），后来被guibas和robert sedgewick修改为如今的“红黑树”。
红黑树的性质：
📙2. 红黑树结构
📜3. 红黑树节点的定义
红黑树节点的定义通常包含以下几个关键部分：
基本元素：
节点颜色(color)：
构造函数：
节点定义示例(c++)：
enum color
{
red,
black
};
template<class k, class v>
struct rbtreenode
{
rbtreenode<k, v>* _left; // 该节点的左孩子
rbtreenode<k, v>* _right; // 该节点的右孩子
rbtreenode<k, v>* _parent; // 该节点的父亲
pair<k, v> _kv; // pair
color _col; // 该节点的颜色
rbtreenode(const pair<k, v>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(red)
{}
};
📚4. 红黑树的插入
红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步：
在我们进行插入操作之前，我们先定义一个红黑树的类
红黑树定义示例(c++)：
template<class k, class v>
class rbttree
{
typedef bstreenode<k, v> node;
public:
// 其他未实现的成员函数
private:
node* _root = nullptr;
};
红黑树的插入操作类似于我们之前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)
{
parent = cur;
if (cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
cur = cur->_left;
}
else
{
return false;
}
}
// 新增节点给红色
cur = new node(kv);
cur->_col = red;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
// 检测新节点插入后，红黑树的性质是否造到破坏
return true;
}
🌈检测红黑树是否造到破坏
（如果遭到破坏则对当前红黑树进行变色，旋转处理）
约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
🌞情况一
cur为红，p为红，g为黑，u存在且为红
解决方式：将parent,uncle改为黑，g改为红，然后把g当成cur，继续向上调整。
🌙情况二
cur为红，p为红，g为黑，u不存在/u存在且为黑
解决方式： p为g的左孩子，cur为p的左孩子，则进行右单旋转；p为g的右孩子，cur为p的右孩子，则进行左单旋转
⭐情况三
cur为红，p为红，g为黑，u不存在/u存在且为黑
解决方式： p为g的左孩子，cur为p的右孩子，则针对p做左右双旋；p为g的右孩子，cur为p的左孩子，则针对p做右左旋转
检测红黑树是否造到破坏代码演示(c++)：
while (parent && parent->_col == red)
{
node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
// g
// p u
// c
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)
{
// 单旋
// g
// p
// c
rotater(grandfather);
parent->_col = black;
grandfather->_col = red;
}
else
{
// 双旋
// g
// p
// c
rotatel(parent);
rotater(grandfather);
cur->_col = black;
grandfather->_col = red;
}
break;
}
}
else // parent == grandfather->_right
{
// g
// u p
// c
//
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
{
// g
// u p
// c
//
rotater(parent);
rotatel(grandfather);
cur->_col = black;
grandfather->_col = red;
}
break;
}
}
}
_root->_col = black;
红黑树的旋转和avl树差不多，我们直接上代码回顾以下：
旋转代码示例(c++)：
void rotatel(node* parent) // 左旋
{
node* subr = parent->_right;
node* subrl = subr->_left;
parent->_right = subrl;
subr->_left = parent;
node* parentparent = parent->_parent;
parent->_parent = subr;
if (subrl)
{
subrl->_parent = parent;
}
// 判断parent是不是根节点
if (_root == parent)
{
_root = subr;
subr->_parent = nullptr;
}
else
{
if (parent == parentparent->_left)
{
parentparent->_left = subr;
}
else
{
parentparent->_right = subr;
}
subr->_parent = parentparent;
}
}
void rotater(node* parent) // 右旋
{
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(_root == parent)
{
_root = subl;
subl->_parent = nullptr;
}
else
{
if (parent == parentparent->_left)
{
parentparent->_left = subl;
}
else
{
parentparent->_right = subl;
}
subl->_parent = parentparent;
}
}
📝5. 红黑树的验证
红黑树的检测分为两步：
中序遍历代码演示(c++)：
void inorder()
{
_inorder(_root);
cout << endl;
}
void _inorder(node* root)
{
if (root == nullptr)
{
return;
}
_inorder(root->_left);
cout << root->_kv.first << " ";
_inorder(root->_right);
}
检测其是否满足红黑树的性质(c++)：
bool check(node* root, int blacknum, const int refval)
{
if (root == nullptr)
{
// 走到null之后，判断refval和blacknum是否相等
if (blacknum != refval)
{
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, refval)
&& check(root->_right, blacknum, refval);
}
bool isbalance()
{
if (_root == nullptr)
{
// 空树也是红黑树
return true;
}
if(_root->_col == red)
{
return false;
}
// 参考值
// 检测是否满足红黑树的性质，refval用来记录路径中黑色节点的个数
int refval = 0;
node* cur = _root;
while (cur)
{
if (cur->_col == black)
{
++refval;
}
cur = cur->_left;
}
// 获取任意一条路径中黑色节点的个数
int blacknum = 0;
return check(_root, blacknum, refval);
}
测试：
int main()
{
rbtree<int, int> t;
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for(auto e : a)
{
t.insert(make_pair(e, e));
}
t.inorder();
cout << t.isbalance() << endl;
return 0;
}
没有出现问题，暂时认为此红黑树创建成功！
📘6. 红黑树与avl树的比较
红黑树与avl树在平衡策略、性能特性和实现复杂度等方面存在显著差异。在选择使用哪种数据结构时，需要根据具体的应用场景和需求进行权衡和选择。
📖7. 总结
随着我们对红黑树深入而细致的探讨，这段关于自平衡二叉搜索树的探索之旅也即将画上圆满的句号。红黑树，以其独特的魅力和卓越的性能，不仅在理论上为我们揭示了数据结构的精妙与复杂，更在实际应用中展现了其无可替代的价值与力量
红黑树的故事并未结束。随着技术的不断发展和应用场景的不断拓展，红黑树也将继续发挥其独特的作用，为我们解决更多复杂的问题和挑战。同时，红黑树所蕴含的算法思想和数据结构设计的智慧也将激励着我们不断学习和探索，追求更加高效、优雅和简洁的编程之道
希望本文能够为你提供有益的参考和启示，让我们一起在编程的道路上不断前行！
谢谢大家支持本篇到这里就结束了，祝大家天天开心！
发表评论