STL源码剖析——RB

源码剖析——RB"/>

STL源码剖析——RB

花了差不多一个星期的时间读完了STL红黑树的实现，并凭理解自己写了出来
参考了《算法导论》，教你透彻了解红黑树，强烈推荐，《STL源码剖析》
记录下自己的理解

RB_TREE

红黑树优点：
与BST相比插入，查找，删除在最坏情况下的复杂度仍为O（lgn），相比BST应用范围更广
STL容器set，map都以红黑树为底层容器实现，Linux进程调度算法也用红黑树实现

四种性质：
1. 每个结点要么是红的，要么是黑
2. 根结点是黑的
3. 如果节点为红，子节点必为黑
4. 任一节点至NULL的任何路径，所含黑节点数必定相同

视NULL节点为黑
举个例子，此树为红黑树

1. 旋转

红黑树有两种旋转操作，左旋和右旋，都是为了使树保持平衡

1.1左旋

左旋将支点右子树提上去，取代支点位置，支点右子节点的左子树接到支点右子树上
相当于把左边拉高，右边降低
画图表示如下（懒用VISIO画图，手绘…）

左旋代码：

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::rb_tree_rotate_left(link_type x) {//x为旋转支点，将x右节点左旋，y顶替xlink_type y = x->right;x->right = y->left;//设父节点if (y->left != nullptr)y->left->parent = x;y->parent = x->parent;if (x == root())root() = y;else if (x == x->parent->left)x->parent->left = y;elsex->parent->right = y;//父子颠倒y->left = x;x->parent = y;
}

2.2 右旋

画图示意

右旋代码：

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::rb_tree_rotate_right(link_type x) {//x为旋转支点，将x左节点右旋，y顶替xlink_type y = x->left;x->left = y->right;if (y->right != nullptr)y->right<