以下是一個簡單的紅黑樹實現代碼示例:
```cpp
#include
enum class Color { RED, BLACK };
template
class Node {
public:
T data;
Color color;
Node
Node
Node
Node(T data) : data(data), color(Color::RED), parent(nullptr), left(nullptr), right(nullptr) {}
};
template
class RedBlackTree {
private:
Node
void rotateLeft(Node
Node
node->right = temp->left;
if(temp->left != nullptr) {
temp->left->parent = node;
}
temp->parent = node->parent;
if(node->parent == nullptr) {
root = temp;
} else if(node == node->parent->left) {
node->parent->left = temp;
} else {
node->parent->right = temp;
}
temp->left = node;
node->parent = temp;
}
void rotateRight(Node
Node
node->left = temp->right;
if(temp->right != nullptr) {
temp->right->parent = node;
}
temp->parent = node->parent;
if(node->parent == nullptr) {
root = temp;
} else if(node == node->parent->right) {
node->parent->right = temp;
} else {
node->parent->left = temp;
}
temp->right = node;
node->parent = temp;
}
public:
RedBlackTree() : root(nullptr) {}
void insert(T data) {
Node
Node
Node
while(current != nullptr) {
parent = current;
if(newNode->data < current->data) {
current = current->left;
} else {
current = current->right;
}
}
newNode->parent = parent;
if(parent == nullptr) {
root = newNode;
} else if(newNode->data < parent->data) {
parent->left = newNode;
} else {
parent->right = newNode;
}
// Fix the tree
insertionFixup(newNode);
}
void insertionFixup(Node
while(node != root && node->parent->color == Color::RED) {
if(node->parent == node->parent->parent->left) {
Node
if(uncle != nullptr && uncle->color == Color::RED) {
node->parent->color = Color::BLACK;
uncle->color = Color::BLACK;
node->parent->parent->color = Color::RED;
node = node->parent->parent;
} else {
if(node == node->parent->right) {
node = node->parent;
rotateLeft(node);
}
node->parent->color = Color::BLACK;
node->parent->parent->color = Color::RED;
rotateRight(node->parent->parent);
}
} else {
Node
if(uncle != nullptr && uncle->color == Color::RED) {
node->parent->color = Color::BLACK;
uncle->color = Color::BLACK;
node->parent->parent->color = Color::RED;
node = node->parent->parent;
} else {
if(node == node->parent->left) {
node = node->parent;
rotateRight(node);
}
node->parent->color = Color::BLACK;
node->parent->parent->color = Color::RED;
rotateLeft(node->parent->parent);
}
}
}
root->color = Color::BLACK;
}
};
int main() {
RedBlackTree
rbTree.insert(10);
rbTree.insert(20);
rbTree.insert(30);
return 0;
}
```
這段代碼實現了一個簡單的紅黑樹,并實現了插入節點以及插入后的修復操作。您可以根據需要進行擴展和修改。