当前位置：首页 > news >正文

红黑树：平衡二叉查找树的经典实现

news 2025/6/14 2:01:54

红黑树：平衡二叉查找树的经典实现

红黑树（Red-Black Tree）是一种自平衡的二叉查找树，广泛应用于各种场景，比如操作系统中的进程调度、数据库中的数据索引等。它是一种高效的平衡树，能够在最坏情况下保持较低的时间复杂度，确保插入、删除和查找操作的时间复杂度为 O(log n)。

本文将介绍红黑树的基本概念、性质、操作及其应用。

一、红黑树的定义

红黑树是一棵二叉查找树，除了普通的二叉查找树性质外，它还满足以下附加性质：

每个节点要么是红色，要么是黑色。
根节点是黑色。
每个叶节点（NIL节点，空节点）是黑色。
如果一个节点是红色的，则它的两个子节点都是黑色的（即不能有两个连续的红色节点）。
从任一节点到其每个叶子节点的所有路径上都包含相同数量的黑色节点。

这些性质使得红黑树在插入和删除节点后仍然能够保持平衡。

二、红黑树的基本操作

红黑树支持常见的二叉查找树操作，如插入、删除和查找，但为了保持树的平衡，它在执行插入和删除操作时需要进行颜色调整和树的旋转操作。接下来，我们介绍这些操作的实现过程。

1. 插入操作

红黑树的插入操作和普通二叉查找树的插入类似，但在插入新节点后，可能会违反红黑树的性质。因此，插入后需要通过颜色变换和旋转操作来恢复红黑树的平衡。

具体步骤如下：

新插入的节点初始颜色为红色（为了避免增加黑色节点的路径长度）。
如果新插入节点的父节点也是红色，则违反了红黑树的性质4，需要进行调整。
通过重新着色、左旋或右旋来恢复红黑树的平衡。

2. 删除操作

红黑树的删除操作比插入操作更复杂。当删除一个节点后，可能会破坏红黑树的性质，需要对树进行调整。删除节点后，如果删除的节点是黑色，红黑树的平衡可能被破坏，因此要通过一系列旋转和颜色调整来维持红黑树的平衡。

3. 旋转操作

旋转操作是红黑树维护平衡的核心。红黑树中有两种旋转操作：

左旋：将节点的右子节点提升为父节点，原父节点成为新父节点的左子节点。
右旋：与左旋相反，将节点的左子节点提升为父节点，原父节点成为新父节点的右子节点。

通过旋转操作，红黑树能够调整树的结构，保持平衡。

三、红黑树的实现

以下是红黑树的基本实现代码：

#include <iostream>
using namespace std;// 红黑树节点颜色定义
enum Color { RED, BLACK };// 红黑树节点类
struct Node {int data;Color color;Node* left, * right, * parent;// 构造函数Node(int data) {this->data = data;left = right = parent = nullptr;this->color = RED;  // 新插入节点默认为红色}
};// 红黑树类
class RedBlackTree {
private:Node* root;protected:// 左旋操作void leftRotate(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 rightRotate(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 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;// 叔叔节点是红色，只需重新着色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 {// 叔叔节点是黑色，且当前节点是右孩子if (pt == parent_pt->right) {leftRotate(root, parent_pt);pt = parent_pt;parent_pt = pt->parent;}// 叔叔节点是黑色，且当前节点是左孩子rightRotate(root, grand_parent_pt);swap(parent_pt->color, grand_parent_pt->color);pt = parent_pt;}}// 父节点是祖父节点的右孩子else {Node* uncle_pt = grand_parent_pt->left;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 {if (pt == parent_pt->left) {rightRotate(root, parent_pt);pt = parent_pt;parent_pt = pt->parent;}leftRotate(root, grand_parent_pt);swap(parent_pt->color, grand_parent_pt->color);pt = parent_pt;}}}root->color = BLACK;}public:RedBlackTree() { root = nullptr; }// 插入新节点void insert(const int& data) {Node* pt = new Node(data);root = BSTInsert(root, pt);fixViolation(root, pt);}// 中序遍历void inorder() { inorderHelper(root); }private:// 二叉搜索树的插入Node* BSTInsert(Node* root, Node* pt) {if (root == nullptr)return pt;if (pt->data < root->data) {root->left = BSTInsert(root->left, pt);root->left->parent = root;}else if (pt->data > root->data) {root->right = BSTInsert(root->right, pt);root->right->parent = root;}return root;}// 中序遍历的帮助函数void inorderHelper(Node* root) {if (root == nullptr)return;inorderHelper(root->left);cout << root->data << " ";inorderHelper(root->right);}
};int main() {RedBlackTree 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 << "中序遍历: ";tree.inorder();cout << endl;return 0;
}