5个基本性质
1.每个节点要么是红 要么是黑2.根节点是黑3.每个叶子节点是黑的4.如果一个节点是红的，那么子节点都是黑的5.对于每个节点，该节点到跟的所有路径包含有相同的黑节点
插入
新节点默认是红，如果是黑肯定破坏了性质，红的话还要分情况讨论插入有3种情况，先按照平衡二叉树的插入，进行，依然保持查找特性，但是可能会破坏红黑树的性质因此要对树进行调整，以保持性质。
左右旋转
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) templateiterator _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 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)); }