散列表中碰撞的解决
由于散列表的元素个数小于关键字的取值集合U, 因此会有两个不同的关键字映射到散列表的同一个槽上， 这时就发生了碰撞。发生了碰撞时， 书上给出了两种方法来解决， 而且保证此时的散列表平均情况下的查找复杂度是O(1)。
链接法
在链接法中，关键字映射到同一个槽上的元素通过一个链表来保存， 此时散列表T[0..m-1]的任意元素T[j]是一个链表， 当插入一个元素时，将元素放在它所对应的槽所指向链表的头部。 下面对链接法的性能进行分析。
定义散列表T的装载因子, 其中n是元素个数，m是散列表槽数, 我们假设元素满足简单一致散列的条件： 任何元素散列到m个槽中的每一个的可能性是相同的。
用表示链表T[j]的长度，有 $$ E[n_j] = \alpha = n/m $$
有如下性质成立：
-
链接方式散列表在简单一致假设下，查找一个不存在元素所需时间的期望为
假设查找的元素是k, 它所对应的槽为h(k)，链表T[h(k)]的长度， 所以平均情况下需要遍历一个长度为的链表，外加常数的散列函数时间和寻址T[h(k)]的时间， 总共为
-
链接方式散列表在简单一致假设下，平均查找一个已存在的元素所需的时间为
对于任意元素x，检查的元素个数等于x所在链表中，出现在x之前的元素个数加1。 设是第i个插入的元素，i=1,2,..,n, 定义：
由简单一致性假设，，所以检查元素个数的期望为：
所以平均查找时间为:
开放寻址法
在开放寻址法中，对于每一个关键字k，定义探查序列 <h(k, 0), h(k, 1),…, h(k, m-1)> 是<0, 1, …, m-1>的一个排列。在插入某一个元素x时，如果它的关键字是k, 按照它所对应的探查序列从h(k, 0)到h(k, m-1)依次检查散列表，如果h(k,i)是空槽， 那么将x插入到这个槽，否则检查h(k, i+1)。在查找时， 也是沿着探查序列开始寻找。
探查序列的计算方法有很多，比如说线性探查法，二次探查法，双重散列法。 但是这些技术都不能保证一致散列的假设： 对于每一个关键字k, <h(k, 0), h(k, 1),…, h(k, m-1)>是<0, 1, …, m-1>的任何一种排列的可能性是相同的。
在一致散列的假设下，有如下性质成立：
- 对于装载因子为的开放散列表，查找一个不存在的元素所需的探查数期望至多为 定义随机变量X为探查数，为进行了第i次探查，有:
-
向一个装载因子为的开放寻址散列表中插入一个元素，平均情况下最多进行次探查。
因为要插入一个元素x，只需要做一次查找x就能找到一个空槽，所以探查次数与查找一个不存在元素的查找相同。
-
一个装载因子为的开放散列表中查找一个存在的元素的期望探查次数至多为
对于每一个元素x，查找它所需要的探查次数与插入它所需要的探查次数相同， 对于第i个插入的元素x, 所需的探查次数最多为， 所以平均的探查次数最多为：
对比开放寻址法与链接法，链接法能够支持装载因子的情况， 而开放寻址法不能支持。
二叉查找树与红黑树
二叉查找树和红黑数都是用来存储动态集合的数据结构， 红黑树对二叉查找树进行了扩展，通过一些额外的性质， 保证了二叉查找树的平衡性， 这样就能够保证树的高度为O(lgn)， 其中n是节点的个数。 有了这些额外的性质时， 在插入节点或者删除节点的时候就需要一些额外的操作来保持这些性质。
二叉查找树的基本操作
二叉查找树所支持的基本操作有：
- 查找。 因为在二叉查找树中， 对于任何一个节点， 左子树中的关键字都小于当前节点的关键字， 而右子树中的关键字都大于当前节点的关键字， 所以可以通过一个简单的递归的来查找一个关键字： 如果关键字大于当前关键字，则递归查询右子树， 否则如果关键字小于当前关键字，递归查询左子树。
-
插入。插入也可以通过简单的递归来实现：
- 如果要插入的关键字大于当前的关键字，如果右子树为空， 则把这个节点作为当前节点的右儿子，否则递归插入到右子树
- 如果要插入的关键字小于当前的关键字，如果左子树为空， 则把这个节点作为当前节点的左儿子，否则递归插入到左子树
- 寻找二叉查找树中的最小节点和最大节点。
这两个操作是对称的，只需要给出求最小节点的方法，
采用递归的方式实现：
- 如果左子树非空，则返回左子树中的最小节点
- 否则返回当前节点
- 寻找节点x的直接前趋或者直接后继。
这两个操作是对称的，只需要给出寻找直接后继的方法：
节点x的直接后继是指关键字大于key[x]中最小的那个节点，
- 如果x的右儿子存在，那么后继在x的右子树中， 以x的右子树中的最小节点就是x的直接后继
- 如果x的右儿子不存在，那么需要
- 删除。在删除一个节点x的时候，有三种情况需要考虑：
- 如果要删除的节点是叶节点，直接删除即可。
- 如果要删除的节点只有一个儿子，那么先建立它的祖先和它儿子的父子关系, 然后把它删除。
- 如果要删除的节点有两个儿子，那么先从它的右子树中找到x的直接后继节点y， 此时y一定没有左儿子（因为如果y有左儿子的话左儿子一定大于x且小于y， 与y是x的直接后继矛盾）, 所以可以把y先从树中移除(删除y一定属于前两种情况)， 然后用y代替x的位置。
红黑树的性质
相对于二叉查找树来说，赋予了每一个节点红色或者黑色， 同时整个红黑树需要保持下面的性质：
- 每个节点或者是红的，或者是黑的
- 根节点是黑的
- 每个叶节点是黑的
- 如果一个节点是红的，那么它的两个儿子必须是黑的
- 对每一个节点，从该节点到叶节点的所有路径上包含相同数目的黑节点
其中，性质3可以不用考虑，因为在红黑树中， 所有的叶节点都是NIL, 它永远都是黑色。
有了这几条性质之后， 能保证一棵有n个节点（不包括NIL叶节点）的红黑树高度至多为2lg(n+1)。 这时，查找操作能够在O(lgn)的时间内完成。
在插入和删除时红黑树性质的保持
红黑树的性质可能在插入或者删除节点的时候被破坏， 此时需要一些操作来维护红黑数的性质。
插入
插入一个节点时，始终把新插入的节点的设成红色， 这时，会有两种原因造成红黑树性质的破坏：
- 如果新插入的节点是根节点，那么会破坏性质2
- 如果插入节点的父节点是红色，那么将会破坏性质4
函数RB-INSERT_FIX_UP()用于在插入z时红黑树T性质的保持：
def RB-INSERT-FIXUP (T, z):
while color[p[z]] = RED
do if p[z] = left[p[p[z]]]
then y ← right[p[p[z]]]
if color[y] = RED
then color[p[z]] ← BLACK ###case1
color[y] ← BLACK ###case1
color[p[p[z]]] ← RED ###case1
z ← p[p[z]] ###case1
else if z = right[p[z]]
then z ← p[z] ###case2
LEFT-ROTATE (T, z) ###case2
color[p[z]] ← BLACK ###case3
color[p[ p[z]]] ← RED ###case3
RIGHT-ROTATE (T, p[p[z]]) ###case3
else (same as then clause
with “right” and “left” exchanged)
color[root[T]] ← BLACK
这个函数能达到目的因为：
- 如果是上面的原因1违反, 那么p[z]是黑色，不会进入循环，直接在最后一行把根节点设为黑色
- 如果是原因2违反，情况就要复杂一些，不能简单地把当前节点或者其父节点设为黑色就能解决问题，
因为此时可能会导致从根到各个叶节点路径上黑节点数目不相等（经过z的个数多1）。在这种情况下，
就要想办法把性质4的不一致向根节点“传递”，因为如果这种不一致到了根节点，
直接把根节点设为红色就可以，而不会引起其他的问题, 代码中分了三种情况：
-
如果是情况1，p[z]和z的叔叔都是红色，可以把p[z]和y(z的叔叔)都设为黑色， 然后把p[p[z]]设为红色，这样就把这种红红的不一致向上传递了两层， 这种不一致在向上传递的过程中会有三种情况：
- 没有造成不一致， 因为虽然把newz = p[p[z]]设为了红色，但可能此时p[newz]也是黑色，没有违反性质4
- 造成不一致然后遇到了情况1， 这时会把这种不一致继续向上传递
- 造成不一致然后遇到了情况2，3，这时直接可以通过旋转和颜色调整解决，不用向上传递
无论是哪一种情况，要么会被解决，要么传递到根由根来解决。
- 如果是情况2，3，这时可以通过旋转和重新着色解决性质4的不一致，而不会造成其他问题。
-
删除
在删除一个节点时，如果被删除的节点是红色， 那么不会有问题，因为它的儿子和父亲都是黑色， 不会违背性质4， 同时任何路径上的黑色节点的个数也不会发生变化。 但如果删除的是一个黑色的节点y，会有以下原因导致性质违背：
- 如果y是根节点，而y的红色儿子成为了新的根，会违背性质2
- 如果y的儿子x(y最多有一个儿子，可以从二叉查找树的删除中得到这个结论)和父亲都是红色， 那么会违背性质4
- 删除y会导致经过y的路径上的黑节点数目个数少1，违背性质5
函数RB-DELETE-FIXUP()用于在删除节点x的父亲时性质维护：
def RB-DELETE-FIXUP(T, x):
while x != root[T] and color[x] = BLACK
do if x = left[p[x]]
then w ← right[p[x]]
if color[w] = RED
then color[w] ← BLACK ###case1
color[p[x]] ← RED ###case1
LEFT-ROTATE (T, p[x]) ###case1
w ← right[p[x]] ###case1
if color[left[w]] = BLACK and color[right[w]] = BLACK
then color[w] ← RED ###case2
x ← p[x] ###case2
else if color[right[w]] = BLACK
then color[left[w]] ← BLACK ###case3
color[w] ← RED ###case3
RIGHT-ROTATE (T, w) ###case3
w ← right[p[x]] ###case3
color[w] ← color[p[x]] ###case4
color[p[x]] ← BLACK ###case4
color[right[w]] ← BLACK ###case4
LEFT-ROTATE (T, p[x]) ###case4
x ← root[T] ###case4
else (same as then clause with “right” and “left” exchanged)
color[x] ← BLACK
从代码中可以看出，原因1或者原因2都没有进入循环，直接通过把x设为黑色就能解决问题。 解决原因3的基本思路是给x赋予一层多余的黑色(充当一个黑色节点的计数)，试着把这个多余的黑色往根传递, 在向上传递的过程中，可能会遇到3种情况：
- 这种多余的黑色传递到了一个红色的节点，那么直接把这个红色的节点设为黑色即可
- 在传递过程中遇到了情况3，4，可以通过旋转和颜色调整而解决问题，不会引起其他的问题
- 一直遇到情况2而传递到了根节点，这时直接去掉这个多余的黑色即可， 因为此时从根到叶节点的所有路径的黑节点数目都少1，性质5得到解决。
为什么再调整过程中旋转的次数不超过3次？简单看来，有如下转换关系：
- case1 -> case2, case3, case4,情况1结束之后将到达情况2，或情况3，或情况4
- case2 -> new while, 情况2之后将进入新的循环
- case3 -> case4，情况3将到达情况4
- case4 -> 终止，情况4之后把x设为root，将导致循环终止
情况1会有旋转，如果进入了情况3或情况4，将导致循环终止，此时旋转次数不超过3次， 但如果进入进入情况2，那么将会进入新的循环，此时有可能碰到情况1然后再次旋转， 然后进入再进入情况2…这样一直向上到根，旋转的次数可能会超过3次， 是这样吗？
上面的情况的是不可能发生的，因为情况1会把p[x]设为红色，如果此时进入情况2， 在新的循环开始时，新的x就是p[x]，它的颜色是红色，直接会退出循环，把x设为黑色， 调整结束，不会再继续向上传递。所以旋转的次数不会超过3次。