《C++数据结构之红黑树的实现》是一篇介绍红黑树实现的文章，通过本文，你可以了解到什么是红黑树以及如何实现红黑树。
什么是红黑树
红黑树是一种自平衡的二叉查找树，它具有良好的平衡性和查找性能。红黑树可以在O(log n)的时间内完成查找、插入和删除操作。
红黑树的一个重要性质是它的任何一个节点都有一个颜色（红色或黑色）属性。在插入、删除操作中，需要通过一定的规则来对节点的颜色、位置进行调整来维持红黑树的平衡性。
红黑树的实现
红黑树的实现需要涉及到节点的定义、插入、删除、查找等操作。下面分别进行介绍。
节点的定义
红黑树节点需要保存节点的数据、颜色、指向父节点、左子树、右子树的指针。定义如下：
template<typename T>
struct RBNode {
T data;
bool color;
RBNode<T>* parent, * left, * right;
RBNode(T data, bool color = false, RBNode<T>* parent = nullptr,
RBNode<T>* left = nullptr, RBNode<T>* right = nullptr) : data(data), color(color), parent(parent), left(left), right(right) {}
};
插入操作
插入节点时，需要通过旋转和变色来保证红黑树的平衡性。
插入时，首先按照二叉查找树的规则找到插入位置，并插入一个红色节点。如果父节点是黑色，插入结束，红黑树仍然保持平衡；如果父节点是红色，则需要进行平衡操作。
平衡操作有以下几种：
- 如果插入节点的父节点是爷爷节点的左孩子，则叔叔节点是右孩子：
a. 如果叔叔节点是红色的，则重新给父节点和叔叔节点涂黑色，爷爷节点涂红色，并将爷爷节点作为当前节点进行后续平衡操作。
b. 如果叔叔节点是黑色的，并且当前节点是父节点的右孩子，则左旋转父节点，并把父节点作为当前节点进行后续平衡操作。
c. 如果叔叔节点是黑色的，并且当前节点是父节点的左孩子，则将父节点涂黑色，爷爷节点涂红色，然后以爷爷节点为支点进行右旋转。
- 如果插入节点的父节点是爷爷节点的右孩子：
a. 如果叔叔节点是红色的，则重新给父节点和叔叔节点涂黑色，爷爷节点涂红色，并将爷爷节点作为当前节点进行后续平衡操作。
b. 如果叔叔节点是黑色的，并且当前节点是父节点的左孩子，则右旋转父节点，并把父节点作为当前节点进行后续平衡操作。
c. 如果叔叔节点是黑色的，并且当前节点是父节点的右孩子，则将父节点涂黑色，爷爷节点涂红色，然后以爷爷节点为支点进行左旋转。
插入操作的代码实现如下：
template<typename T>
void RBTree<T>::insertFixup(RBNode<T>* node) {
while (node->parent && node->parent->color == red) {
RBNode<T>* p = node->parent;
RBNode<T>* g = node->parent->parent;
if (p == g->left) {
RBNode<T>* u = g->right;
if (u && u->color == red) {
p->color = black;
u->color = black;
g->color = red;
node = g;
}
else {
if (node == p->right) {
node = p;
leftRotate(node);
p = node->parent;
}
p->color = black;
g->color = red;
rightRotate(g);
}
}
else {
RBNode<T>* u = g->left;
if (u && u->color == red) {
p->color = black;
u->color = black;
g->color = red;
node = g;
}
else {
if (node == p->left) {
node = p;
rightRotate(node);
p = node->parent;
}
p->color = black;
g->color = red;
leftRotate(g);
}
}
}
root->color = black;
}
template<typename T>
void RBTree<T>::insert(T data) {
// 创建插入节点
RBNode<T>* node = new RBNode<T>(data, red);
// 查找插入位置
RBNode<T>* p = nullptr;
RBNode<T>* cur = root;
while (cur) {
p = cur;
if (data < cur->data) {
cur = cur->left;
}
else {
cur = cur->right;
}
}
// 连接父节点和插入节点
node->parent = p;
if (!p) {
root = node;
}
else if (data < p->data) {
p->left = node;
}
else {
p->right = node;
}
// 修复红黑树
insertFixup(node);
}
删除操作
删除节点时，是突出之处。当要删除的节点有两个非空子节点时，无法直接删除该节点。如果直接删除该节点，会破坏红黑树的平衡性，因此，在删除前需要找到要删除节点的前驱或后继节点来替换要删除的节点。同时，需要进行旋转和变色来保持红黑树平衡。
① 如果要删除的节点没有孩子或只有一个孩子，直接删除。
② 如果要删除的节点有两个孩子，则找到它的后继节点（该节点的左子树中最小的节点），并将后继节点的数据替换到要删除的节点中，然后删除后继节点。
删除操作的代码实现如下：
template<typename T>
void RBTree<T>::removeFixup(RBNode<T>* node, RBNode<T>* p) {
while (node != root && (!node || node->color == black)) {
if (node == p->left) {
RBNode<T>* s = p->right;
if (s->color == red) {
s->color = black;
p->color = red;
leftRotate(p);
s = p->right;
}
if ((!s->left || s->left->color == black) && (!s->right || s->right->color == black)) {
s->color = red;
node = p;
p = p->parent;
}
else {
if (!s->right || s->right->color == black) {
s->left->color = black;
s->color = red;
rightRotate(s);
s = p->right;
}
s->color = p->color;
p->color = black;
s->right->color = black;
leftRotate(p);
node = root;
}
}
else {
RBNode<T>* s = p->left;
if (s->color == red) {
s->color = black;
p->color = red;
rightRotate(p);
s = p->left;
}
if ((!s->right || s->right->color == black) && (!s->left || s->left->color == black)) {
s->color = red;
node = p;
p = p->parent;
}
else {
if (!s->left || s->left->color == black) {
s->right->color = black;
s->color = red;
leftRotate(s);
s = p->left;
}
s->color = p->color;
p->color = black;
s->left->color = black;
rightRotate(p);
node = root;
}
}
}
if (node) {
node->color = black;
}
}
template<typename T>
void RBTree<T>::remove(const T& data) {
RBNode<T>* node = searchNode(data);
if (!node) {
return;
}
// 记录删除节点的颜色和父节点
bool color = node->color;
RBNode<T>* p = node->parent;
// 如果有两个孩子，则找到后继节点，用后继节点替代
if (node->left && node->right) {
RBNode<T>* s = node->right;
while (s->left) {
s = s->left;
}
node->data = s->data;
node = s;
p = s->parent;
color = s->color;
}
// 替换节点为其左右孩子节点
RBNode<T>* child = node->left ? node->left : node->right;
if (child) {
child->parent = p;
}
if (!p) {
root = child;
}
else if (node == p->left) {
p->left = child;
}
else {
p->right = child;
}
// 修复红黑树
if (color == black) {
removeFixup(child, p);
}
delete node;
}
查找操作
查找操作与普通二叉查找树中的查找操作相同，效率为O(log n)。具体实现如下：
template<typename T>
RBNode<T>* RBTree<T>::searchNode(const T& data) const {
RBNode<T>* cur = root;
while (cur) {
if (cur->data == data) {
return cur;
}
else if (data < cur->data) {
cur = cur->left;
}
else {
cur = cur->right;
}
}
return nullptr;
}
示例说明
下面给出两个关于红黑树的示例：
示例一
给定一个字符串数组，如何用红黑树实现字符串去重？
思路：遍历字符串数组，将其插入红黑树中，如果遇到重复的字符串，则不插入，最终得到的树中的所有节点即为去重后的字符串。插入时，需要重载比较运算符。
代码实现：
#include "RBTree.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
vector<string> strs = { "hello", "world", "hello", "cpp", "world" };
RBTree<string> tree;
for (auto& str : strs) {
tree.insert(str);
}
// 输出去重后的字符串
tree.inOrder([](const string& str) {
cout << str << " ";
});
// 输出结果：cpp hello world
return 0;
}
示例二
如何用红黑树实现一个有序集合？
思路：通过红黑树来实现一个有序集合，可以保证该集合中的元素按照从小到大的顺序排列。在插入节点和删除节点时，保持红黑树的平衡性，通过遍历树，可以输出有序集合中的元素。
代码实现：
#include "RBTree.h"
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> nums = { 3, 1, 4, 5, 2 };
RBTree<int> tree;
for (auto& num : nums) {
tree.insert(num);
}
// 遍历树，输出集合元素
tree.inOrder([](int num) {
cout << num << " ";
});
// 输出结果：1 2 3 4 5
return 0;
}
以上就是关于C++数据结构之红黑树的实现的完整攻略，希望能对你有所帮助。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C++数据结构之红黑树的实现 - Python技术站
微信扫一扫 
支付宝扫一扫 