《算法》搜索笔记

• 符号表（symbol table）又被称为字典（dictionary），索引
• 二叉查找树，红黑树，散列表
• 递归的实现更容易验证其正确性，而非递归实现效率更高

符号表的实现

• 包含键值对的链表，无论是put还是get都是无顺序查找
  • 像一个空表中插入n个不同的键需要N^2次比较
• 有序数组，当插入和查询的时候利用二分查找确认位置
  • 插入很慢，因为每次插入的时候需要移动数组
• 二分查找树

二分查找树（Binary Search Tree）

• 每个节点包括一个左儿子，一个右儿子，一个键，一个值，一个结点计数器
• 对一个序列而言，有序的BST可能不止一棵，然后将BST投影到一根直线上，其必定是有序序列，即所有有序的BST在直线上的投影都是一致的
  • 
• 无论是查找还是插入都是lgn，而且代码实现都很简单
• 但最坏情形为n，不可接受
• 实现有两个儿子的节点的删除最为困难

INSERT

• 若大于根节点，则插入右子树
• 若小于根节点，则插入左子树

FLOOR

• 若小于根节点，则一定存在于左子树
• 若大于根节点，则可能存在于右子树

删除

• 若只有一个儿子，则用该儿子代替父亲即可
• 若有两个儿子，则用后继代替该点，再删除该后继（即右子树中的最小值）即可

散列表

拉链法 separate chaining

线性探测法 linear probing

散列函数应该易于计算并且能够均匀分布所有的键

对于每种类型的键我们都需要一个与之对应的散列函数

除留余数法 modular hashing

• 选择大小为素数M的数组，对于任意正整数k,计算k除以M的余数
• 由于我们需要的是数组的索引，所以可以将其符号位mask掉

浮点数

• 如果键是0到1之间的实数，将键表示为二进制然后使用除留余数法
• java对于浮点数的默认方法

字符串

• Horner方法
• java对于String的默认方法

        int hash = 0;
        for (int i = 0; i < s.length(); i++)
            hash = (R * hash + s.charAt(i)) % M;
  

组合键

• 对于Date类型

        int hash = (((day * R + month) % M) * R + year) % M;
  

Java的约定

• 若equals为true,则hashcode相同
• 逆否命题：若hashcode不同，equals为false

自定义hashcode

public class Transaction{
    private final String who;
    private final Date when;
    private final double amount;

    public int hashCode(){
        int hash = 17;
        hash = 31 * hash + who.hashCode();
        hash = 31 * hash + when.hashCode();
        hash = 31 * hash + ((Double)amount).hashCode();
        return hash;
    }
}

有序性相关的操作

• 散列最主要的目的在于均匀地将键散布开来，因此在计算散列后键的顺序信息就丢失了
• 所以散列表不是合适的选择

开放地址散列表 open-addressing hashing method

• 插入：若命中，则修改；若未命中，则移向下一个；若为空，则插入
• 搜索：若命中，则找到；若未命中，则移向下一个；若为空，则返回
• 删除：只是将键的位置置为空是不行的，这会导致此位置之后的元素无法找到
  • 若存在，则置为空，同时对连续的非空后继做如下操作
    • 置为空，重新插入
  • 若不存在，则返回
• 不允许使用率达到1，因为此时未命中的查找会导致无限循环。为了性能，我们会调整大小来保证使用率在1/8和1/2之间，小于1/2时探测次数在1.5到2.5之间
• 调整大小(resize)：建立新开放地址散列表，重新插入

平衡查找树 BALANCED SEARCH TREES

2-3查找树 2-3 SEARCH TREES

任何空链接到根节点的路径长度都是相等的

只有当根节点被分解为3个2-node时，所有空链接到根节点的路径长度才会加1

和标准的二叉查找树由上向下生长不同，2-3树的生长是由下向上的

2-node

• 含有一个键和两个链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点

3-node

• 含有两个键和三个链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都处于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点

查找

• 要判断一个键是否在树中，我们先将它和根节点中的键比较。如果它和其中任意一个相等，查找命中；否则我们就根据比较的结果找到相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中。

插入

• 若止于2-node，则将其变为3-node即可
• 若止于3-node
  1. 若该节点为根节点，则变为4-node，做局部变换（高度+1）
  2. 若该节点的父节点为2-node，先变为4-node，做局部变换，使父节点变为3-node
     • 有左右儿子两种情况
  3. 若该节点的父节点为3-node，先变为4-node，做局部变换，使父节点变为4-node，继续对父节点做局部变换，直至遇到2-node，或者遇到根节点
     • 有左中右儿子三种情况

红黑树 Red-Black BSTs

基本思想：用标准的二叉查找树和一些额外的信息表示2-3树

替换3-node

• 将3-node表示为一条左斜的红色链接

或者说

• 红链接均为左链接
• 没有任何一个节点同时和两条红链接相连
• 该树是完美黑色平衡的，即任意空链接到根节点的路径上的黑链接数量相同
• 满足这样定义的红黑树和相应的2-3树是一一对应的

颜色

• 每个节点都只有一条指向自己的链接，我们将链接的颜色当作自己的颜色；若为空链接，则为黑节点。例如，若指向自己的是红链接，则称该节点为红节点

private static final boolean RED = true;
private static final boolean BLACK = false;

private class Node{
    Key key;
    Value val;
    Node left, right;
    int N;
    boolean color;

    Node(Key key, Value val, int N, boolean color){
        this.key = key;
        this.val = val;
        this.N = N;
        this.color = color;
    }
}

private boolean isRed(Node x){
    if(x == null) return false;
    return x.color == RED;
}

旋转

• 在某些操作的过程中，可能会出现红色右链接和两条连续的红链接
• 左旋转 left rotation
  • 若指向的节点的右链接是红色的，该操作会对树进行必要的调整并返回一个指向包含同一组键的子树且其左链接为红色的根节点的链接
• 右旋转 right rotation
  • 类似于左链接

向2-node中插入新键

• 若新键小于老键，新增红色节点
• 若新键大于老键，左旋转

向一棵双键树（即3-node）中插入新键

• 若新键最大，则最小最大键涂黑，中键涂红
• 若新键最小，则先将右旋转最大键，然后最小最大键涂黑，中键涂红
• 若新键居中，则先左旋转最小键，再右旋转最大键，然后最小最大键涂黑，中键涂红

根节点总是黑色

• 红色的根节点说明根节点是一个3-node的一部分，然而实际情况并不是这样。因此我们每次在插入后都会将根节点设为黑色，每当根节点由红变黑时树的黑链接高度就会加1

删除

自顶向下的2-3-4树

• 将4-node表示为三个2-node组成的一棵平衡的子树，根节点和两个子节点都用红链接
• 在向下的过程中分解所有4-node并进行颜色转换
• 和插入操作一样，在向上的过程中用旋转将4-节点配平

删除最小键

• 如果当前节点的左子节点不是2-节点，完成；
• 如果当前节点的左子节点是2-节点而它的亲兄弟节点不是2-节点，将当前节点的最小键移到左子节点中，将左子节点的兄弟节点的最小键移到当前节点中
• 如果当前节点的左子节点和他的亲兄弟节点都是2-节点，将左子节点、父节点中的最小键和左子节点最近的兄弟节点合并为一个4-节点，使父节点由3-节点变为2-节点或者由4-节点变为3-节点

删除操作

• 如果被查找的键在树的底部，我们可以直接删除它
• 如果不在，我们需要将它和它的后继节点交换，就和二叉查找树一样
• 因为当前节点必然不是2-节点，问题已经转化为在一棵根节点不是2-节点的子树中删除最小的键。和之前一样，删除之后我们需要向上回溯并分解余下的4-节点