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++如何通过Qt反射机制实现数据类序列化

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类，并对数据类进行存储、打印、调试等操作。由于数据类
阅读更多...
Linux下如何使用C++获取硬件信息

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息：读取"/proc/cpuinfo"文件获取磁盘信息：读取"/proc/diskstats"文
阅读更多...
C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
Python获取C++中返回的char*字段的两种思路

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串，目前我找到两种解决问题的思路，具体实现如下：
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...
C/C++错误信息处理的常见方法及函数

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,：本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例：2. strerror()示例：3. perror(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2