深入理解红黑树：在C++中实现插入、删除和查找操作

本文主要是介绍深入理解红黑树：在C++中实现插入、删除和查找操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

深入理解红黑树：在C++中实现插入、删除和查找操作

红黑树是一种自平衡二叉搜索树，广泛应用于各种算法和系统中。它通过颜色属性和旋转操作来保持树的平衡，从而保证插入、删除和查找操作的时间复杂度为O(log n)。本文将详细介绍如何在C++中实现一个红黑树，并提供插入、删除和查找操作的具体实现。

红黑树的基本性质

红黑树具有以下性质：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 每个叶子节点（NIL节点）是黑色。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的（即没有两个连续的红色节点）。
5. 对每个节点，从该节点到其所有后代叶子节点的路径上，包含相同数量的黑色节点。

这些性质确保了红黑树的平衡性，使得树的最长路径不会超过最短路径的两倍。

红黑树节点定义

首先，我们定义一个红黑树节点类，用于表示红黑树中的每个节点。

enum Color { RED, BLACK };template <typename T>
class Node {
public:T data;Color color;Node* left;Node* right;Node* parent;Node(T data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

红黑树类定义

接下来，我们定义一个红黑树类，包含红黑树的基本结构和成员函数。

template <typename T>
class RedBlackTree {
private:Node<T>* root;void rotateLeft(Node<T>*& root, Node<T>*& pt);void rotateRight(Node<T>*& root, Node<T>*& pt);void fixInsert(Node<T>*& root, Node<T>*& pt);void fixDelete(Node<T>*& root, Node<T>*& pt);void inorderHelper(Node<T>* root);Node<T>* BSTInsert(Node<T>* root, Node<T>* pt);Node<T>* minValueNode(Node<T>* node);Node<T>* deleteBST(Node<T>* root, T data);public:RedBlackTree() : root(nullptr) {}void insert(const T& data);void deleteNode(const T& data);bool search(const T& data);void inorder();
};

插入操作

插入操作包括标准的二叉搜索树插入和红黑树的修复操作。首先，我们进行标准的BST插入，然后通过旋转和重新着色来修复红黑树的性质。

template <typename T>
void RedBlackTree<T>::insert(const T& data) {Node<T>* pt = new Node<T>(data);root = BSTInsert(root, pt);fixInsert(root, pt);
}template <typename T>
Node<T>* RedBlackTree<T>::BSTInsert(Node<T>* root, Node<T>* 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;
}template <typename T>
void RedBlackTree<T>::fixInsert(Node<T>*& root, Node<T>*& pt) {Node<T>* parent_pt = nullptr;Node<T>* 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<T>* 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) {rotateLeft(root, parent_pt);pt = parent_pt;parent_pt = pt->parent;}rotateRight(root, grand_parent_pt);std::swap(parent_pt->color, grand_parent_pt->color);pt = parent_pt;}} else {Node<T>* 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) {rotateRight(root, parent_pt);pt = parent_pt;parent_pt = pt->parent;}rotateLeft(root, grand_parent_pt);std::swap(parent_pt->color, grand_parent_pt->color);pt = parent_pt;}}}root->color = BLACK;
}

删除操作

删除操作相对复杂，需要考虑多种情况。首先，我们进行标准的BST删除，然后通过旋转和重新着色来修复红黑树的性质。

template <typename T>
void RedBlackTree<T>::deleteNode(const T& data) {Node<T>* node = deleteBST(root, data);if (node != nullptr) {fixDelete(root, node);}
}template <typename T>
Node<T>* RedBlackTree<T>::deleteBST(Node<T>* root, T data) {if (root == nullptr) return root;if (data < root->data) {return deleteBST(root->left, data);} else if (data > root->data) {return deleteBST(root->right, data);}if (root->left == nullptr || root->right == nullptr) {return root;}Node<T>* temp = minValueNode(root->right);root->data = temp->data;return deleteBST(root->right, temp->data);
}template <typename T>
void RedBlackTree<T>::fixDelete(Node<T>*& root, Node<T>*& pt) {Node<T>* sibling;while (pt != root && pt->color == BLACK) {if (pt == pt->parent->left) {sibling = pt->parent->right;if (sibling->color == RED) {sibling->color = BLACK;pt->parent->color = RED;rotateLeft(root, pt->parent);sibling = pt->parent->right;}if (sibling->left->color == BLACK && sibling->right->color == BLACK) {sibling->color = RED;pt = pt->parent;} else {if (sibling->right->color == BLACK) {sibling->left->color = BLACK;sibling->color = RED;rotateRight(root, sibling);sibling = pt->parent->right;}sibling->color = pt->parent->color;pt->parent->color = BLACK;sibling->right->color = BLACK;rotateLeft(root, pt->parent);pt = root;}} else {sibling = pt->parent->left;if (sibling->color == RED) {sibling->color = BLACK;pt->parent->color = RED;rotateRight(root, pt->parent);sibling = pt->parent->left;}if (sibling->left->color == BLACK && sibling->right->color == BLACK) {sibling->color = RED;pt = pt->parent;} else {if (sibling->left->color == BLACK) {sibling->right->color = BLACK;sibling->color = RED;rotateLeft(root, sibling);sibling = pt->parent->left;}sibling->color = pt->parent->color;pt->parent->color = BLACK;sibling->left->color = BLACK;rotateRight(root, pt->parent);pt = root;}}}pt->color = BLACK;
}

查找操作

查找操作相对简单，通过比较目标值与当前节点的值，决定向左子树还是右子树移动，直到找到目标值或到达空节点。

template <typename T>
bool RedBlackTree<T>::search(const T& data) {Node<T>* current = root;while (current != nullptr) {if (data == current->data) {return true;} else if (data < current->data) {current = current->left;} else {current = current->right;}}return false;
}

中序遍历

中序遍历用于验证红黑树的结构，确保所有节点按顺序排列。

template <typename T>
void RedBlackTree<T>::inorder() {inorderHelper(root);
}template <typename T>
void RedBlackTree<T>::inorderHelper(Node<T>* root) {if (root == nullptr) return;inorderHelper(root->left);

这篇关于深入理解红黑树：在C++中实现插入、删除和查找操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---