用C++写一个红黑树
时间: 2023-07-04 10:04:45 浏览: 55
好的,以下是一个简单的红黑树实现:
```c++
#include <iostream>
using namespace std;
// 红黑树节点
enum Color {
RED,
BLACK
};
class Node {
public:
int value;
Color color;
Node* left;
Node* right;
Node* parent;
Node(int value) {
this->value = value;
color = RED;
left = nullptr;
right = nullptr;
parent = nullptr;
}
};
// 红黑树类
class RedBlackTree {
private:
Node* root;
void leftRotate(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != nullptr) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
} else if (x->parent->left == x) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void rightRotate(Node* x) {
Node* y = x->left;
x->left = y->right;
if (y->right != nullptr) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
} else if (x->parent->left == x) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->right = x;
x->parent = y;
}
void insertFixup(Node* z) {
while (z->parent != nullptr && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
Node* y = z->parent->parent->right;
if (y != nullptr && y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
z = z->parent;
leftRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(z->parent->parent);
}
} else {
Node* y = z->parent->parent->left;
if (y != nullptr && y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
rightRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(z->parent->parent);
}
}
}
root->color = BLACK;
}
public:
RedBlackTree() {
root = nullptr;
}
void insert(int value) {
Node* z = new Node(value);
Node* y = nullptr;
Node* x = root;
while (x != nullptr) {
y = x;
if (z->value < x->value) {
x = x->left;
} else {
x = x->right;
}
}
z->parent = y;
if (y == nullptr) {
root = z;
} else if (z->value < y->value) {
y->left = z;
} else {
y->right = z;
}
insertFixup(z);
}
void inorderTraversal(Node* node) {
if (node == nullptr) {
return;
}
inorderTraversal(node->left);
cout << node->value << " ";
inorderTraversal(node->right);
}
void printInorder() {
inorderTraversal(root);
cout << endl;
}
};
int main() {
RedBlackTree tree;
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(15);
tree.insert(18);
tree.insert(25);
tree.printInorder();
return 0;
}
```
这个红黑树实现还比较基础,但可以满足大部分需求。当然,实际应用中可能需要进行更多的优化。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)