一.红黑树的基本结构

基本性质：

1.与AVL树相同，红黑树也是基于BST树的，满足BST树的基本性质。

2.每一个节点都是有颜色的，红或者黑。

3.root（根节点）必须是黑色的。

4.所有叶子节点都必须是黑色的，叶子节点是NULL节点，并不存储实际数据。

5.从根节点到叶子节点，不能存在两个连续的红色节点。

6.从任意节点到叶子节点的所有简单路径都必须包含相同数目的黑色节点。

7.左右子树的高度差不能超过2倍关系。

红黑树的基本结构：

template<typename T>
class RbTree
{
public:
	RbTree()
		:root(nullptr)
	{
	}
	~RbTree() {}
private:

	enum Color
	{
		RED,
		BLACK

	};
	struct Node
	{


		Node(T data = T(), Node* left = nullptr, Node* right = nullptr, Color color = BLACK, Node* parent = nullptr)
			: m_data(data)
			, left(left)
			, right(right)
			, parent(parent)
			, color(color)
		{
		}




		T m_data;
		Node* left;
		Node* right;
		Node* parent;
		Color color;

	};

	Node* root;
};

二.常见操作

1.插入操作

红黑树的插入操作会破坏红黑树的性质，所有我们需要对其进行插入调整操作。

1.如果原树为空，直接插入，插入节点的颜色为黑色。

2.如果原树非空，为了维护红黑树的性质，我们选择插入红色节点，检查插入元素的父节点，父节点为黑色，则直接插入，如果父节点为红色，进行插入调整

插入调整的三种情况

插入调整的第一步就是将祖先节点的颜色与其孩子节点交换，但是这样祖先节点变成了红色，可能与其另一个孩子节点相冲突，所以我们需要关注祖先节点的另一个孩子节点，即插入节点的叔叔节点。

（1）如果叔叔节点为红色

如图：

我们就需要将祖先节点的颜色与其孩子节点交换，然后将叔叔节点置为黑色。

（2）如果叔叔节点为黑色，插入节点位于B节点的左孩子

如图：

我们需要先将祖先节点的颜色与其孩子节点交换，然后以A为轴，进行右旋转

（3）如果如果叔叔节点为黑色，插入节点位于B节点的右孩子

我们需要先以B节点为轴，进行左旋转，然后同情况2.

注意：所有插入调整都需要处理根节点可能在调整的过程中被变红的可能，即都需要在调整结束后强制将根节点设置为黑色。

插入操作代码实现：

//插入调整
void fixAfterinsert(Node* node)
{
	while (getColor(node->parent) == RED)
	{
		if (getLeft(getParent(getParent(node))) == getParent(node))
		{
			Node* uncle = getParent(node->parent)->right;
			if (getColor(uncle) == RED)
			{
				setColor(getParent(node->parent), RED);
				setColor(getParent(node), BLACK);
				setColor(uncle, BLACK);
				node = getParent(node->parent);


			}
			else
			{
				if (getParent(node)->right == node)
				{
					node = getParent(node);
					leftRotate(node);

				}


				setColor(getParent(node->parent), RED);
				setColor(getParent(node), BLACK);
				rightRotate(getParent(node->parent));
				break;


			}
		}
		else
		{
			Node* uncle = getParent(node->parent)->left;
			if (getColor(uncle) == RED)
			{
				setColor(getParent(node->parent), RED);
				setColor(getParent(node), BLACK);
				setColor(uncle, BLACK);
				node = getParent(node->parent);



			}
			else
			{
				if (getParent(node)->left == node)
				{
					node = getParent(node);
					rightRotate(node);


				}

				setColor(getParent(node->parent), RED);

				setColor(getParent(node), BLACK);
				leftRotate(getParent(node->parent));
				break;


			}
		}

	}
	setColor(root, BLACK);
}

2.旋转操作

（1）右旋转

//右旋转操作
void rightRotate(Node* node)
{
	Node* child = node->left;
	child->parent = node->parent;
	if (node->parent == nullptr)
	{
		root = child;
	}
	else
	{
		if (node->parent->left == node)
		{
			node->parent->left = child;
		}
		else
		{
			node->parent->right = child;
		}
	}
	node->left = child->right;
	if (child->right != nullptr)
	{
		child->right->parent = node;
	}

	child->right = node;
	node->parent = child;
}

（2）左旋转

//左旋转操作
void leftRotate(Node* node)
{
	Node* child = node->right;
	child->parent = node->parent;
	if (node->parent == nullptr)
	{
		root = child;
	}
	else
	{
		if (node->parent->left == node)
		{
			node->parent->left = child;
		}
		else
		{
			node->parent->right = child;
		}
	}
	node->right = child->left;
	if (child->left != nullptr)
	{
		child->left->parent = node;
	}

	child->left = node;
	node->parent = child;
}

3.删除操作

	//删除调整
	void fixAfterremove(Node* node)
	{
		while (getColor(node) == BLACK)
		{
			if (getLeft(getParent(node)) == node)
			{
				Node* brother = getRight(getParent(node));
				if (getColor(brother) == RED)
				{
					setColor(brother, BLACK);
					setColor(getParent(node), RED);
					leftRotate(getParent(node));
					brother = getRight(getParent(node));
				}
				if (getColor(getRight(brother)) == BLACK && getColor(getLeft(brother)) == BLACK)
				{
					setColor(brother, RED);
					node = getParent(node);
				}
				else
				{
					if (getColor(getRight(brother)) != RED)
					{
						setColor(getLeft(brother), BLACK);
						setColor(brother, RED);
						rightRotate(brother);
						brother = getRight(getParent(node));
					}
					setColor(brother, getColor(getParent(node)));
					setColor(getParent(node), BLACK);
					setColor(getRight(brother), BLACK);
					leftRotate(getParent(node));
					break;
				}

			}
			else
			{
				Node* brother = getLeft(getParent(node));
				if (getColor(brother) == RED)
				{
					setColor(brother, BLACK);
					setColor(getParent(node), RED);
					rightRotate(getParent(node));
					brother = getLeft(getParent(node));
				}
				if (getColor(getLeft(brother)) == BLACK && getColor(getRight(brother)) == BLACK)
				{
					setColor(brother, RED);
					node = getParent(node);
				}
				else
				{
					if (getColor(getLeft(brother)) != RED)
					{
						setColor(getRight(brother), BLACK);
						setColor(brother, RED);
						leftRotate(brother);
						brother = getLeft(getParent(node));
					}
					setColor(brother, getColor(getParent(node)));
					setColor(getParent(node), BLACK);
					setColor(getLeft(brother), BLACK);
					rightRotate(getParent(node));
					break;
				}
			}
		}
		setColor(node, BLACK);
	}