1.红黑树的性质
- 根、叶子为黑节点
- 红节点的子节点为黑，不能连续为红
- 从任一节点到其每个叶子节点的所有路径上黑节点数相同
2.C++结构定义
- 先定义节点、再定义树结构
- 因为叶子节点都隐藏，所以统一指向一个
哨兵节点
typedef struct _rbree_node {int key;void *value;struct _rbree_node* left;struct _rbree_node* right;struct _rbree_node* parent;int color;
}rbree_node;typedef struct _rbtree
{rbree_node* root;rbree_node* nil; // 哨兵节点
} rbtree;
- 进一步改进，封装红黑树的性质，这样不同类型的树都可以调用节点，增加复用性
3.左右旋转(两个参数T,x or T,y)
- 左右旋要换三对边:
左旋为例:
- x-r->b
if b != nil
b-p->x- y-p = x-p
if x-p == nil:
T-root->y
if x-p != nil:
if x-p-l == x:
y-p-l = y
if x-p-r == x:
y-p-r = y- y-l = x
x-p = y
右旋时，把左旋中x y left right互相调换
4.插入
- 红黑树在插入一个节点前已经是红黑树
– 因为插入一个红色节点不改变红黑树的规则（路径上黑节点相等），所以给新插入的节点一律赋值为红色，然后再做调整
– 调整过程就是把红色向上层层传导的过程
2无法直接调平衡，需要先转成3，再调平衡
5.删除
6.完整实现
#include <iostream>
using namespace std;// 定义颜色枚举，红色和黑色
enum Color { RED, BLACK };// 定义红黑树的节点结构
struct Node {int data; // 节点存储的数据bool color; // 节点颜色（RED 或 BLACK）Node *left, *right, *parent; // 左子节点、右子节点和父节点指针// 构造函数，初始化节点Node(int data) {this->data = data;left = right = parent = nullptr; // 初始时子节点和父节点为空this->color = RED; // 新插入的节点默认为红色}
};// 定义红黑树类
class RBTree {
private:Node *root; // 根节点protected:// 保护成员函数，用于内部操作void rotateLeft(Node *&, Node *&); // 左旋void rotateRight(Node *&, Node *&); // 右旋void fixViolation(Node *&, Node *&); // 修复红黑树性质public:// 构造函数，初始化根节点为空RBTree() { root = nullptr; }// 插入节点void insert(const int &data);// 中序遍历void inorder();// 层序遍历void levelOrder();// 查询节点Node* search(int data);private:// 中序遍历辅助函数void inorderHelper(Node *root);// 层序遍历辅助函数void levelOrderHelper(Node *root);// 查询节点辅助函数Node* searchHelper(Node *root, int data);
};// 左旋操作
void RBTree::rotateLeft(Node *&root, Node *&pt) {Node *pt_right = pt->right; // 获取当前节点的右子节点pt->right = pt_right->left; // 将右子节点的左子树作为当前节点的右子树if (pt->right != nullptr)pt->right->parent = pt; // 更新父节点指针pt_right->parent = pt->parent; // 更新右子节点的父节点if (pt->parent == nullptr)root = pt_right; // 如果当前节点是根节点，更新根节点else if (pt == pt->parent->left)pt->parent->left = pt_right; // 如果当前节点是左子节点，更新父节点的左子节点elsept->parent->right = pt_right; // 如果当前节点是右子节点，更新父节点的右子节点pt_right->left = pt; // 将当前节点作为右子节点的左子节点pt->parent = pt_right; // 更新当前节点的父节点
}// 右旋操作
void RBTree::rotateRight(Node *&root, Node *&pt) {Node *pt_left = pt->left; // 获取当前节点的左子节点pt->left = pt_left->right; // 将左子节点的右子树作为当前节点的左子树if (pt->left != nullptr)pt->left->parent = pt; // 更新父节点指针pt_left->parent = pt->parent; // 更新左子节点的父节点if (pt->parent == nullptr)root = pt_left; // 如果当前节点是根节点，更新根节点else if (pt == pt->parent->left)pt->parent->left = pt_left; // 如果当前节点是左子节点，更新父节点的左子节点elsept->parent->right = pt_left; // 如果当前节点是右子节点，更新父节点的右子节点pt_left->right = pt; // 将当前节点作为左子节点的右子节点pt->parent = pt_left; // 更新当前节点的父节点
}// 修复红黑树性质
void RBTree::fixViolation(Node *&root, Node *&pt) {Node *parent_pt = nullptr;Node *grand_parent_pt = nullptr;// 当当前节点不是根节点，且当前节点是红色，且父节点也是红色时，需要修复while ((pt != root) && (pt->color != BLACK) &&(pt->parent->color == RED)) {parent_pt = pt->parent; // 父节点grand_parent_pt = pt->parent->parent; // 祖父节点// 父节点是祖父节点的左子节点if (parent_pt == grand_parent_pt->left) {Node *uncle_pt = grand_parent_pt->right; // 叔叔节点// 情况 1：叔叔节点是红色if (uncle_pt != nullptr && uncle_pt->color == RED) {grand_parent_pt->color = RED;parent_pt->color = BLACK;uncle_pt->color = BLACK;pt = grand_parent_pt; // 将当前节点指向祖父节点，继续修复}else {// 情况 2：节点是父节点的右子节点if (pt == parent_pt->right) {rotateLeft(root, parent_pt); // 左旋pt = parent_pt;parent_pt = pt->parent;}// 情况 3：节点是父节点的左子节点rotateRight(root, grand_parent_pt); // 右旋swap(parent_pt->color, grand_parent_pt->color); // 交换颜色pt = parent_pt; // 将当前节点指向父节点}}// 父节点是祖父节点的右子节点else {Node *uncle_pt = grand_parent_pt->left; // 叔叔节点// 情况 1：叔叔节点是红色if ((uncle_pt != nullptr) && (uncle_pt->color == RED)) {grand_parent_pt->color = RED;parent_pt->color = BLACK;uncle_pt->color = BLACK;pt = grand_parent_pt; // 将当前节点指向祖父节点，继续修复}else {// 情况 2：节点是父节点的左子节点if (pt == parent_pt->left) {rotateRight(root, parent_pt); // 右旋pt = parent_pt;parent_pt = pt->parent;}// 情况 3：节点是父节点的右子节点rotateLeft(root, grand_parent_pt); // 左旋swap(parent_pt->color, grand_parent_pt->color); // 交换颜色pt = parent_pt; // 将当前节点指向父节点}}}root->color = BLACK; // 根节点始终为黑色
}// 插入节点
void RBTree::insert(const int &data) {Node *pt = new Node(data); // 创建新节点if (root == nullptr) {root = pt;root->color = BLACK; // 根节点必须为黑色return;}Node *parent = nullptr;Node *current = root;// 找到插入位置while (current != nullptr) {parent = current;if (pt->data < current->data)current = current->left;elsecurrent = current->right;}pt->parent = parent; // 设置新节点的父节点if (pt->data < parent->data)parent->left = pt; // 插入到左子树elseparent->right = pt; // 插入到右子树fixViolation(root, pt); // 修复红黑树性质
}// 中序遍历辅助函数
void RBTree::inorderHelper(Node *root) {if (root == nullptr)return;inorderHelper(root->left); // 遍历左子树cout << root->data << " "; // 输出当前节点inorderHelper(root->right); // 遍历右子树
}// 中序遍历
void RBTree::inorder() {inorderHelper(root);
}// 层序遍历辅助函数
void RBTree::levelOrderHelper(Node *root) {if (root == nullptr)return;cout << root->data << " "; // 输出当前节点levelOrderHelper(root->left); // 遍历左子树levelOrderHelper(root->right); // 遍历右子树
}// 层序遍历
void RBTree::levelOrder() {levelOrderHelper(root);
}// 查询节点辅助函数
Node* RBTree::searchHelper(Node *root, int data) {if (root == nullptr || root->data == data)return root;if (data < root->data)return searchHelper(root->left, data); // 在左子树中查找return searchHelper(root->right, data); // 在右子树中查找
}// 查询节点
Node* RBTree::search(int data) {return searchHelper(root, data);
}// 测试代码
int main() {RBTree tree;// 插入节点tree.insert(7);tree.insert(3);tree.insert(18);tree.insert(10);tree.insert(22);tree.insert(8);tree.insert(11);tree.insert(26);// 中序遍历cout << "Inorder Traversal: ";tree.inorder();cout << endl;// 层序遍历cout << "Level Order Traversal: ";tree.levelOrder();cout << endl;// 查询节点Node *node = tree.search(18);if (node != nullptr)cout << "Found: " << node->data << endl;elsecout << "Not Found" << endl;return 0;
}
