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++右移运算符的一个小坑及解决

C++右移运算符的一个小坑及解决

《C++右移运算符的一个小坑及解决》文章指出右移运算符处理负数时左侧补1导致死循环,与除法行为不同,强调需注意补码机制以正确统计二进制1的个数... 目录我遇到了这么一个www.chinasem.cn函数由此可以看到也很好理解总结我遇到了这么一个函数template<typename T>unsigned
阅读更多...
C++统计函数执行时间的最佳实践

C++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法
阅读更多...
深入解析C++ 中std::map内存管理

深入解析C++ 中std::map内存管理

《深入解析C++中std::map内存管理》文章详解C++std::map内存管理,指出clear()仅删除元素可能不释放底层内存,建议用swap()与空map交换以彻底释放,针对指针类型需手动de... 目录1️、基本清空std::map2️、使用 swap 彻底释放内存3️、map 中存储指针类型的对象
阅读更多...
C++ STL-string类底层实现过程

C++ STL-string类底层实现过程

《C++STL-string类底层实现过程》本文实现了一个简易的string类,涵盖动态数组存储、深拷贝机制、迭代器支持、容量调整、字符串修改、运算符重载等功能,模拟标准string核心特性,重点强... 目录实现框架一、默认成员函数1.默认构造函数2.构造函数3.拷贝构造函数(重点)4.赋值运算符重载函数
阅读更多...
C++ vector越界问题的完整解决方案

C++ vector越界问题的完整解决方案

《C++vector越界问题的完整解决方案》在C++开发中,std::vector作为最常用的动态数组容器,其便捷性与性能优势使其成为处理可变长度数据的首选,然而,数组越界访问始终是威胁程序稳定性的... 目录引言一、vector越界的底层原理与危害1.1 越界访问的本质原因1.2 越界访问的实际危害二、基
阅读更多...
c++日志库log4cplus快速入门小结

c++日志库log4cplus快速入门小结

《c++日志库log4cplus快速入门小结》文章浏览阅读1.1w次，点赞9次，收藏44次。本文介绍Log4cplus，一种适用于C++的线程安全日志记录API，提供灵活的日志管理和配置控制。文章涵盖... 目录简介日志等级配置文件使用关于初始化使用示例总结参考资料简介log4j 用于Java，log4c
阅读更多...
C++归并排序代码实现示例代码

C++归并排序代码实现示例代码

《C++归并排序代码实现示例代码》归并排序将待排序数组分成两个子数组,分别对这两个子数组进行排序,然后将排序好的子数组合并,得到排序后的数组,：本文主要介绍C++归并排序代码实现的相关资料,需要的... 目录1 算法核心思想2 代码实现3 算法时间复杂度1 算法核心思想归并排序是一种高效的排序方式，需要用
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
C++中detach的作用、使用场景及注意事项

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()？它的作用是什么？类比一下：二、join()的作用总结三、join()怎么
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2