以下是一个简单的红黑树实现代码示例:
#include <iostream>
enum class Color { RED, BLACK };
template <typename T>
class Node {
public:
T data;
Color color;
Node<T>* parent;
Node<T>* left;
Node<T>* right;
Node(T data) : data(data), color(Color::RED), parent(nullptr), left(nullptr), right(nullptr) {}
};
template <typename T>
class RedBlackTree {
private:
Node<T>* root;
void rotateLeft(Node<T>* node) {
Node<T>* temp = node->right;
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<T>* node) {
Node<T>* temp = node->left;
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<T>* newNode = new Node<T>(data);
Node<T>* parent = nullptr;
Node<T>* current = root;
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<T>* node) {
while(node != root && node->parent->color == Color::RED) {
if(node->parent == node->parent->parent->left) {
Node<T>* uncle = node->parent->parent->right;
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<T>* uncle = node->parent->parent->left;
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<int> rbTree;
rbTree.insert(10);
rbTree.insert(20);
rbTree.insert(30);
return 0;
}
这段代码实现了一个简单的红黑树,并实现了插入节点以及插入后的修复操作。您可以根据需要进行扩展和修改。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,请发送邮件至 55@qq.com 举报,一经查实,本站将立刻删除。转转请注明出处:https://www.szhjjp.com/n/1009671.html