红黑树

5个基本性质

1. 每个节点要么是红，要么是黑
2. 根节点是黑
3. 每个叶子节点是黑的
4. 如果一个节点是红的，那么子节点都是黑的
5. 对于每个节点，该节点到根的所有路径包含有相同的黑节点

插入

新节点默认为红色。若插入黑色节点，必然破坏性质5；插入红色则需要分情况讨论。

插入流程先按平衡二叉树的方式进行，保持查找特性不变，但可能破坏红黑树性质，因此需要对树进行调整以恢复性质。

左右旋转

STL XTREE代码

	void _Lrotate(_Nodeptr _Wherenode)
		{	// promote right node to root of subtree
		_Nodeptr _Pnode = this->_Right(_Wherenode);
		this->_Right(_Wherenode) = this->_Left(_Pnode);

		if (!this->_Isnil(this->_Left(_Pnode)))
			this->_Parent(this->_Left(_Pnode)) = _Wherenode;
		this->_Parent(_Pnode) = this->_Parent(_Wherenode);

		if (_Wherenode == _Root())
			_Root() = _Pnode;
		else if (_Wherenode == this->_Left(this->_Parent(_Wherenode)))
			this->_Left(this->_Parent(_Wherenode)) = _Pnode;
		else
			this->_Right(this->_Parent(_Wherenode)) = _Pnode;

		this->_Left(_Pnode) = _Wherenode;
		this->_Parent(_Wherenode) = _Pnode;
		}


	void _Rrotate(_Nodeptr _Wherenode)
		{	// promote left node to root of subtree
		_Nodeptr _Pnode = this->_Left(_Wherenode);
		this->_Left(_Wherenode) = this->_Right(_Pnode);

		if (!this->_Isnil(this->_Right(_Pnode)))
			this->_Parent(this->_Right(_Pnode)) = _Wherenode;
		this->_Parent(_Pnode) = this->_Parent(_Wherenode);

		if (_Wherenode == _Root())
			_Root() = _Pnode;
		else if (_Wherenode == this->_Right(this->_Parent(_Wherenode)))
			this->_Right(this->_Parent(_Wherenode)) = _Pnode;
		else
			this->_Left(this->_Parent(_Wherenode)) = _Pnode;

		this->_Right(_Pnode) = _Wherenode;
		this->_Parent(_Wherenode) = _Pnode;
		}
插入，mark一下，插入只有四种情况，需要修复

xtree(1833)

	template<class _Valty,
	class _Nodety>
		iterator _Insert_at(bool _Addleft, _Nodeptr _Wherenode,
		_Valty&& _Val, _Nodety _Node)
	{	// add node with value next to _Wherenode, to left if _Addleft
			if (max_size() - 1 <= this->_Mysize)
			{	// tree would get too big, fail
				_Destroy_if_not_nil(_Node);
				_Xlength_error("map/set<T> too long");
			}
			_Nodeptr _Newnode = _Buynode_if_nil(_Node,
				_STD forward<_Valty>(_Val));

			++this->_Mysize;
			_Newnode->_Parent = _Wherenode;

			if (_Wherenode == this->_Myhead)
			{	// first node in tree, just set head values
				_Root() = _Newnode;
				_Lmost() = _Newnode;
				_Rmost() = _Newnode;
			}
			else if (_Addleft)
			{	// add to left of _Wherenode
				this->_Left(_Wherenode) = _Newnode;
				if (_Wherenode == _Lmost())
					_Lmost() = _Newnode;
			}
			else
			{	// add to right of _Wherenode
				this->_Right(_Wherenode) = _Newnode;
				if (_Wherenode == _Rmost())
					_Rmost() = _Newnode;
			}

			for (_Nodeptr _Pnode = _Newnode;
				this->_Color(this->_Parent(_Pnode)) == this->_Red;)
			if (this->_Parent(_Pnode)
				== this->_Left(this->_Parent(this->_Parent(_Pnode))))
			{	// fixup red-red in left subtree
				_Wherenode =
					this->_Right(this->_Parent(this->_Parent(_Pnode)));
				if (this->_Color(_Wherenode) == this->_Red)
				{	// parent has two red children, blacken both
					this->_Color(this->_Parent(_Pnode)) = this->_Black;
					this->_Color(_Wherenode) = this->_Black;
					this->_Color(this->_Parent(this->_Parent(_Pnode)))
						= this->_Red;
					_Pnode = this->_Parent(this->_Parent(_Pnode));
				}
				else
				{	// parent has red and black children
					if (_Pnode == this->_Right(this->_Parent(_Pnode)))
					{	// rotate right child to left
						_Pnode = this->_Parent(_Pnode);
						_Lrotate(_Pnode);
					}
					this->_Color(this->_Parent(_Pnode)) =
						this->_Black;	// propagate red up
					this->_Color(this->_Parent(this->_Parent(_Pnode))) =
						this->_Red;
					_Rrotate(this->_Parent(this->_Parent(_Pnode)));
				}
			}
			else
			{	// fixup red-red in right subtree
				_Wherenode =
					this->_Left(this->_Parent(this->_Parent(_Pnode)));
				if (this->_Color(_Wherenode) == this->_Red)
				{	// parent has two red children, blacken both
					this->_Color(this->_Parent(_Pnode)) = this->_Black;
					this->_Color(_Wherenode) = this->_Black;
					this->_Color(this->_Parent(this->_Parent(_Pnode))) =
						this->_Red;
					_Pnode = this->_Parent(this->_Parent(_Pnode));
				}
				else
				{	// parent has red and black children
					if (_Pnode == this->_Left(this->_Parent(_Pnode)))
					{	// rotate left child to right
						_Pnode = this->_Parent(_Pnode);
						_Rrotate(_Pnode);
					}
					this->_Color(this->_Parent(_Pnode)) =
						this->_Black;	// propagate red up
					this->_Color(this->_Parent(this->_Parent(_Pnode))) =
						this->_Red;
					_Lrotate(this->_Parent(this->_Parent(_Pnode)));
				}
			}

			this->_Color(_Root()) = this->_Black;	// root is always black
			return (iterator(_Newnode, this));
		}