C++ -- 红黑树的基本操作

2024-06-17 17:44
文章标签 c++ 基本操作 红黑树

本文主要是介绍C++ -- 红黑树的基本操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

摘要

基本规则

基本操作

利用Graphviz 库

总结

摘要

红黑树是一种自平衡的二叉搜索树，它在插入和删除节点时，通过颜色和旋转操作保持树的平衡，确保插入、删除和查找的时间复杂度都是 (O(log n))。红黑树的每个节点都有一个颜色属性，红色或黑色。通过一些规则，红黑树保持了相对平衡，使得最长路径长度不会超过最短路径长度的两倍。

基本规则

1. 每个节点不是红色就是黑色。
2. 根节点是黑色。
3. 每个叶子节点（NIL节点）是黑色。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
5. 从任一节点到其每个叶子的所有简单路径都包含相同数量的黑色节点。

基本操作

插入操作

#include <iostream>enum Color { RED, BLACK };struct Node {int data;Color color;Node *left, *right, *parent;Node(int data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};class RedBlackTree {
public:RedBlackTree() : root(nullptr) {}void insert(int data) {Node* newNode = new Node(data);root = bstInsert(root, newNode);fixViolation(newNode);}void inorder() { inorderHelper(root); }private:Node* root;Node* bstInsert(Node* root, Node* node) {if (root == nullptr) return node;if (node->data < root->data) {root->left = bstInsert(root->left, node);root->left->parent = root;} else if (node->data > root->data) {root->right = bstInsert(root->right, node);root->right->parent = root;}return root;}void fixViolation(Node* node) {Node* parent = nullptr;Node* grandParent = nullptr;while (node != root && node->color == RED && node->parent->color == RED) {parent = node->parent;grandParent = parent->parent;if (parent == grandParent->left) {Node* uncle = grandParent->right;if (uncle != nullptr && uncle->color == RED) {grandParent->color = RED;parent->color = BLACK;uncle->color = BLACK;node = grandParent;} else {if (node == parent->right) {rotateLeft(parent);node = parent;parent = node->parent;}rotateRight(grandParent);std::swap(parent->color, grandParent->color);node = parent;}} else {Node* uncle = grandParent->left;if (uncle != nullptr && uncle->color == RED) {grandParent->color = RED;parent->color = BLACK;uncle->color = BLACK;node = grandParent;} else {if (node == parent->left) {rotateRight(parent);node = parent;parent = node->parent;}rotateLeft(grandParent);std::swap(parent->color, grandParent->color);node = parent;}}}root->color = BLACK;}void rotateLeft(Node* node) {Node* rightNode = node->right;node->right = rightNode->left;if (node->right != nullptr) node->right->parent = node;rightNode->parent = node->parent;if (node->parent == nullptr) root = rightNode;else if (node == node->parent->left) node->parent->left = rightNode;else node->parent->right = rightNode;rightNode->left = node;node->parent = rightNode;}void rotateRight(Node* node) {Node* leftNode = node->left;node->left = leftNode->right;if (node->left != nullptr) node->left->parent = node;leftNode->parent = node->parent;if (node->parent == nullptr) root = leftNode;else if (node == node->parent->left) node->parent->left = leftNode;else node->parent->right = leftNode;leftNode->right = node;node->parent = leftNode;}void inorderHelper(Node* root) {if (root == nullptr) return;inorderHelper(root->left);std::cout << root->data << " ";inorderHelper(root->right);}
};int main() {RedBlackTree tree;tree.insert(10);tree.insert(20);tree.insert(30);tree.insert(15);std::cout << "Inorder traversal of the constructed tree is ";tree.inorder();std::cout << std::endl;return 0;
}

// Output
Inorder traversal of the constructed tree is 10 15 20 3020(B)/    \
10(B)  30(B)\15(R)

插入和删除操作

#include <iostream>
#include <queue>enum Color { RED, BLACK };struct Node {int data;Color color;Node *left, *right, *parent;Node(int data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}Node* sibling() {if (parent == nullptr) return nullptr;return this == parent->left ? parent->right : parent->left;}bool hasRedChild() {return (left != nullptr && left->color == RED) || (right != nullptr && right->color == RED);}
};class RedBlackTree {
public:Node* root;RedBlackTree() : root(nullptr) {}void insert(int data) {Node* newNode = new Node(data);root = bstInsert(root, newNode);fixViolation(newNode);}void deleteNode(int data) {Node* nodeToDelete = search(root, data);if (nodeToDelete == nullptr) return;deleteBSTNode(nodeToDelete);}void inorder() { inorderHelper(root); }void levelOrder() {if (root == nullptr) return;std::queue<Node*> q;q.push(root);while (!q.empty()) {Node* temp = q.front();std::cout << temp->data << " ";q.pop();if (temp->left != nullptr)q.push(temp->left);if (temp->right != nullptr)q.push(temp->right);}}private:Node* bstInsert(Node* root, Node* node) {if (root == nullptr) return node;if (node->data < root->data) {root->left = bstInsert(root->left, node);root->left->parent = root;} else if (node->data > root->data) {root->right = bstInsert(root->right, node);root->right->parent = root;}return root;}Node* search(Node* root, int data) {if (root == nullptr || root->data == data) return root;return data < root->data ? search(root->left, data) : search(root->right, data);}void deleteBSTNode(Node* node) {Node* replacement = BSTreplace(node);bool bothBlack = ((replacement == nullptr || replacement->color == BLACK) && (node->color == BLACK));Node* parent = node->parent;if (replacement == nullptr) {if (node == root) {root = nullptr;} else {if (bothBlack) {fixDoubleBlack(node);} else {if (node->sibling() != nullptr) node->sibling()->color = RED;}if (node == node->parent->left) {node->parent->left = nullptr;} else {node->parent->right = nullptr;}}delete node;return;}if (node->left == nullptr || node->right == nullptr) {if (node == root) {node->data = replacement->data;node->left = node->right = nullptr;delete replacement;} else {if (node == node->parent->left) {parent->left = replacement;} else {parent->right = replacement;}delete node;replacement->parent = parent;if (bothBlack) {fixDoubleBlack(replacement);} else {replacement->color = BLACK;}}return;}std::swap(node->data, replacement->data);deleteBSTNode(replacement);}Node* BSTreplace(Node* node) {if (node->left != nullptr && node->right != nullptr) return successor(node->right);if (node->left == nullptr && node->right == nullptr) return nullptr;return node->left != nullptr ? node->left : node->right;}Node* successor(Node* node) {Node* temp = node;while (temp->left != nullptr) temp = temp->left;return temp;}void fixViolation(Node* node) {Node* parent = nullptr;Node* grandParent = nullptr;while (node != root && node->color == RED && node->parent->color == RED) {parent = node->parent;grandParent = parent->parent;if (parent == grandParent->left) {Node* uncle = grandParent->right;if (uncle != nullptr && uncle->color == RED) {grandParent->color = RED;parent->color = BLACK;uncle->color = BLACK;node = grandParent;} else {if (node == parent->right) {rotateLeft(parent);node = parent;parent = node->parent;}rotateRight(grandParent);std::swap(parent->color, grandParent->color);node = parent;}} else {Node* uncle = grandParent->left;if (uncle != nullptr && uncle->color == RED) {grandParent->color = RED;parent->color = BLACK;uncle->color = BLACK;node = grandParent;} else {if (node == parent->left) {rotateRight(parent);node = parent;parent = node->parent;}rotateLeft(grandParent);std::swap(parent->color, grandParent->color);node = parent;}}}root->color = BLACK;}void fixDoubleBlack(Node* node) {if (node == root) return;Node* sibling = node->sibling();Node* parent = node->parent;if (sibling == nullptr) {fixDoubleBlack(parent);} else {if (sibling->color == RED) {parent->color = RED;sibling->color = BLACK;if (sibling == parent->left) {rotateRight(parent);} else {rotateLeft(parent);}fixDoubleBlack(node);} else {if (sibling->hasRedChild()) {if (sibling->left != nullptr && sibling->left->color == RED) {if (sibling == parent->left) {sibling->left->color = sibling->color;sibling->color = parent->color;rotateRight(parent);} else {sibling->left->color = parent->color;rotateRight(sibling);rotateLeft(parent);}} else {if (sibling == parent->left) {sibling->right->color = parent->color;rotateLeft(sibling);rotateRight(parent);} else {sibling->right->color = sibling->color;sibling->color = parent->color;rotateLeft(parent);}}parent->color = BLACK;} else {sibling->color = RED;if (parent->color == BLACK) {fixDoubleBlack(parent);} else {parent->color = BLACK;}}}}}void rotateLeft(Node* node) {Node* rightNode = node->right;node->right = rightNode->left;if (node->right != nullptr) node->right->parent = node;rightNode->parent = node->parent;if (node->parent == nullptr) root = rightNode;else if (node == node->parent->left) node->parent->left = rightNode;else node->parent->right = rightNode;rightNode->left = node;node->parent = rightNode;}void rotateRight(Node* node) {Node* leftNode = node->left;node->left = leftNode->right;if (node->left != nullptr) node->left->parent = node;leftNode->parent = node->parent;if (node->parent == nullptr) root = leftNode;else if (node == node->parent->left) node->parent->left = leftNode;else node->parent->right = leftNode;leftNode->right = node;node->parent = leftNode;}void inorderHelper(Node* root) {if (root == nullptr) return;inorderHelper(root->left);std::cout << root->data << " ";inorderHelper(root->right);}
};int main() {RedBlackTree tree;tree.insert(10);tree.insert(20);tree.insert(30);tree.insert(15);tree.insert(25);tree.insert(5);std::cout << "Inorder traversal of the constructed tree is ";tree.inorder();std::cout << std::endl;tree.deleteNode(20);std::cout << "Inorder traversal after deleting 20 is ";tree.inorder();std::cout << std::endl;std::cout << "Level order traversal of the tree is ";tree.levelOrder();std::cout << std::endl;return 0;
}

// OutputInorder traversal of the constructed tree is 5 10 15 20 25 30 
Inorder traversal after deleting 20 is 5 10 15 25 30 
Level order traversal of the tree is 15 10 30 5 25 15(B)/    \
10(B)  30(B)/     /
5(B)  25(R)

利用Graphviz 库

利用 Graphviz 库的图形化表示我们需要生成的红黑树。

Graphviz Online

#include <iostream>
#include <fstream>
#include <queue>enum Color { RED, BLACK };struct Node {int data;Color color;Node *left, *right, *parent;Node(int data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}Node* sibling() {if (parent == nullptr) return nullptr;return this == parent->left ? parent->right : parent->left;}bool hasRedChild() {return (left != nullptr && left->color == RED) || (right != nullptr && right->color == RED);}
};class RedBlackTree {
public:Node* root;RedBlackTree() : root(nullptr) {}void insert(int data) {Node* newNode = new Node(data);root = bstInsert(root, newNode);fixViolation(newNode);}void deleteNode(int data) {Node* nodeToDelete = search(root, data);if (nodeToDelete == nullptr) return;deleteBSTNode(nodeToDelete);}void inorder() { inorderHelper(root); }void levelOrder() {if (root == nullptr) return;std::queue<Node*> q;q.push(root);while (!q.empty()) {Node* temp = q.front();std::cout << temp->data << " ";q.pop();if (temp->left != nullptr)q.push(temp->left);if (temp->right != nullptr)q.push(temp->right);}}void generateGraphviz(const std::string& filename) {std::ofstream file(filename);file << "digraph G {\n";if (root == nullptr) {file << "}\n";return;}generateGraphvizHelper(file, root);file << "}\n";}private:Node* bstInsert(Node* root, Node* node) {if (root == nullptr) return node;if (node->data < root->data) {root->left = bstInsert(root->left, node);root->left->parent = root;} else if (node->data > root->data) {root->right = bstInsert(root->right, node);root->right->parent = root;}return root;}Node* search(Node* root, int data) {if (root == nullptr || root->data == data) return root;return data < root->data ? search(root->left, data) : search(root->right, data);}void deleteBSTNode(Node* node) {Node* replacement = BSTreplace(node);bool bothBlack = ((replacement == nullptr || replacement->color == BLACK) && (node->color == BLACK));Node* parent = node->parent;if (replacement == nullptr) {if (node == root) {root = nullptr;} else {if (bothBlack) {fixDoubleBlack(node);} else {if (node->sibling() != nullptr) node->sibling()->color = RED;}if (node == node->parent->left) {node->parent->left = nullptr;} else {node->parent->right = nullptr;}}delete node;return;}if (node->left == nullptr || node->right == nullptr) {if (node == root) {node->data = replacement->data;node->left = node->right = nullptr;delete replacement;} else {if (node == node->parent->left) {parent->left = replacement;} else {parent->right = replacement;}delete node;replacement->parent = parent;if (bothBlack) {fixDoubleBlack(replacement);} else {replacement->color = BLACK;}}return;}std::swap(node->data, replacement->data);deleteBSTNode(replacement);}Node* BSTreplace(Node* node) {if (node->left != nullptr && node->right != nullptr) return successor(node->right);if (node->left == nullptr && node->right == nullptr) return nullptr;return node->left != nullptr ? node->left : node->right;}Node* successor(Node* node) {Node* temp = node;while (temp->left != nullptr) temp = temp->left;return temp;}void fixViolation(Node* node) {Node* parent = nullptr;Node* grandParent = nullptr;while (node != root && node->color == RED && node->parent->color == RED) {parent = node->parent;grandParent = parent->parent;if (parent == grandParent->left) {Node* uncle = grandParent->right;if (uncle != nullptr && uncle->color == RED) {grandParent->color = RED;parent->color = BLACK;uncle->color = BLACK;node = grandParent;} else {if (node == parent->right) {rotateLeft(parent);node = parent;parent = node->parent;}rotateRight(grandParent);std::swap(parent->color, grandParent->color);node = parent;}} else {Node* uncle = grandParent->left;if (uncle != nullptr && uncle->color == RED) {grandParent->color = RED;parent->color = BLACK;uncle->color = BLACK;node = grandParent;} else {if (node == parent->left) {rotateRight(parent);node = parent;parent = node->parent;}rotateLeft(grandParent);std::swap(parent->color, grandParent->color);node = parent;}}}root->color = BLACK;}void fixDoubleBlack(Node* node) {if (node == root) return;Node* sibling = node->sibling();Node* parent = node->parent;if (sibling == nullptr) {fixDoubleBlack(parent);} else {if (sibling->color == RED) {parent->color = RED;sibling->color = BLACK;if (sibling == parent->left) {rotateRight(parent);} else {rotateLeft(parent);}fixDoubleBlack(node);} else {if (sibling->hasRedChild()) {if (sibling->left != nullptr && sibling->left->color == RED) {if (sibling == parent->left) {sibling->left->color = sibling->color;sibling->color = parent->color;rotateRight(parent);} else {sibling->left->color = parent->color;rotateRight(sibling);rotateLeft(parent);}} else {if (sibling == parent->left) {sibling->right->color = parent->color;rotateLeft(sibling);rotateRight(parent);} else {sibling->right->color = sibling->color;sibling->color = parent->color;rotateLeft(parent);}}parent->color = BLACK;} else {sibling->color = RED;if (parent->color == BLACK) {fixDoubleBlack(parent);} else {parent->color = BLACK;}}}}}void rotateLeft(Node* node) {Node* rightNode = node->right;node->right = rightNode->left;if (node->right != nullptr) node->right->parent = node;rightNode->parent = node->parent;if (node->parent == nullptr) root = rightNode;else if (node == node->parent->left) node->parent->left = rightNode;else node->parent->right = rightNode;rightNode->left = node;node->parent = rightNode;}void rotateRight(Node* node) {Node* leftNode = node->left;node->left = leftNode->right;if (node->left != nullptr) node->left->parent = node;leftNode->parent = node->parent;if (node->parent == nullptr) root = leftNode;else if (node == node->parent->left) node->parent->left = leftNode;else node->parent->right = leftNode;leftNode->right = node;node->parent = leftNode;}void inorderHelper(Node* root) {if (root == nullptr) return;inorderHelper(root->left);std::cout << root->data << " ";inorderHelper(root->right);}void generateGraphvizHelper(std::ofstream& file, Node* root) {if (root->left != nullptr) {file << root->data << " -> " << root->left->data << ";\n";generateGraphvizHelper(file, root->left);} else {file << "null" << root->data << "L [shape=point];\n";file << root->data << " -> null" << root->data << "L;\n";}if (root->right != nullptr) {file << root->data << " -> " << root->right->data << ";\n";generateGraphvizHelper(file, root->right);} else {file << "null" << root->data << "R [shape=point];\n";file << root->data << " -> null" << root->data << "R;\n";}}
};int main() {RedBlackTree tree;tree.insert(10);tree.insert(20);tree.insert(30);tree.insert(15);tree.insert(25);tree.insert(5);tree.generateGraphviz("rbtree.dot");std::cout << "Graphviz dot file generated as rbtree.dot" << std::endl;return 0;
}

// Output
digraph G {
10 -> 5;
10 -> 20;
20 -> 15;
20 -> 30;
30 -> 25;
null5L [shape=point];
5 -> null5L;
null5R [shape=point];
5 -> null5R;
null15L [shape=point];
15 -> null15L;
null15R [shape=point];
15 -> null15R;
null25L [shape=point];
25 -> null25L;
null25R [shape=point];
25 -> null25R;
null30L [shape=point];
30 -> null30L;
null30R [shape=point];
30 -> null30R;
}10/  \
5    20/  \15  30/25

总结

红黑树（Red-Black Tree）是一种自平衡二叉搜索树，常用于需要高效插入、删除和查找操作的数据结构中。红黑树的特点包括每个节点是红色或黑色、根节点是黑色、红色节点的子节点必须是黑色、从任一节点到其每个叶子节点的路径上的黑色节点数目相同。

这篇关于C++ -- 红黑树的基本操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1070122。

相关文章

【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...
c++的初始化列表与const成员

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量，在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员，因为执行构造函数时，类对象已经创建完成，只有类对象创建完成才能调用成员函数，构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化，该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面，主要用于给
阅读更多...
2024/9/8 c++ smart

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2