红黑树：节点插入详解及其红黑树自我实现

红黑树的四个性质：

每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点）

红黑树节点的定义：

// 红黑树节点的定义template<class T>struct RBTreeNode{RBTreeNode(const T& x = T(), Color c = RED): left(nullptr), right(nullptr), parent(nullptr), data(x), color(c){}RBTreeNode<T>* left;RBTreeNode<T>* right;RBTreeNode<T>* parent;T data;Color color;};

情况一：cur节点为红色 && 叔叔节点存在且为红色

如果grandparent是根节点，调整完成后，需要将grandparent改为黑色如果grandparent是子树，grandparent一定有双亲，且grandparent的双亲如果是红色，需要继续向上调整

调整方法：

uncle，parent节点变为黑色grandparent节点变为红色

调整后：

情况二: cur节点为红色是parent左孩子，parent为红，grandparent为黑，uncle不存在 || uncle为黑

如果uncle节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，abc子树中一定有节点的颜色是黑色，就不满足性质4∶每条路径黑色节点个数相同。如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

调整方法：

将parent节点改为黑色，grandparent节点改为红色以grandparent为根节点进行右单旋

调整后：

将parent节点改为黑色，grandparent节点改为红色：

以grandparent为根节点进行右单旋：

情况三: cur节点为红色是parent右孩子，parent为红，grandparent为黑，uncle不存在 || uncle为黑

调整方法：

对以parent为根节点进行左单旋情况调整成为情况二，同理情况二

调整后：

对以parent为根节点进行左单选： 同理情况二

剩下两种情况为二、三情况中二叉树的镜像，同理二三可得

情况二中的镜像：parent为grandparent的右孩子，cur为parent的右孩子，则进行以grandparent为根节点进行左单旋转情况三中的镜像：parent为grandparent的右孩子，cur为parent的左孩子，则以parent为根节点右单旋

红黑树代码实现：

#pragma once#include <iostream>using namespace std;enum Color{RED, BLACK };//红黑树节点定义template<class T>struct RBTreeNode{RBTreeNode(const T& x = T(), Color c = RED): left(nullptr), right(nullptr), parent(nullptr), data(x), color(c){}RBTreeNode<T>* left;RBTreeNode<T>* right;RBTreeNode<T>* parent;T data;Color color;};//假设：红黑树中值是唯一的template<class T>class RBTree{typedef RBTreeNode<T> Node;public:RBTree(){head = new Node();head->left = head;head->right = head;head->parent = nullptr; // 红黑树中没有任何节点}~RBTree(){Destroy(GetRoot());delete head;head = nullptr;}bool Insert(const T& data){Node*& root = GetRoot();if (root == nullptr){root = new Node(data, BLACK);root->parent = head;head->left = root;head->right = root;return true;}//查找插入节点在二叉树中的位置Node* cur = root;Node* parent = head;while (cur != nullptr){if (cur->data > data)cur = cur->left;else if (cur->data < data)cur = cur->right;elsereturn false;}//插入新节点cur = new Node(data);if (parent->data > cur->data)parent->left = cur;elseparent->right = cur;//插入节点默认是红色的，对节点颜色开始更新while (parent != head && parent->color == RED){Node* grandFather = parent->parent;if (parent == grandFather->left){//情况一：叔叔节点存在且为红色Node* uncle = grandFather->right;if (uncle && RED == uncle->color){parent->color = BLACK;uncle->color = BLACK;grandFather->color = RED;cur = grandFather;parent = cur->parent;}else{//情况二和情况三:叔叔节点不存在 || 叔叔节点存在且为黑色if (cur == parent->right){// 情况三RotateLeft(parent);swap(parent, cur);}//情况二parent->color = BLACK;grandFather->color = RED;RotateRight(grandFather);}}else{Node* uncle = grandFather->left;if (uncle && uncle->color == RED){// 情况一的反情况parent->color = BLACK;uncle->color = BLACK;grandFather->color = RED;cur = grandFather;parent = cur->parent;}else{if (cur == parent->left){//情况三的反情况RotateRight(parent);swap(parent, cur);}//情况二的反情况parent->color = BLACK;grandFather->color = RED;RotateLeft(grandFather);}}}// 新节点插入之后，红色树中的最大或者最小节点发生变化root->color = BLACK;head->left = LeftMost();head->right = RightMost();return true;}private:void RotateRight(Node* parent){Node* subL = parent->left;Node* subLR = subL->right;parent->left = subLR;if (subLR)subLR->parent = parent;subL->right = parent;Node* pparent = parent->parent;parent->parent = subL;subL->parent = pparent;if (pparent == head){// 说明旋转之前parent一定是根节点head->parent=subL}else{if (parent=pparent->left)pparent->left = subL;elsepparent->right = subL;}}void RotateLeft(Node* parent){Node* subR = parent->right;Node* subRL = subR->left;parent->right = subRL;// 注意：右单支if (subRL)subRL->parent = parent;subR->left = parent;// 更新subR和parent的双亲Node* pparent = parent->parent;parent->parent = subR;subR->parent = pparent;// 需要处理旋转之后parent双亲的情况if (pparent == head){// 旋转之前parent是根节点head->parent = subR;}else{// 旋转之前parent是有双亲的if (parent == pparent->left)pparent->left = subR;elsepparent->right = subR;}}Node*& GetRoot(){return head->parent;}Node* LeftMost(){Node* root = GetRoot();if (nullptr == root)return head;Node* cur = root;while (cur->left)cur = cur->left;return cur;}Node* RightMost(){Node* root = GetRoot();if (nullptr == root)return head;Node* cur = root;while (cur->right)cur = cur->right;return cur;}void Destroy(Node* & root){if (root){Destroy(root->left);Destroy(root->right);delete root;root = nullptr;}}private:Node* head; // 指向红黑树中的头节点};

如果觉得《红黑树：节点插入详解及其红黑树自我实现》对你有帮助，请点赞、收藏，并留下你的观点哦！