源码剖析——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<
更多推荐
STL源码剖析——RB
发布评论