2015-08-04
敬叶 初稿

数据结构

STL关联容器包括set和map，二者底层都用红黑树实现，衍生体multiset和multimap也不例外。对应的有基于哈希表的实现，名字也很像，分别为： hash_set、hash_map、hash_multiset和hash_multimap。

关联容器内部是一个平衡二叉树，平衡二叉树包括AVL-tree、 RB-tree和AA-tree等等。红黑树应用比较广泛，Linux内核中内存管理也广泛用到红黑树。不同领域用到的树也是不尽相同的，如编译器需要表达式树，文件压缩要用哈夫曼编码树，数据库要用到复杂的B-tree。

二叉搜索树在插入和删除操作之后失去平衡就会降低搜索效率，因此在实际应用中需要让结构保持平衡。

AVL树要求高度差最大为1，插入时破坏平衡，可以调整插入点至根节点路径上破坏平衡的最深节点，假设该节点为X，根据插入节点和X的位置，可以有四种可能： X左节点左子树、X左节点右子树、X右节点左子树、X右节点右子树。

外侧插入可以通过单旋转平衡：

avl-rotate-1.png

内侧插入可以通过双旋转平衡：

avl-rotate-2.png

红黑树概念

红黑树需要满足如下规则：

  1. 根结点和NULL节点是黑色
  2. 如果节点为红，子节点为黑
  3. 任意节点至NULL节点的任意路径包含的黑色节点数相同

根据规则3，新增节点必为红色，根据规则2，新增节点的父节点必为黑色。考虑如下情形，新插入节点会破坏规则，需要作出调整。

rb-insert.png

情况1，对P、G做一次单旋转，并修改颜色：

rb-rotate-1.png

情况2，第一步对P、X单旋转，修改G、X颜色。第二步对G做一次单旋转。

rb-rotate-2.png

情况3，对P、G做单旋转，修改X颜色，如果旋转后P的父节点为黑色，无需动作，否则看情况4。

rb-rotate-3.png

情况4，对P、G做单旋转，修改X颜色，此时P的父节点为红色，继续向上做相同的操作。

rb-rotate-4.png

对于情况4，递归向上处理会降低效率，采用如下的方式来加速：假定新插入A，沿着A向上，发现一个节点X两个子节点为红色，就将该节点和子节点反色。

rb-rotate-5.png

再对上图中的G、P右旋转并反色即可，注意下图有个标注错误，X和A标记反了：

rb-rotate-6.png

红黑树实现

为了简化边界处理，SGI STL引入了一个头节点header，初始状态其父节点指向NULL，表示没有根节点，左右子节点均指向自己。当有节点时，父节点指向root，即二者互为父节点，左右子节点分别指向最左和最右节点。

任何插入都会调用调整函数以满足红黑树规范。 

 1: inline void __rb_tree_rebalance(__rb_tree_node_base *x,
 2:     __rb_tree_node_base *&root)
 3: {
 4:     x->color = __rb_tree_red;
 5:     while (x != root && x->parent->color == _rb_tree_red) {
 6:         if (x->parent == x->parent->parent->left) {
 7:             __rb_tree_node_base *y = x->parent->parent->right;
 8:             if (y && y->color == __rb_tree_red) {
 9:                 x->parent->color = __rb_tree_black;
10:                 y->color = __rb_tree_black;
11:                 x->parent->parent->color = __rb_tree_red;
12:                 x = x->parent->parent;
13:             }
14:             else {
15:                 if (x == x->parent->right) {
16:                     x = x->parent;
17:                     __rb_tree_rotate_left(x, root);
18:                 }
19:                 x->parent->color = __rb_tree_black;
20:                 x->parent->parent->color = __rb_tree_red;
21:                 __rb_tree_rotate_right(x->parent->parent, root);
22:             }
23:         }
24:         else {
25:             __rb_tree_node_base *y = x->parent->parent->left;
26:             if (y && y->color == __rb_tree_red) {
27:                 x->parent->color == __rb_tree_black;
28:                 y->color = __rb_tree_black;
29:                 x->parent->parent->color = __rb_tree_red;
30:                 x = x->parent->parent;
31:             }
32:             else {
33:                 if (x == x->parent->left) {
34:                     x = x->parent;
35:                     __rb_tree_rotate_right(x, root);
36:                 }
37:                 x->parent->color =  __rb_tree_black;
38:                 x->parent->parent->color = __rb_tree_red;
39:                 __rb_tree_rotate_left(x->parent->parent, root);
40:             }
41:         }
42:     }
43:     root->color = __rb_tree_black;
44: }
4
根据规则3，新节点颜色必为红色
5
父节点必为红色，否则没有调整的必要
6
父节点是左节点，即包含左左、左右两种情况
8-11
父节点和伯父节点都是红色，要执行反色操作
12
向上追溯
14-22
不追溯情况，执行旋转后退出循环，因为x->parent->color已经不满足循环条件
15-18
左右情况：先左旋后右旋，即情况2
19-21
左左情况：只需右旋，即情况1
24-41
这和6-23刚好互为对称操作

哈希表

哈希表首先要解决的问题是如何将一个很大的域映射到一个可以接受的范围内。这个可接受的范围实际就是允许哈希数组的大小。另一个问题就是如何解决碰撞，这里简单说明常见方法。

线性探测：

  • 插入时向下找空位
  • 查询时向下遍历，直到空位，很显然效率低
  • 删除时标记已删除即可，待整理时对其操作

二次探测：插入时向下找空位：\( H + i^2 \) 其它操作和线性探测方法上是相同。

有几个问题：

  • 线性探测可以保证每次探测都是不同的值，二次探测可否满足
  • 如果没有X，插入是否保证成功
  • 表格能否动态增长

只要保证长度为质数，负载因子在0.5以下，插入新元素探测次数小于3。

不过比较有趣的是二次探测可以在设计上化简： \[ H_i = H_0 + i^2 (mod N) \]

\[ H_{i-1} = H_0 + (i-1)^2 (mod N) \]

化简可得： \[ H_i = H_{i-1} + 2i - 1 (mod N) \]

开链法：即相同哈希值的元素插入到同一个链表中。 SGI和Linux内核都采用这种方法。

对于字符串的哈希算法，SGI提供了如下函数： 

inline size_t __stl_hash_string(const char *s)
{
    unsigned long h = 0;
    for (; *s; s++)
        h = 5 * h + *s;
    return h;
}