高阶数据结构 —— 红黑树(较平衡搜索树)
文章目录
- 1. 红黑树的概念
- 1.1 红黑树的性质
- 1.2 红黑树效率的分析
- 2. 红黑树的旋转
- 2.1 情况一
- 2.2 情况二
- 2.3 情况三
- 2.4 对以上三种情况的总结
- 3. 红黑树的实现
- 3.1 红黑树的节点
- 3.2 红黑树的私有成员以及构造
- 3.3 红黑树的插入
- 3.3.1 左右单旋 的代码：
- 3.3.2 插入的代码
- 3.4 判断红黑树的代码
- 3.4.1 红黑树是否为搜索树
- 3.4.2 红黑树的性质是否满足
- 5. AVL树代码汇总
- 6. 结尾语
前言： 红黑树的实现，较AVL树实现 是简单些的，本篇博客对于旋转的讲解 不会很细节，如果 对于旋转 还有问题的朋友，可以去看一下 我的上一篇博客 AVL树的实现，看完这篇博客 再来看 红黑树的实现 就会好理解一些。
1. 红黑树的概念
红黑树 是二叉搜索树，并且 它的节点 非黑即红；它通过控制节点的颜色，从而达到 一个目的：没有任何一条路径 可以超过最短路径的两倍。这是接近平衡的，也就是说 它不能保证 树完全平衡。就像AVL树 有一点不平衡，立马就旋转；而红黑树 是 当有路径 超过 最短路径的俩倍时，才会旋转。但是 红黑树比AVL树应用的更广泛一些，因为 红黑树 旋转的次数少，而且 效率还较高。
1.1 红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点）
分析：
1，2，5 性质简单解释 ：每个节点 非黑即红；树的根节点必须是黑的；叶子节点为黑，这个意思是 NULL 节点都是 黑的。
性质3：如果一个节点是红色的，那么它的两孩子是黑色的。为什么要这样做？意思就是不能有连续的红色相连。
性质4：意思就是 每条路径上的 黑色节点 数目是相同的。
这两条性质是控制 红黑树平衡的关键。
首先了解两个概念：
- 最短路径：全是黑节点的路径
- 最长路径：最短路径的二倍，一黑一红交替组成
解释性质3：
- 最短路径是全黑的节点，最长路径是最短路径的二倍，那么 如果出现 连续的红色节点 ，那么 最长路径就会超过最短路径的二倍。
解释性质4：
- 每条路径上的黑色节点数目是相同的，这也是控制最长路径不超过最短路径的二倍的手段。可以遐想一下：每条路径本来都是黑色的节点，也就是最短路径，但是 全是黑节点的话就像当于普通的搜索树了，所以我要求插入红色节点来控制平衡，插入红色节点必须满足 不能连续的插入 红色，这就保证了 最长路径就会超过最短路径的二倍。每条路径上的黑色节点数目相同，可以想成最初始的那个形态，然后不断的插入 红色节点(可能会导致变色以及旋转 )。
1.2 红黑树效率的分析
假设红黑树中每条路径上的 黑色节点数目 是 X，红黑树的高度 是 h，N是树中节点的数目。
满二叉树 的 N = 2h-1/
那么 ：
- X <= h <= 2X
- 2X-1 <=N<= 22X-1 对应两种情况 ：全黑 和 一黑一红
X <= log 2N+1 ， X >= log 4N+1 。
严格平衡的搜索树 AVL树 效率是 log n; 而红黑树的效率是 log n ~ 2*log n。其实数据搜索的数量越大，这个二倍越可以被忽略。所以 红黑树的效率是 不错的，并且 旋转的数目也较少。
2. 红黑树的旋转
首先要明白一件事 ： 插入的节点 默认插入的 是红色的，插入红色的省事呀，想吧 ，如果插入一个黑色的节点，它的影响是较大的，它会影响这条路径上 黑色节点的数目。而且 红黑树要求所有路径的黑色节点数目相等，那么插入一个黑色节点，其余的路径也需要变动呢？综上，得出一个结论，插入的节点默认是 红色。
2.1 情况一
新插入节点 cur 的 parent 节点为红，uncle 节点存在且为红(grand节点必为黑)：
这种情况只需要变色:
- parent 和 uncle 都变成 黑
- grand 变成 红
grand变红的原因：这条子路径本来黑色节点数目为 1，但是 parent和uncle变成了 黑色，所以 为了 保持 原有黑色数目不变，将grand 变成 红。
但是 有没有可能 grand就是根节点？grand的parent如果是红色怎么办？grand的parent为黑呢？
- grand是根节点，那么 再将 grand变为 黑。
- grand的parent为红色，那么就需要继续往上更新红黑关系，因为 不允许有红色节点相连，更新的方式：
cur = grand，就相当于 grand作为新插入的节点。 - grand的parent为黑色，那么就不需要继续往上更新了。
我画的图是 在左树上插入节点，在右树上插入节点的情况，和上面完全类似。我给出图，大家下去自己完成：
2.2 情况二
新插入节点 cur 的 parent节点为红，uncle 节点存在且为黑 / uncle节点不存在(直线)：
首先看 uncle节点 不存在的情况：
这种情况 单纯的变色是不能够的，所以 需要旋转，怎么旋呢？右单旋。
然后再变色：
其次我们来看 uncle存在且为黑的情况：
其实这种情况是由情况一演变而来的：
现在发现：grand的parent 也是红色的，所以需要继续往上更新，更新后发现，uncle存在且为黑，所以需要右单旋。
最后再改变颜色：
总结：新插入节点 cur 的 parent节点为红，uncle 节点存在且为黑 / uncle节点不存在。
- 对grand节点进行 右单旋
- 将grand节点变为红，parent节点变为黑
我上面的例子用的是插入到左边，那么插入到右边，同样道理，对grand节点进行 左单旋，再将grand节点变为红，parent节点变为黑。依旧给出图，大家自行动手画：
2.3 情况三
新插入节点 cur 的 parent节点为红，uncle 节点存在且为黑 / uncle节点不存在(折线)：
先来看 uncle 不存在情况：
这种情况，单旋是不能解决问题的，所以需要双旋。
- 先对parent进行 左单旋
- 再对grand进行 右单旋
然后再变色：
再来看uncle 节点存在且为黑：
我们可以发现 都是 由情况一 转变成 情况二或者情况三 :
现在我们来对情况三 进行 双旋 ：
再进行变色:
总结： 情况二和情况三的条件貌似相同，但是 一个是直线，一个是折线。所以一个是单旋，一个是双旋。
- 对 parent进行 左单旋
- 再对grand进行 右单旋
- 最后 将cur 变为黑，将grand 变为红
当然 还是留个图给大家，这个得先对parent进行右单旋，再对grand进行左单旋：
2.4 对以上三种情况的总结
其实应该六种情况，因为 上面 举得例子都是 以插入到 左树的情况来看的，当然还有插入到右树的情况，但是 大逻辑都一样，所以总结为三种情况。
- 情况一：新插入节点 cur 的 parent 节点为红，uncle 节点存在且为红(grand节点必为黑)
- 情况二：新插入节点 cur 的 parent节点为红，uncle 节点存在且为黑 / uncle节点不存在(直线)
- 情况三：新插入节点 cur 的 parent节点为红，uncle 节点存在且为黑 / uncle节点不存在(折线)
对于情况一来说：只需要变色就好了，情况二就得 单旋 + 变色 ，情况三 得双旋 + 变色。
如果 不懂得 旋转，如何旋转 可以 看看 我上一篇博客 AVL树的实现。
3. 红黑树的实现
3.1 红黑树的节点
enum Color
{
Red,
Black
};
template<class K,class V>
struct RBtree_node
{
RBtree_node<K, V>* left_;
RBtree_node<K, V>* right_;
RBtree_node<K, V>* parents_;
std::pair<K, V> kv_;
Color col_;
RBtree_node(const std::pair<K, V>& kv)
:left_(nullptr),
right_(nullptr),
parents_(nullptr),
kv_(kv),
col_(Red)
{}
};
用三叉链进行链接，每个节点的数据是一个 pait<K,V> kv_;节点的颜色用枚举常量解决就可以了。然后是 节点的构造函数，默认颜色置为空。
3.2 红黑树的私有成员以及构造
class RBtree
{
typedef RBtree_node<K, V> Node;
private:
Node* _root;
public:
RBtree()
:_root(nullptr)
{}
3.3 红黑树的插入
3.3.1 左右单旋 的代码：
void revolov_R(Node* issue_node)
{
Node* issue_Lnode = issue_node->left_;
Node* issue_Lnode_R = issue_Lnode->right_;
Node* issue_node_parent = issue_node->parents_;
issue_node->left_ = issue_Lnode_R;
if (issue_Lnode_R)
{
issue_Lnode_R->parents_ = issue_node;
}
issue_Lnode->right_ = issue_node;
issue_node->parents_ = issue_Lnode;
if (issue_node_parent == nullptr)
{
_root = issue_Lnode;
issue_Lnode->parents_ = nullptr;
}
else
{
if (issue_node_parent->left_ == issue_node)
issue_node_parent->left_ = issue_Lnode;
else
issue_node_parent->right_ = issue_Lnode;
issue_Lnode->parents_ = issue_node_parent;
}
}
void revolov_L(Node* issue_node)
{
Node* issue_Rnode = issue_node->right_;
Node* issue_Rnode_L = issue_Rnode->left_;
Node* issue_node_parent = issue_node->parents_;
issue_node->right_ = issue_Rnode_L;
if (issue_Rnode_L)
{
issue_Rnode_L->parents_ = issue_node;
}
issue_Rnode->left_ = issue_node;
issue_node->parents_ = issue_Rnode;
if (issue_node_parent == nullptr)
{
_root = issue_Rnode;
issue_Rnode->parents_ = nullptr;
}
else
{
if (issue_node_parent->left_ == issue_node)
issue_node_parent->left_ = issue_Rnode;
else
issue_node_parent->right_ = issue_Rnode;
issue_Rnode->parents_ = issue_node_parent;
}
}
3.3.2 插入的代码
插入依据的就是 上面我们的大逻辑：判断的关键点 就是 uncle。
bool insert(const std::pair<K, V>& node)
{
if (_root == nullptr)
{
_root = new Node(node);
_root->col_ = Black;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (node.first > cur->kv_.first)
{
parent = cur;
cur = cur->right_;
}
else if (node.first < cur->kv_.first)
{
parent = cur;
cur = cur->left_;
}
else
{
assert(false);
}
}
cur = new Node(node);
cur->col_ = Red;
if (parent->kv_.first > cur->kv_.first)
{
parent->left_ = cur;
cur->parents_ = parent;
}
else
{
parent->right_ = cur;
cur->parents_ = parent;
}
/ 控制红黑树结构
while (parent && parent->col_ == Red)
{
Node* grand = parent->parents_;
/// 插入到左树
if (parent == grand->left_)
{
Node* uncle = grand->right_;
/// 情况一 ：uncle 存在且 为红
if (uncle && uncle->col_ == Red)
{
parent->col_ = Black;
uncle->col_ = Black;
grand->col_ = Red;
/// 往上更新
cur = grand;
parent = cur->parents_;
}
/// 情况二 或情况三 ：uncle 不存在或者为黑
else
{
右单旋
if (cur == parent->left_)
{
revolov_R(grand);
parent->col_ = Black;
grand->col_ = Red;
}
else
{
revolov_L(parent);
revolov_R(grand);
cur->col_ = Black;
grand->col_ = Red;
}
/ 不需要更新，跳出去
break;
}
}
/// 插入到右树
else
{
Node* uncle = grand->left_;
/// 情况一
if (uncle && uncle->col_ == Red)
{
parent->col_ = Black;
uncle->col_ = Black;
grand->col_ = Red;
/// 往上更新
cur = grand;
parent = cur->parents_;
}
else
{
左单旋
if (cur == parent->right_)
{
revolov_L(grand);
parent->col_ = Black;
grand->col_ = Red;
}
else
{
revolov_R(parent);
revolov_L(grand);
cur->col_ = Black;
grand->col_ = Red;
}
/// 不需要更新，所以跳出
break;
}
}
}
/// 走出循环 我们默认 将 根节点给为黑，这很关键 用于处理一种情况 ：那就是 单一的情况一，并且它还改变了根节点 的颜色
_root->col_ = Black;
return true;
}
3.4 判断红黑树的代码
3.4.1 红黑树是否为搜索树
走一个中序就能完成判断：
public:
void InOrder()
{
_InOrder(_root);
}
private:
void _InOrder(Node* root)
{
if (root == NULL)
return;
_InOrder(root->left_);
std::cout << root->kv_.first << ":" << root->kv_.second << std::endl;
_InOrder(root->right_);
}
3.4.2 红黑树的性质是否满足
public:
bool IsBalance()
{
if (_root && _root->col_ == Red)
{
std::cout << "根节点不是黑色" << std::endl;
return false;
}
// 最左路径黑色节点数量做基准值
int banchmark = 0;
Node* left = _root;
while (left)
{
if (left->col_ == Black)
++banchmark;
left = left->left_;
}
int blackNum = 0;
return _IsBalance(_root, banchmark, blackNum);
}
private:
bool _IsBalance(Node* root, int banchmark, int blackNum)
{
/// 判断的是 每个路径的 黑色节点数目，blacknum是基准
/// 走到空，说明 走完了一条路径
if (root == nullptr)
{
if (banchmark != blackNum)
{
std::cout << "存在路径黑色节点的数量不相等" << std::endl;
return false;
}
return true;
}
出现连续红色 也不可以
if (root->col_ == Red && root->parents_->col_ == Red)
{
std::cout << "出现连续红色节点" << std::endl;
return false;
}
/ 每条路径中黑色节点 ++
if (root->col_ == Black)
{
++blackNum;
}
return _IsBalance(root->left_, banchmark, blackNum)
&& _IsBalance(root->right_, banchmark, blackNum);
}
写完红黑树 可以 用以上方法来判断 树写的是否正确。
5. AVL树代码汇总
#include<iostream>
#include<assert.h>
#include<vector>
namespace RB_tree
{
enum Color
{
Red,
Black
};
template<class K, class V>
struct RBtree_node
{
RBtree_node<K, V>* left_;
RBtree_node<K, V>* right_;
RBtree_node<K, V>* parents_;
std::pair<K, V> kv_;
Color col_;
RBtree_node(const std::pair<K, V>& kv)
:left_(nullptr),
right_(nullptr),
parents_(nullptr),
kv_(kv),
col_(Red)
{}
};
template<class K, class V>
class RBtree
{
typedef RBtree_node<K, V> Node;
private:
Node* _root;
public:
RBtree()
:_root(nullptr)
{}
public:
bool insert(const std::pair<K, V>& node)
{
if (_root == nullptr)
{
_root = new Node(node);
_root->col_ = Black;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (node.first > cur->kv_.first)
{
parent = cur;
cur = cur->right_;
}
else if (node.first < cur->kv_.first)
{
parent = cur;
cur = cur->left_;
}
else
{
assert(false);
}
}
cur = new Node(node);
cur->col_ = Red;
if (parent->kv_.first > cur->kv_.first)
{
parent->left_ = cur;
cur->parents_ = parent;
}
else
{
parent->right_ = cur;
cur->parents_ = parent;
}
while (parent && parent->col_ == Red)
{
Node* grand = parent->parents_;
/// 插入到左树
if (parent == grand->left_)
{
Node* uncle = grand->right_;
/// 情况一
if (uncle && uncle->col_ == Red)
{
parent->col_ = Black;
uncle->col_ = Black;
grand->col_ = Red;
/// 往上更新
cur = grand;
parent = cur->parents_;
}
/// 情况二 或情况三
else
{
右单旋
if (cur == parent->left_)
{
revolov_R(grand);
parent->col_ = Black;
grand->col_ = Red;
}
else
{
revolov_L(parent);
revolov_R(grand);
cur->col_ = Black;
grand->col_ = Red;
}
break;
}
}
/// 插入到右树
else
{
Node* uncle = grand->left_;
/// 情况一
if (uncle && uncle->col_ == Red)
{
parent->col_ = Black;
uncle->col_ = Black;
grand->col_ = Red;
/// 往上更新
cur = grand;
parent = cur->parents_;
}
else
{
左单旋
if (cur == parent->right_)
{
revolov_L(grand);
parent->col_ = Black;
grand->col_ = Red;
}
else
{
revolov_R(parent);
revolov_L(grand);
cur->col_ = Black;
grand->col_ = Red;
}
break;
}
}
}
_root->col_ = Black;
return true;
}
private:
void revolov_R(Node* issue_node)
{
Node* issue_Lnode = issue_node->left_;
Node* issue_Lnode_R = issue_Lnode->right_;
Node* issue_node_parent = issue_node->parents_;
issue_node->left_ = issue_Lnode_R;
if (issue_Lnode_R)
{
issue_Lnode_R->parents_ = issue_node;
}
issue_Lnode->right_ = issue_node;
issue_node->parents_ = issue_Lnode;
if (issue_node_parent == nullptr)
{
_root = issue_Lnode;
issue_Lnode->parents_ = nullptr;
}
else
{
if (issue_node_parent->left_ == issue_node)
issue_node_parent->left_ = issue_Lnode;
else
issue_node_parent->right_ = issue_Lnode;
issue_Lnode->parents_ = issue_node_parent;
}
}
void revolov_L(Node* issue_node)
{
Node* issue_Rnode = issue_node->right_;
Node* issue_Rnode_L = issue_Rnode->left_;
Node* issue_node_parent = issue_node->parents_;
issue_node->right_ = issue_Rnode_L;
if (issue_Rnode_L)
{
issue_Rnode_L->parents_ = issue_node;
}
issue_Rnode->left_ = issue_node;
issue_node->parents_ = issue_Rnode;
if (issue_node_parent == nullptr)
{
_root = issue_Rnode;
issue_Rnode->parents_ = nullptr;
}
else
{
if (issue_node_parent->left_ == issue_node)
issue_node_parent->left_ = issue_Rnode;
else
issue_node_parent->right_ = issue_Rnode;
issue_Rnode->parents_ = issue_node_parent;
}
}
public:
void InOrder()
{
_InOrder(_root);
}
private:
void _InOrder(Node* root)
{
if (root == NULL)
return;
_InOrder(root->left_);
std::cout << root->kv_.first << ":" << root->kv_.second << std::endl;
_InOrder(root->right_);
}
public:
bool IsBalance()
{
if (_root && _root->col_ == Red)
{
std::cout << "根节点不是黑色" << std::endl;
return false;
}
// 最左路径黑色节点数量做基准值
int banchmark = 0;
Node* left = _root;
while (left)
{
if (left->col_ == Black)
++banchmark;
left = left->left_;
}
int blackNum = 0;
return _IsBalance(_root, banchmark, blackNum);
}
private:
bool _IsBalance(Node* root, int banchmark, int blackNum)
{
if (root == nullptr)
{
if (banchmark != blackNum)
{
std::cout << "存在路径黑色节点的数量不相等" << std::endl;
return false;
}
return true;
}
if (root->col_ == Red && root->parents_->col_ == Red)
{
std::cout << "出现连续红色节点" << std::endl;
return false;
}
if (root->col_ == Black)
{
++blackNum;
}
return _IsBalance(root->left_, banchmark, blackNum)
&& _IsBalance(root->right_, banchmark, blackNum);
}
};
}
6. 结尾语
以上本期内容，有问题私信或者评论。