目录
一、概念：
为了保持AVL树的平衡性，AVL树需要频繁地调整全树整体拓扑结构，代价较大。为此在AVL树的平衡标准上进一步放宽条件，引入红黑树的概念：
- 每个结点都是黑色或者红色
- 根结点都是黑色
- 每个叶子结点(虚构的外部节点，NULL结点)都是黑色
- 不存在两个相邻的红结点
- 对于每个结点，从该结点到任一叶节点（3中的叶子结点）的简单路径上，黑结点的个数相同
结论1：从根到叶结点的最长路径不大于最短路径，由④和⑤可知最短路径全是黑结点，最长路径是黑红结点依次相交的路径
结论2:有n个内部结点的红黑树的高度为h<=log2(n+1),由①和③可知，任何一条简单路径上都至少由一半是黑结点，树的黑高为h/2，即树高为h时并且所有黑结点能组成的高为h/2的满二叉树时，黑结点个数最多，所以n>=2^(h/2)-1-->log2(n+1)
总结：由此可见红黑树的平衡条件比AVL树宽松不少，降低了树的动态调整的次数，如果一颗动态查找树，需要较多的插入和删除，选择红黑树比AVL树合适。
二、红黑树的结点
template<class V> class RBTreeNode { public: RBTreeNode(const V& data) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(RED) {} V _data; Colour _col; RBTreeNode<V>* _left; RBTreeNode<V>* _right; RBTreeNode<V>* _parent; };
三、红黑树的插入
首先，我们需要知道每个新插入的结点都是红色，否则若是黑色结点，该条路径会比其他路径多一个黑色结点，会破坏红黑树的规则。
其插入过程如下：
- 第一步：通过比较查找合适的插入位置，然后建立新结点并且插入树中。让cur为插入结点指针，分四种情况。进入第二步：
- 第一种：插入为根节点，将颜色变为红色，否则判断插入结点的父节点的颜色
- 第二种：parent为黑色不用处理，直接return结束。
- 第三种：parent为红色，uncle（父节点的兄弟结点 ）也为红色，那么将parent和uncle变为黑色，将grandparent（父节点的父节点）变为红色，parent变为RED，grandparent变为为BLACK，cur=grantparent，判断的结点向上递增两位。返回第二步判断后处理。
- 第四种: parent为红色，uncle不存在或者为黑色，根据cur和parent以及grantparent的位置，旋转后变色，旋转分为右单旋，左单旋，先右后左单选，先左后右单旋。
第二种情况如图：
右单旋：图中情况二
类似AVL树，复用旋转函数，但是少了平衡因子变化AVL树
//旋转加变色，然后return后结束插入 rotateR(ppNode);//ppNode是爷爷结点 parent->_col = BLACK; ppNode->_col = RED;右单旋：
void rotateR(Node* parent) { Node* cur = parent->_left; Node* cur_right = cur->_right; parent->_left = cur_right; //旋转第一步parent和cur_right的链接; if (cur->_right != nullptr)//X cur_right->_parent = parent; cur->_right = parent; //再处理cur和parent的链接 Node* parent_parent = parent->_parent;//保存结点，用于处理，cur->parent; parent->_parent = cur; if (parent == _root) //处理cur和parent_parent的链接 { _root = cur; cur->_parent = nullptr;//X } else { cur->_parent = parent_parent; if (parent_parent->_left == parent) { parent_parent->_left = cur; } else { parent_parent->_right = cur; } } //parent->_bf = 0;//旋转后平衡因子为0 //cur->_bf = 0; }
先左后右双旋 ：情况1
//双旋＋变色 rotateLR(ppNode); cur->_col = BLACK; ppNode->_col = RED;左右双旋函数： 类似AVL树，复用左单旋和右单旋函数，但是少了平衡因子变化AVL树
void rotateRL(Node* parent) { Node* cur = parent->_right; Node* cur_left = cur->_left; /*int bf = cur_left->_bf;*/ rotateR(parent->_right); rotateL(parent); }
两种对称情况： 左单旋和先右后左双旋函数
void rotateRL(Node* parent) { Node* cur = parent->_right; Node* cur_left = cur->_left; /*int bf = cur_left->_bf;*/ rotateR(parent->_right); rotateL(parent); }void rotateL(Node* parent) { Node* cur = parent->_right; Node* cur_left = cur->_left; parent->_right = cur_left; if (cur_left != nullptr) cur_left->_parent = parent; cur->_left = parent; Node* ppNode = parent->_parent; parent->_parent = cur; if (parent == _root) { _root = cur; cur->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = cur; } else { ppNode->_right = cur; } cur->_parent = ppNode; } /*parent->_bf = 0; cur->_bf = 0;*/ }
四、迭代器 (核心：结点指针)
iterator++：iterator++的所指结点，为其右子树的最大值（最左结点），无右子树时，为某一祖先，即从下向上遍历，第一个祖先的左孩子为该iterator所指结点的祖先。
self& operator++() { if (_node->_right) { //右子树最小结点 Node* subLeft= _node->_right; while (subLeft->_left) { subLeft = subLeft->_left; } _node = subLeft; } else{ Node* cur = _node; Node* parent = cur->_parent; while (parent) { if (parent->_left == cur) { _node = parent; break; } else { cur = parent; parent = parent->_parent; } } if (parent == nullptr) { _node = _node->_right; } } return *this; }iterator--：同理
self& operator--() { if (_node->_left) { //左子树最大结点 Node* maxLeft = _node->_left; while (maxLeft->_right) { maxLeft = maxLeft->_right; } _node = maxLeft; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent) { //找到祖先的右孩子是该结点的祖先，就是前一个结点 if (parent->_right == cur) { _node = parent; break; } else { cur = parent; parent = parent->_parent; } } if (parent == nullptr) {//除了存在的结点，其他任何指向都为空，多此一举 _node = _node->_left; } } return *this; }
五、应用
map和set
标签：Node,map,结点,right,ordered,cur,parent,STL,left From： https://blog.csdn.net/weixin_50470247/article/details/136505675