关联式容器：观念上类似关联式数据库（实际上简单很多），每个元素都有一个键值和一个实值，当元素插入到关联容器中时，容器内部结构（RB-tree或者hash-table）依照键值将其插入到适当的位置。
AVL tree：
一种二叉搜索树。任何节点的左右子树高度最多相差1。
如果插入后平衡被破坏，则分为以下情况：
1、 插入点位于X的左子节点的左子树。 左左
2、 ……………………………… 右子数。 左右
3、 …………………右………… 左子数。 右左
4、 …………………右………… 右子数。 右右
旋转：
1、 单旋转：将违反AVL tree规则的子树的插入元素边的第一个节点提起来，变成跟节点。再调整。
2、 双旋转：从下往上，单旋转两次。
RB-TREE红黑树：
template<class Key, class Value, class KeyOfVaule,
class Compare, class Alloc>
pair<typename rb_tree<Key, Value, KeyOfVaule, Compare, Alloc>::iterator,
bool>
rb_tree<Key, Value, KeyOfVaule, Compare, Alloc>::
insert_unique(const Value& v)
{
link_type y = header;
link_type x = root(); //从根节点开始
bool comp = true;
while(x!=0) //往下寻找适合点
{
y=x;
comp = key_compare(KeyOfValue()(v), key(x)); //遇大往左，遇小往右
x = comp ? left(x) : right(x);
}
iterator j = iterator(y); //找到插入点，j是插入点的父节点。
if(comp) //如果是遇大，则分两种情况：
if(j==begin()) //一种是插入到最前端，就不用考虑插入点
return pair<iterator, bool>(__insert(x, y, v), true); //和j--可能会想等了。
else //另一种情况，因为插入值小于j节点的值
--j; //但是不确定是不是可能会等于j--节点。因此需要比较
if(key_compare(key(j.node), KeyOfValue()(v))) //这里的比较也是两种情况，1种是没有经过上面过程，
return pair<iterator, bool>(__insert(x, y v), true); //comp=0，就是插入到右节点，直接进行比较，不等于就插入。
//另一种情况是经过了上面过程，比较一下j--和插入值的大小。
return pair<iterator, bool>(j, false); //相等就不插入。
}
1、 每个节点不是红色就是黑色
2、 根节点为黑色
3、 如果节点为红色，其子节点必须为黑色
4、 任一节点至NULL（树尾端）的任何路径，所含黑节点数必须相同
由规则4 => 新增节点必须为红色。规则3 => 新增节点父节点为黑色。如果插入不满足上述要求，就需要调整RB-tree。
RB-tree迭代器和节点设计方式和slist的迭代器设计方式一样：
typedef bool __rb_tree_color_type;
const rb_tree_color_type __rb_tree_red = false;
const rb_tree_color_type __rb_tree_black = true;
struct __rb_tree_node_base
{
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color;
base_ptr parent;
base_ptr left;
base_ptr right;
static base_ptr minimum(base_ptr x);
static base_ptr maximum(base_ptr x);
};
template <class Value>
struct __rb_tree_node: public __rb_tree_node_base
{
typedef __rb_tree_node<Value>* link_type;
Value value_field;
};
struct __rb_tree_base_iterator
{
__rb_tree_node_base* node;
void increment();
void decrement();
};
template <class T, class Ref, class Ptr>
struct __rb_tree_iterator: public __rb_tree_base_iterator
{
typedef __rb_tree_node<T> *link_typed;
operator *();
operator ->();
operator ++();
operator ++(int);
operator --();
operator --(int);
};
而在迭代器中，最重要的就是increment和decrement两个函数，++，--等重载运算符调用了这两个函数。代码如下：
void increment()
{
if(node->right != 0) //情况1，有右子节点
{
node = node->right; //就向右走
while(node->left!=0)
node = node->left; //然后一直往左子树走到底,得到结果
}
else //情况2，没有右子节点
{
base_ptr y = node->parent; //找出父节点
while(node==y->right) //上溯直到所指节点不为右子节点
{
node=y;
y=y->parent;
}
if(node->right!=y) //若此时的右子节点不等于此时的父节点
node = y; //情况3，此时的父节点就是结果
//否则，情况4，此时的node为结果
//这里会出现情况4的原因，是BR-tree有个特别的header，颜色为红它的父节点为根节点，而根节点
//的父节点是header，header左子节点指向最小值，右子节点指向最大值。因此在寻找根节点的下一
//节点，而恰巧根节点没有右子节点的时候，就出现了第四种情况。
}
}
void decrement()
{
if(node->color==__rb_tree_red&&
node->parent->parent == node) //情况1
node = node->right; //当node为end()（header）的时候出现
else if(node->left!=0) //情况2
{ //如果有左子节点，结果为其左子树的
base_ptr y = node->left; //最右边叶子节点
while(y->right!=0)
y=y->right;
node = y;
}
else
{
base_ptr y = node->parent; //情况3
while(node == y->left) //如果没有左子节点，则从此节点开始上溯，
{ //找到的第一个非左子节点的父节点就是结果
node=y;
y=y->parent;
}
node = y;
}
}
RB-tree的插入，分为两种情况，一种是允许重复的键值（multset、multmap），另一个是不允许重复键值（set，map），不允许重复插入的情况代码如下：
template<class Key, class Value, class KeyOfVaule,
class Compare, class Alloc>
pair<typename rb_tree<Key, Value, KeyOfVaule, Compare, Alloc>::iterator,
bool>
rb_tree<Key, Value, KeyOfVaule, Compare, Alloc>::
insert_unique(const Value& v)
{
link_type y = header;
link_type x = root(); //从根节点开始
bool comp = true;
while(x!=0) //往下寻找适合点
{
y=x;
comp = key_compare(KeyOfValue()(v), key(x)); //遇大往左，遇小往右
x = comp ? left(x) : right(x);
}
iterator j = iterator(y); //找到插入点，j是插入点的父节点。
if(comp) //如果是遇大，则分两种情况：
if(j==begin()) //一种是插入到最前端，就不用考虑插入点
return pair<iterator, bool>(__insert(x, y, v), true); //和j--可能会想等了。
else //另一种情况，因为插入值小于j节点的值
--j; //但是不确定是不是可能会等于j--节点。因此需要比较
if(key_compare(key(j.node), KeyOfValue()(v))) //这里的比较也是两种情况，1种是没有经过上面过程，
return pair<iterator, bool>(__insert(x, y v), true); //comp=0，就是插入到右节点，直接进行比较，不等于就插入。
//另一种情况是经过了上面过程，比较一下j--和插入值的大小。
return pair<iterator, bool>(j, false); //相等就不插入。
}
其中，真正用来插入的函数是__insert，下面是insert函数代码。
template<class Key, class Value, class KeyOfVaule,
class Compare, class Alloc>
typename rb_tree<Key, Value, KeyOfVaule, Compare, Alloc>::iterator
rb_tree<Key, Value, KeyOfVaule, Compare, Alloc>::
__insert(base_ptr x_, base_ptr y_, const Value &v)
{
//参数x为插入节点，y为插入点的父节点，v为插入的新值
link_type x = (link_type) x_;
link_type y = (link_type) y_;
link_type z;
if(y==header||x!=0||key_compare(KeyOfValue()(v), key(y))) //如果本来是一颗空树，或者是要插入到y的左子节点，（x可能不等于0么？）
{
z = create_node(v); //产生一个新的节点
left(y) = z; //新节点为插入点的父节点y的左子节点
if(y==header)
posted on 2010-06-06 16:49
dead_horse 阅读(506)
评论(0) 编辑 收藏 引用 所属分类:
STL读书笔记