查找
此文为《算法4》的学习笔记，内容基本摘自《算法4》
本部分将会学习三种经典的数据类型来实现高效的符号表：二叉查找树、红黑树、散列表
1.符号表
符号表最主要的目的就是将一个键和一个值联系起来。
1.1 API
此处罗列下后面讲述的可能使用到的API
| 函数 | 作用 |
|---|---|
ST() |
创建一张有序符号表 |
Key floor(Key key) |
小于等于key的最大键 |
Key ceiling(Key key) |
大于等于key的最小键 |
int rank(Key key) |
小于key的键的数量 |
Key select(int k) |
排名为k的键 |
1.2 无序链表中的顺序查找
对于链表，查找操作困难，插入操作简单
对put()操作，如果链表中已经存在这样的值，则更改value值；如果不存在，则新创建一个节点。对于链表。
1.3 有序数组中的二分查找(待补充)
在有序数组中完成查找很简单，但是完成插入困难（按序插入）
递归的二分查找
public int rank(Key key , int lo , int hi){int mid = lo + (hi-lo)/2;int cmp = key.comparaTo(keys[mid]);if(cmp > 0) return rank(key,lo,mid-1);else if(cmp < 0) return rank(key, mid+1,hi);else return mid;}
递归的rank()保留了以下性质：
- 如果该表中存在该键，
rank()应该返回该键的位置，即表中小于它的键的数量； - 如果表中不存在该键，
rank()还是返回表中小于它的键的数量（好好理解）。
迭代的二分查找
public int rank(Key key){int lo = 0 , hi = n - 1; //n为数组的长度while(lo <= hi){mid = lo + (hi-lo)/2;int cmp = key.comparaTo(keys[mid]);if(cmp > 0) hi = mid-1;else if(cmp < 0) lo = mid+1;else return mid;}}
2. 二叉查找树
在本节中我们将学习一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。
二叉树（BST）
一棵二叉查找树（BST）是一棵二叉树，其中每个结点都含有一个 Comparable 的键（以 及相关联的值）且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点 的键。
二叉树的节点个数
size(x) = size(x.left) + size(x.right) + 1
二叉树的查找操作其实就是二分查找的另一个版本。
一次查找也就定义了树的一条路径，对于命中的查找，路径在含有被查找的键的节点处结束；对于未命中的查找，路径的终点是一个空链接。
2.1 基本实现
基于二叉查找树的符号表
以下代码实现BST的初始化，以及get()和put()操作
public class BST<Key extends Comparable<Key>,value>{private Node root;private class Node{private Key key;private Value value;private Node left,right;private int N;}public Node(Key key,Value val, int N){this.key = key;this.val = val;this.N = N;}public int size(){return size(root);}private int size(Node x){if(x==null) return 0 ;return x.N;}public Value get(Key key){return get(root,key);}private Value get(Node root,Key key){ //get获取值if(root == null) return null;int cmp = key.comparaTo(root.key);if(cmp>0) {return get(root.right,key);}else if(cmp < 0 ){return get(root.left,key);}else{return root.value;}}public void put(Key key, Value val){root = put(root,key,val);}private Node put(Node x , Key key , Value value){ //插入if(x==null) return new Node(key,value,1);int cmp = key.comparaTo(x.key);if(cmp < 0 ){x.right = put(x.right,key,value);}else if(cmp > 0 ){x.left = put(x.left,key,value);}else{x.val = value;}x.N = size(x.left)+size(x.right)+1;//存在值替换的可能性return x;}}
2.2 有序性相关的方法与删除操作
最小键和最大键
最小键——左子树的左子树；最大键——右子树的右子树
pulic Key min(){return min(root).key;}private Node min(Node x ){if(x.left == null) return x;return min(x.left);}
向上取整和向下取整
如果给定的键 key 小于二叉查找树的根结点的 键，那么小于等于 key 的最大键 floor(key) 一定在根结点的左子树中；如果给定的键 key 大于二叉查找树的根结点，那么只有当根结点右子树中存在小于等于 key 的结点时，小于等于 key 的最大键才会出现在右子树中，否则根结点就是小于等于 key 的最大键。这段描述说明了 floor() 方法的递归实现，同时也递推地证明了它能够计算出预期的结果。 将“左”变为“右”（同时将小于变为大于）就能 够得到 ceiling() 的算法。向下取整函数的计算如图所示。
pulic Key floor(Key key){Node x = floor(root , key);if(x == null) return null;return x;}private Node floor(Node x , Key key){if(x == null ) return null;int cmp = key.comparaTo(x.key);if(cmp < 0){ //当key的值小于x，则目标在x的左子树return floor(x.left,key);//如果左子树中没有符合条件的，则返回null，不必像对右子树一样}if(cmp == 0 ) return x;Node t = floor(x.right,key); //当key的值大于x，目标在x的右子树或者xif(t!=null) return t; //右子树中t符合条件else return x; //右子树中没有符合条件的，返回根节点x}
选择操作
假设我们想找到排名为k的键（即树中正好有k个小于它的键）。如果左子树中的结点数t大于k， 那么我们就继续（递归地）在左子树中查找排名为 k 的键；如果 t 等于 k，我们就返回根结点中的键； 如果 t 小于 k，我们就（递归地）在右子树中查找排名为（k-t-1）的键。和刚才一样，这段描述既说明了 select() 方法的递归实现同时也证明了它的正确性。
public Key select(int k ){return select(root,k).key;}private Node select(Node x , int k){//返回排名为k的节点if(x==null) return null;int t = size(x.left);if(t > k) return select(x.left,k);else if(t < k) return select(x.right,t-k-1);else return x;}
排名
rank() 是 select() 的逆方法，它会返回给定键的排名。它的实现和 select() 类似：如果给定的键和根结点的键相等，我们返回左子树中的结点总数 t；如果给定的键小于根结点，我们会返 回该键在左子树中的排名（递归计算）；如果给定的键大于根结点，我们会返回 t+1（根结点）加上它在右子树中的排名（递归计算）。
public int rank(Key key){return rank(root,key);}private int rank(Node x ,Key key){//返回以x为节点的子树中小于x.key的键的数量if(x == null) return 0 ;int cmp = key.comparaTo(x.key);if(cmp<0){return rank(x.left,key);}else if(cmp > 0 ){ //左子树中的高度+右子树中可能的高度return size(x.left)+1+rank(x.right,key);}else{return size(s.left);}}
删除最大键和删除最小键
二叉查找树中最难实现的方法就是delete() 方法，即从符号表中删除一个键值对。作为热身运动，我们先考虑 deleteMin() 方法（删除最小键所对应的键值对）。和 put() 一 样，我们的递归方法接受一个指向结点的链接，并返回一个指向节点的链接。这样我们就能够方便地改变树的结构，将返回的链接赋给作为参数的链接。
对于 deleteMin()，我们要不断深入根结点的左子树中直至遇见一个空链接，然后将指向该结点的链接指向该结点的右子树（只需要在递归调用中返回它的右链接即可）。此时已经没有任何链接指向要被删除的结点，因此它会被垃圾收集器清理掉。我们给出的标准递归代码在删除结点后会正确地设置 它的父结点的链接并更新它到根结点的路径上的所有结点的计数器的值。deleteMax() 方法的实现和 deleteMin() 完全类似。
//该函数返回删除最大键或最小键之后的整个树public void deletMin(){root = deletMin(root);}private Node deletMin(Node x){if(x.left == null ) return x.right;//当找到目标时，结合下一语句，直接将其右孩子接到父节点的左孩子处（其父节点的值大于这个右孩子节点）x.left = deletMin(x.left);x.N = size(x.left)+size(x.right)+1;return x;}
删除操作
在删除结点x后用它的后继节点填补它的位置。因为x有一个右子节点，因此它的后继节点就是其右子树中的最小节点。这样的替换仍然能够保证树的有序性，因为x.key和它的后继结点的键之间不存在其他的键。我们能够用 4 个 简单的步骤完成将 x 替换为它的后继结点的任务（具体过程如图所示）：
- 将指向即将被删除的结点的链接保存为
t； - 将 x 指向它的后继结点
min(t.right)； - 将 x 的右链接（原本指向一棵所有结点都大于
x.key的二叉查找树）指向deleteMin(t. right)，也就是在删除后所有结点仍然都大于x.key的子二叉查找树； - 将 x 的左链接（本为空）设为
t.left（其下所有的键都小于被删除的结点和它的后继节点）。
在递归调用后我们会修正被删除的结点的父结点的链接，并将由此结点到根结点的路径上的所 有结点的计数器减 1（这里计数器的值仍然会被设为其所有子树中的结点总数加一）。
public void delete(Key key){root = delete(root , key);}private Node delete(Node x, Key key){if(x == null){return null;}int cmp = key.comparaTo(x.key);if(cmp < 0){x.left = delete(x.left,key);}else if(cmp > 0){x.right = delte(x.right,key);}else{ //找到需要删除的节点位置//这里就是返回剩余的孩子节点，具体连接到父节点的左孩子还是右孩子是由上层递归调用决定的if(x.right == null) return x.left;if(x.left == null) return x.right;Node t = x;x = min(t.right); //找到右子树中的最小节点x.right = deleteMin(t.right); //移动这样的最小节点效果等同于删除最小节点x.left = t.left; //处于目标节点的左节点}x.N = size(x.left) + size(x.right) + 1;return x; // 将更新后的x连接到上层递归调用的父节点上}
范围查找
public Iterable<Key> keys(){ return keys(min(), max()); }public Iterable<Key> keys(Key lo, Key hi){Queue<Key> queue = new Queue<Key>();keys(root, queue, lo, hi);return queue;}private void keys(Node x, Queue<Key> queue, Key lo, Key hi){if (x == null) return;int cmplo = lo.compareTo(x.key);int cmphi = hi.compareTo(x.key);if (cmplo < 0) keys(x.left, queue, lo, hi); //先在左子树中找到最后一个满足条件的节点if (cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);//寻找满足条件的目标节点if (cmphi > 0) keys(x.right, queue, lo, hi);//同理在右子树中找目标节点}
3. 平衡查找树
3.1 2-3查找树
3.1.1 定义
一棵 2-3 查找树或为一棵空树，或由以下结点组成：
- 2- 结点，含有一个键（及其对应的值）和两条链接，左链接指向的 2-3 树中的键都小于该结点，右链接指向的 2-3 树中的键都大于该结点。
- 3- 结点，含有两个键（及其对应的值）和三条链接，左链接指向的 2-3 树中的键都小于该结点，中链接指向的 2-3 树中的键都位于该结点的两个键之间，右链接指向的 2-3 树中的键都大于该结点。
一棵完美平衡的 2-3 查找树中的所有空链接到根结点的距离都应该是相同的。
3.1.2 查找
将二叉查找树的查找算法一般化我们就能够直接得到 2-3 树的查找算法。要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中任意一个相等，查找命中；否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接， 查找未命中。
3.1.3 插入
1、向2-结点中插入新键
要在 2-3 树中插入一个新结点，我们可以和二叉查找树 一样先进行一次未命中的查找，然后把新结点挂在树的底部。但这样的话树无法保持完美平衡性。我们使用2-3 树的主要原因就在于它能够在插入后继续保持平衡。如果未命中的查找结束于一个2- 结点，事情就好办了：我们只要把这个 2- 结点替换为一个 3- 结点，将要插入的键保存在其中即可（如 图 3.3.3 所示）。
2、向一棵只含有一个3-结点的树中插入新键
在考虑一般情况之前，先假设我们需要向一棵只含有一个3- 结点的树中插入一个新键。这棵树中有两个键，所以在它唯一的结点中已经没有可插入新键的空间了。为了将新键插入，我们先临时将新键存入该结点中，使之成为一个 4- 结点。它很自然地扩展了以前的结点并含有3个键和4 条链接。创建一个4- 结点很方便，因为很容易将它转换为一棵由3个2-结点组成的2-3树，其中一个结点（根）含有中键， 一个结点含有 3 个键中的最小者（和根结点的左链接相连），一个结点含有 3 个键中的最大者（和 根结点的右链接相连）。这棵树既是一棵含有 3 个结点的二叉查找树，同时也是一棵完美平衡的 2-3 树，因为其中所有的空链接到根结点的距离都相等。插入前树的高度为 0，插入后树的高度为 1。 这个例子很简单但却值得学习，它说明了 2-3 树是如何生长的，如图 3.3.4 所示。
3、向一个父结点为2-结点的3-结点中插入新键
假设未命中的查找结束于一个 3- 结点，而它的父结点是一个2- 结点。在这 种情况下我们需要在维持树的完美平衡的前提下为新键腾出空间。我们先像刚才一样构造一个临时的 4- 结点并将其分解，但此时我们不会为中键创建一个新结点，而是将其移动至原来的父结点中。 你可以将这次转换看成将指向原 3- 结点的一条链接替换为新父结点中的原中键左右两边的两条链接，并分别指向两个新的2- 结点。根据我们的假设，父结点中是有空间的：父结点是一个2- 结点（一 个键两条链接），插入之后变为了一个3- 结点（两个键 3 条链接）。另外，这次转换也并不影响（完美平衡的）2-3 树的主要性质。树仍然是有序的，因为中键被移动到父结点中去了；树仍然是完美平衡的，插入后所有的空链接到根结点的距离仍然相同。
4、向一个父结点为3-结点的3-结点中插入新键
现在假设未命中的查找结束于一个父结点为3- 结点的结点。我们再次和刚才一样构造一个临时的 4- 结点并分解它，然后将它的中键插入它的父结点中。但父结点也是一个3- 结点，因此我们再用这个中键构造一个新的临时 4- 结点，然后在这个结点上进行相同的变换，即分解这个父结点并将它的中键插入到它的父结点中去。推广到一般情况，我们就这样一直向上不断分解临时的 4- 结点并将中键插入更高层的父结点，直至遇到一个 2- 结点并将它替换为一个不需要继续 分解的 3- 结点，或者是到达 3- 结点的根。该过程如图 3.3.6 所示。
5、分解根结点
如果从插入结点到根结点的路径上全都是3- 结点，我们的根结点最终变成一个临时的4- 结点。 此时我们可以按照向一棵只有一个3- 结点的树中插入新键的方法处理这个问题。我们将临时的 4- 结点分解为3 个 2- 结点，使得树高加 1，如图 3.3.7 所示。请注意，这次最后的变换仍然保持了树的完美平衡性，因为它变换的是根结点。
3.1.4 局部变换
将一个4- 结点分解为一棵2-3 树可能有 6 种情况，都总结在了图 3.3.8 中。这个4- 结点可能是根结点，可能是一个2- 结点的左子结点或者右子结点，也可能是一个3- 结点的左子结点、中子结点或者右子结点。2-3 树插入算法的根本在于这些变换都是局部的：除了相关的结点和链接之外不 必修改或者检查树的其他部分。每次变换中，变更的链接数量不会超过一个很小的常数。需要特别指出的是，不光是在树的底部，树中的任何地方只要符合相应的模式，变换都可以进行。每个变换都会将 4- 结点中的一个键送入它的父结点中，并重构相应的链接而不必涉及树的其他部分。
3.1.5 全局性质
这些局部变换不会影响树的全局有序性和平衡性：任意空链接到根结点的路径长度都是相等的。
所以局部变换都不会影响整棵树的有序性和平衡性。
标准的二叉查找树由上向下生长，2-3树的生长是由下向上的。
3.2 红黑二叉查找树
2-3查找树的实现形式
3.2.1 定义
1、替换3-结点
红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全由2-结点构成）和一些额外信息（替换3-结点）来表示2-3树。我们将树中的链接分为两种类型：
- 红链接：将两个2-结点连接起来构成一个3-结点
- 黑链接：2-3树种的普通链接
确切的说，我们将3-结点表示为一条左斜的红色链接（两个2-结点其中之一是另一个的左子结点）相连的两个2-结点。
这样的表示方法的有点是：我们无需修改就可以直接使用标准二叉查找树的get()方法。对于任意2-3树，只要对结点进行转换，即可派生出一颗对应的二叉查找树。
2、另一种定义
红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树：
- 红色链接均为左链接；
- 没有任何一个结点同时与两条红链接相连；
- 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链数量相同。
3、颜色表示
每个结点都只会有一条指向自己的链接（从它的父结点指向它），将链接的颜色保存在表示结点的Node数据类型的color中，如果指向它的链接是红色的，则设为true，否则为false。约定空链接为黑色，当我们提到一个结点的颜色时，我们指的是指向该结点的链接的颜色。
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;}}
3.2.2 旋转
在我们实现的某些操作中可能会出现红色右链接或者两条连续的红链接，但在操作完成前都会被旋转修复。旋转操作会改变红链接的指向。
当有一条红色的链接需要被转化为左链接，这个操作叫左旋转，同理，可以得到右旋转的定义。
在旋转的操作中，我们只是将用两个键中的较小者作为根结点变为较大者作为根节点。
无论是左旋转还是右旋转，旋转操作都会返回一条链接。我们使用rotateRight()和rotateLeft()的返回值重置父结点（或者是根节点）中相应的链接。返回的链接可能是左链接也可能是右链接，但是总会将它赋予父结点中的链接。这个链接可能是红色或黑色——rotateRight()和rotateLeft()都通过将x.color设为h.color保留它原来的颜色。
Node rotateRight(Node h){Node x = h.right;h.right = x.left;x.left = h;x.color = h.color;h.color = RED;x.N = h.N;h.N = 1+size(h.left)+size(h.right);return x;}Node rotateLeft(Node h){Node x = h.left;h.left = x.right;x.right = h;x.color = h.color;h.color = RED;x.N = h.N;h.N = 1+size(h.left)+size(h.right);return x;}
3.2.3 插入
1、向单个2-结点中插入新键
一棵只含有一个键的的红黑树只含有一个2-结点。插入另一个键之后，我们马上就需要将它们旋转。如果新键小于老键，新增一条红色的结点即可。如果新键大于老键，则会新增的红色结点会产生一条红色的右链接，需要使用root=rotateLeft(root);来旋转为红色左链接并修正根结点的链接。如图3.3.18所示。
2、向树底部的2-结点插入新键
在底部插入新键，使用红链接将新结点和它的父节点相连。新键插入之后的处理方法同1。
3、向一颗双键树（即一个3-结点）中插入新键
这种情况可以分为3种子情况：（1）新键小于树中的两个键；（2）在两者之间；（3）大于树中的两个键。每种情况都会产生一个同时连接到两条红链接的结点。
- 新键大于原树中的两个键
新键被连接到3-结点的右连接。此时树是平衡的，根结点为中间大小的键，其有两条红链接分别和较大较小的结点相连。如果将两条链接的颜色都由红变黑，即可得到一棵由三个结点组成，高为2的平衡树，它正好对应一棵2-3树，其他两种情况最终也会转化为这种情况。——【颜色转换】 - 新键小于原树种的两个键
新键被连接到最左边的空链接，这样就产生了两条连续的红链接。此时只需要将上层的红链接右旋转即可得到第一种情况。——【上层红链接右旋转】 - 新键介于原树种的两个键之间
这种情况会产生两条红色链接，一条红色左链接一条红色右链接，此时我们需要将下层的红链接左旋转即可得到第二种情况。——【下层红链接左旋转】
4、颜色转换
使用方法filpColors()来转换一个结点的两个红色子结点的颜色。将子结点的颜色由红变黑之外，将父结点的颜色由黑变红。——【局部变换】
void filpColor(Node h){h.color = RED;h.left.color = BLACK;h.right.color = BLACK、;}
5、根结点总是黑色
在3的描述的情况中，颜色转换会使根结点变为红色。红色的根结点说明根结点是一个3-结点的一部分，但在实际中，我们在每次插入后，都将根结点设为黑色。每次根节点由红变黑时树的黑链接高度就会+1。
6、向树底部的3-结点插入新键
其情况同【3】中讨论的那样。
指向新结点的链接可能是3-结点的右链接（此时我们只需要转换颜色即可），或是左链接（此时需要进行右旋转之后再转换颜色），或是中链接（需要先左旋转下层链接然后右旋转上层链接，最后再转换颜色）。颜色转换会使到中结点的链接变红，相当于将其送入了父结点。这意味着在父结点中继续插入一个新键。
7、将红链接在树中向上传递
2-3树种的插入算法需要我们分解3-结点，将中间键插入父结点，直到碰到一个2-结点或者根结点。
在各种情况中：每次必要的旋转之后都会进行颜色转换，使得中结点变红。对于父结点，处理这样一个红色结点的方式与处理一个新插入的红色结点完全相同，即继续把红链接转移到中结点上。
插入过程中的旋转操作与颜色转换的选择：
- 如果右子结点是红色的而左子结点是黑色的，进行左旋转；
- 如果左子结点是红色的且其左子结点也是红色的，进行右旋转；
- 如果左右子结点均为红色，进行颜色转换。
3.2.4 插入操作实现
红黑树的插入操作
public class RedBlackBST<Key extends Comparable<Key>, Value> {private Node root;private class Node;private boolean isRed();private Node rotateLeft(Node h);private Node rotateRight(Node h);private void flipColors(Node h);private int size();public void put(Key key, Value val){root = put(root,key,val);root.color = BLACK;}private Node put(Node h, Key key , Value val){if(h==null){return new Node(key,val,1,RED);//先把2-结点填充为3-结点或将3-结点填充为4-结点}int cmp = key.comparaTo(h.key);if(cmp < 0 ) h.left = put(h.left,key,val);else if(cmp >0) h.right = put(h.right,key,val);else h.val = val;if(isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);if(isRed(h.left) && isRed(h.left.left)) h = rotateRight(h.left); //两左红if(isRed(h.left) && isRed(h.right)) h = filpColors(h);h.N = 1 + size(h.left) + size(h.right);return h;}}
3.2.5 删除操作实现（不懂）
我们可以定义一系列局部变换来在删除一个结点的同时保持树的完美平衡性。这个过程比插入一个结点更加复杂，因为不仅要在（为了删除一个结点面）构造临时4-结点时沿着查找路径向下进行变换，还要在分解遗留的4-结点时沿着路径向上进行变换（同插入操作）。
1、自顶向下的2-3-4树
该设定下允许3-节点的存在，同时由于4-结点可以存在，所以可以允许一个结点同时连接到两条连接。
先学习一个沿查找路径既能向上也能 向下进行变换的稍简单的算法：2-3-4 树的插入算法，2-3-4 树中允许存在我们以前见过的4- 结点。它的插入算法沿查找路径向下进行变换是为了保证当前结点不是 4- 结点（这样树底才有空间来插入新的键），沿查找路径向上进行变换是为了将之前创建的 4- 结点配平，如图 3.3.25 所示。向下的变换和我们在 2-3 树中分解4- 结点所进行的变换完全相同。如果根结点是4- 结点，我们就将它分解成三个2- 结点，使得树高加 1。在向下查找的过程中，如果遇到一个父结点为2-结点的4-结点，我们将4-结点分解为两个2-结点并将中间键传递给它的父结点，使得父结点变为一个3-结点； 如果遇到一个父结点为3- 结点的 4- 结点，我们将 4- 结点分解为两个 2- 结点并将中间键传递给它的父结点，使得父结点变为一个4-结点；我们不必担心会遇到父结点为4- 结点的4- 结点，因为插入算法本身就保证了这种情况不会出现。到达树的底部之后， 我们也只会遇到 2- 结点或者3- 结点，所以我们可以插入新的键。 要用红黑树实现这个算法，我们需要：
- 将 4- 结点表示为由三个 2- 结点组成的一棵平衡的子树， 根结点和两个子结点都用红链接相连；
- 在向下的过程中分解所有 4- 结点并进行颜色转换；
- 和插入操作一样，在向上的过程中用旋转将 4- 结点配平。
令人惊讶的是，只需要移动插入算法的 put() 方法中的一行代码就能实现 2-3-4 树中的插入 操作：将 colorFlip() 语句（及其 if 语句）移动到递归调用之前（null 测试和比较操作之间）。 在多个进程可以同时访问同一棵树的应用中这个算法优于 2-3 树，因为它操作的总是当前结点的一个或两个链接。我们下面要讲的删除算法和它的插入算法类似，而且也适用于 2-3 树。
private Node put(Node h, Key key , Value val){if(h==null){return new Node(key,val,1,RED);//先把2-结点填充为3-结点或将3-结点填充为4-结点}if(isRed(h.left) && isRed(h.right)) h = filpColors(h);int cmp = key.comparaTo(h.key);if(cmp < 0 ) h.left = put(h.left,key,val);else if(cmp >0) h.right = put(h.right,key,val);else h.val = val;if(isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);if(isRed(h.left) && isRed(h.left.left)) h = rotateRight(h.left); //两左红h.N = 1 + size(h.left) + size(h.right);return h;}
2、删除最小键
2-3树中删除最小键的操作。我们注意到从树底部的3- 结点中删除键是很简单的，但2- 结点则不然。从2- 结点中删除一个键会留下一个空结点，一般我们会将它替换为一个空链接，但这样会破坏树的完美平衡性。所以我们需要这样做：为了保证我们不会删除一个 2- 结点，我们沿着左链接向下进行变换，确保当前结点不是 2-结点（可能是 3- 结点，也可能是临时的 4- 结点）。首先，根结点可能有两种情况。如果根是2- 结点且它的两个子结点都是 2- 结点， 我们可以直接将这三个结点变成一个 4- 结点；否则我们需要保证根结点的左子结点不是 2- 结点， 如有必要可以从它右侧的兄弟结点“借”一个键来。以上情况如图 3.3.26 所示。在沿着左链接向下 的过程中，保证以下情况之一成立：
- 如果当前结点的左子结点不是 2- 结点，完成；
- 如果当前结点的左子结点是 2- 结点而它的亲兄弟结点不是 2- 结点，将左子结点的兄弟结点中的一个键移动到左子结点中；
- 如果当前结点的左子结点和它的亲兄弟结点都是 2- 结点，将左子结点、父结点中的最小键和左子结点最近的兄弟结点合并为一个4-结 点，使父结点由3-结点变为2-结点或者由4-结点变为3- 结点。——【递归调用使得父结点必定满足条件】
在遍历的过程中执行这个过程，最后能够得到一个含有最小键的3- 结点或者4- 结点，然后我们就可 以直接从中将其删除，将3- 结点变为2- 结点，或者将4- 结点变为3- 结点。然后我们再回头向上分解所有临时的 4- 结点。
【删除时向下遍历使得当前结点是3-结点或者4-结点，删除完向上分解所有临时的4-结点】
【删除最小键】
实现红黑树的deleteMin()方法，在沿着树的最左路径向下的过程中实现正文所述的变换，保证当前结点不是2-结点。
private Node moveRedLeft(Node h){//假设结点h为红色，h.left和h.left.left都是黑色//将h.left 或者h.left的子节点之一变红——为了将2-结点变为3-结点或者morefilpColors(h);if(isRed(h.right.left)){h.right = rotateRight(h.right);h = rotateLeft(h);}return h;}public void deleteMin(){if(!isRed(root.left) && !isRed(root.right)) root.colcor = RED;root = deleteMin(root);if(!isEmpty()) root.color = BALCK;}private Node deleteMin(Node h){if(h.left == null){return null;}if(!isRed(h.left) && !isRed(h.left.left)){h = moveRedLeft(h);}h.left = deleteMin(h.left);return balance(h);}//这里的 flipColors() 方法将会补全三条链接的颜色;//我们会将父结点设为BLACK（黑）而将两个子结点设为 RED（红）private Node balance(Node h){ //向上分解所有的4-结点if(isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);if(isRed(h.left) && isRed(h.left.left)) h = rotateRight(h.left); //两左红if(isRed(h.left) && isRed(h.right)) h = filpColors(h);h.N = 1 + size(h.left) + size(h.right);return h;}
【删除最大键】
实现红黑树的deleteMax()方法。需要注意的是因为红链接都是左链接，所以这里用到的变换和上面的算法中的稍有不同。
private Node moveRedRight(Node h){//假设结点h为红色，h.right和h.right.left都是黑色//将h.right 或者h.right的子节点之一变红——为了将2-结点变为3-结点或者morefilpColors(h);if(isRed(h.left.left)){h = rotateRight(h);}return h;}public void deleteMax(){if(!isRed(root.left) && !isRed(root.right)) root.colcor = RED;root = deleteMax(root);if(!isEmpty()) root.color = BALCK;}private Node deleteMin(Node h){if(isRed(h.left)) h = rotateRight(h);if(h.left == null){return null;}if(!isRed(h.right) && !isRed(h.right.left)){h = moveRedRight(h);}h.right = deleteMax(h.right);return balance(h);}//这里的 flipColors() 方法将会补全三条链接的颜色;//我们会将父结点设为BLACK（黑）而将两个子结点设为 RED（红）private Node balance(Node h){ //向上分解所有的4-结点if(isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);if(isRed(h.left) && isRed(h.left.left)) h = rotateRight(h.left); //两左红if(isRed(h.left) && isRed(h.right)) h = filpColors(h);h.N = 1 + size(h.left) + size(h.right);return h;}
3、删除操作
在查找路径上进行和删除最小键相同的变换同样可以保证在查找过程中任意当前结点均不是2- 结点。 如果被查找的键在树的底部，我们可以直接删除它。 如果不在，我们需要将它和它的后继结点交换，就和二叉查找树一样。因为当前结点必然不是2- 结点，问题已经转化为在一棵根结点不是 2- 结点的子树中删除最小的键，我们可以在这棵子树中使用前文所述的算法。和以前一样，删除之后我们需要向上回溯并分解余下的 4- 结点。
public void delete(Key key){if(!isRed(root.left) && !isRed(root.right)) root.color = RED;root.color = delete(root,key);if(!isEmpty()) root.color = BLACK;}private Node delete(Node h , Key key){if(key.comparaTo(h,key)<0){if(!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h);h.left = delete(h.left,key);}else{if(isRed(h.left)){h=rotateRight(h);}if(key.comparaTo(h.key)==0 && (h.right == null)) return null;if(!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h);if(key.comparaTo(h.key)==0){h.val = get(h.right,min(h.right).key);h.key = min(h.right).key;h.right = deleteMin(h.right);}else{h.right = delete(h.right,key);}return balance(h);}}
4. 散列表
用算术操作将键转化为数组的索引来访问数组中的键值对。
使用散列的查找算法分为两部：
- 使用散列函数将被查找的键转换为数组的一个索引
在现实情况中，我们需要面对两个或者多个键都会散列到相同的索引值的情况，所以需要下一步操作； - 处理碰撞冲突的过程，两种方法：拉链法和线性探测法
散列表是算法在时间和空间上作出权衡的经典例子。如果没有内存限制，我们可以直接将键作为（可能是一个超大的）数组的 引，那么所有查找操作只需要访问内存一次即可完成。如果没有时间限制，我们可以使用无序数组并进行顺序查找，这样就只需要很少的内存。而散列表则使用了适度的空间和时间并在这两个极端之间找到了一种平衡。
4.1 散列函数
散列函数的计算，这个过程会将键转化为数组的索引。
如果我们有 一个能够保存M个键值对的数组，那么我们就需要一个能够将任意键转化为该数组范围内的索引（[0, M-1] ）范围内的整数的散列函数。我们要找的散列函数应该易于计算并且能够均匀分布所有的键， 即对于任意键，0 到 M-1 之间的每个整数都有相等的可能性与之对应（与键无关）。
散列函数和键的类型有关，严格的说，对于每种类型的键我们都需要一个与之对应的散列函数。
4.1.1 不同数据结构的例子
1、正整数
除留余数法
我们选择大小为素数 M 的数组， 对于任意正整数 k，计算 k 除以 M 的余数。这样可以将键分布在0到M-1的范围内。
2、浮点数
如果键是0到1之间的实数，我们可以将它乘以M并四舍五入得到一个0至 M-1之间的索引值。 尽管这个方法很容易理解，但它是有缺陷的，因为这种情况下键的高位起的作用更大，最低位对散列的结果没有影响。修正这个问题的办法是将键表示为二进制数然后再使用除留余数法（Java 就是 这么做的）。
3、字符串
除留余数法也可以处理较长的键，例如字符串，只需要将其当成大整数即可。例如下列代码就能够用除留余数法计算 String S 的 散列值。
int hash = 0;for(int i = 0 ; i < s.length();i++){hash = (R*hash + s.charAt(i)) % M;}
Java 的charAt() 函数能够返回一个char值，即一个非负16 位整数。如果R比任何字符的值都大，这种计算相当于将字符串当作一个N位的R进制值，将它除以M并取余。一种叫 Horner 方法的经典算法用 N 次乘法、加法和取余来计算一个字符串的散列值。只要 R 足够小，不造成溢出，那么结果就能够如我们所愿，落在 0 至 M-1 之内。使用一个较小的素数，例如31，可以保证字符串中的所有字符都能发挥作用。Java 的 String 的默认实现使用了一个类似的方法。
4、组合键
如果键的类型含有多个整型变量，我们可以和String 类型一样将它们混合起来。例如，假设被查找的键的类型是 Date，其中含有几个整型的域：day（两个数字表示的日），month （两个数字表示的月）和 year（4 个数字表示的年）。我们可以这样计算它的散列值：
int hash = (((day * R + month) % M ) * R + year) % M;
只要 足够小不造成溢出，也可以得到一个0至M-1之间的散列值。在这种情况下我们可以通过选择一个适当的 M，比如 31，来省去括号内的 % M 计 算。和字符串的散列算法一样，这个方法也能处理有任意多整型变量的类型。
5、Java的约定
每种数据类型都需要相应的散列函数，于是 Java 令所有数据类型都继承了一个能够返回一个32比特整数的 hashCode() 方法。每一种数据类型的 hashCode() 方法都必须和 equals() 方法一 致。也就是说，如果 a.equals(b) 返回 true，那么 a.hashCode() 的返回值必然和 b.hashCode() 的返回值相同。相反，如果两个对象的hashCode() 方法的返回值不同，那么我们就知道这两个对象是不同的。但如果两个对象的 hashCode() 方法的返回值相同，这两个对象也有可能不同， 我们还需要用equals() 方法进行判断。请注意，这说明如果你要为自定义的数据类型定义散列函数，你需要同时重写 hashCode() 和 equals() 两个方法。默认散列函数会返回对象的内存地址， 但这只适用于很少的情况。Java 为很多常用的数据类型重写了hashCode()方法（包括 String、 Integer、Double、File 和 URL）。
6、将hashCode()的返回值转化为一个数组索引
因为我们需要的是数组的索引而不是一个 32 位的整数，我们在实现中会将默认的 hashCode()方法和除留余数法结合起来产生一个 0 到 M-1 的整数，方法如下：
private int hash(Key x){return (x.hashCode() & 0x7ffffff) % M;}
这段代码会将符号位屏蔽（将一个 32 位整数变为一个 31 位非负整数），然后用除留余数法计算它除以 M 的余数。在使用这样的代码时我们一般会将数组的大小M取为素数以充分利用原散列值的所有位。
7、软缓存
当散列值的计算很耗时，我们或许可以将每个键的散列值缓存起来，即在每个键中使用一个hash变量来保存它的hashCode()返回值。
4.2 基于拉链法的散列表
一个散列函数能够将键转化为数组索引。散列算法的第二步是碰撞处理，也就是处理两个或多 个键的散列值相同的情况。
一种直接的办法是将大小为M的数组中的每个元素指向一条链表，链表中的每个结点都存储了散列值为该元素的索引的键值对。这种方法被称为拉链法，因为发生冲突的元素都被存储在链表中。这个方法的基本思想就是选择足够大的M，使得所有链表都尽可能短以保证高效的查找。查找分两步：首先根据散列值找到对应的链表，然后沿着链表顺序查找相应的键。
一种简单的方法（但效率稍低）是采用一般性的策略，为M个元素分别构建符号表来保存散列到这里的键，这样也可以重用我们之前的代码。SeparateChainingHashST使用了一个SequentialSearchST对象的数组，在 put() 和get() 的实现中先计算散列函数来选定被查找的 SequantialSearchST 对象，然后使用符号表的 put() 和 get() 方法来完成相应的任务。
因为我们要用 M 条链表保存N个键，无论键在各个链表中的分布如何，链表的平均长度肯定是 N/M。
public class SequentialSearchST<Key,Value>{private Node first; //首结点private class Node{Key key;Value val;Node next;}public Node(Key key , Value val, Node next){this.key = key;this.val = val;this.next = next;}public Value get(Key key){for(Node x = first ; x!=null ; x = x.next){if(key.equals(x.key)) return x.val;return null;}}public void put(Key key, Value val){for(Node x = first; x!=null ; x = x.next){if(key.equals(x.key)){x.val = val ;return ;}}first = new Node(key,val,first);//未命中}}
public class SeparateChainingHashST<Key,Value>{
private int N; //键值对总数
private int M; //散列表大小
private SequentialSearchST<Key,Value>[] st; //存放链表对象的数组
public SeparateChainingHashST(){
this(997);
}
public SperateChainingHashST(int M){
//创建M条链表
this.M = M;
st = (SequentialSearchST<Key,Value>[]) new SequentialSearchST[M];
for(int i = 0 ; i < M ; i++){
st[i] = new SequentialSearchST();
}
}
private int hash(Key key){
return (key.hashCode() & 0x7fffffff) % M;
}
public Value get(Key key){
return (Value) st[hash(key)].get(key);
}
public void put(Key key , Value val){
st[hash(key)].put(key,val);
}
}
这段简单的符号表实现维护着一条链表的数组，用散列函数来为每个键选择一条链表。简单起见， 我们使用了 SequentialSearchST。在创建st[]时需要进行类型转换，因为 Java 不允许泛型的数组。 默认的构造函数会使用 997 条链表，因此对于较大的符号表，这种实现比 SequentialSearchST 大约会快1000倍。当你能够预知所需要的符号表的大小时，这段短小精悍的方案能够得到不错的性能。一种更可靠的方案是动态调整链表数组的大小，这样无论在符号表中有多少键值对都能保证链表较短。
4.3 基于线性探测法的散列表
实现散列表的另一种方式是使用大小为M的数组保存N个键值对，其中。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为开放地址散列表。
开放地址散列表中最简单的方法叫做线性探测法：当碰撞发生时（当一个键的散列值已经被另一个不同的键 占用），我们直接检查散列表中的下一个位置（将索引值+1）。这样的线性探测可能会产生三种结果：
- 命中
- 未命中，键为空
- 继续查找，该位置的键和被查找的键不同
用散列函数找到键在数组中的索引，检查其中的键和被查找的键是否相同。如果不同则继续查找（将索引增大，达到数组结尾时折回数组的开头），直到找到该键或者遇见一个空元素null。将一个数组位置的是否含有被查找的键的操作称作探测。
开放地址类的散列表的核心思想时与其将内存用作链表，不如将它们作为在散列表中的空元素，这些空元素可以作为查找结束的标志。
在实现中使用了并行数组，一条保存键 ，一条保存值。
public class LinearProbingHashST<Key,Value>{
private int N;
private int M = 16;
private Key[] keys;
private Value[] vals;
public LinearProbingHashST(){
keys = (Key[]) new Object[M];
vals = (Value[]) new Object[M];
}
private int hash(Key key){
return (key.hashCode() & 0x7fffffff) % M;
}
private void resize(){
}
public void put(Key key, Value val){
if(N >= M/2) resize(2*M);
for(int i = hash(key); keys[i] != null ; i = (i+1)%M){
if(keys[i].equals(key)){
vals[i] = val;
return ;
}
keys[i] = key;
vals[i] = val;
N++;
}
}
public Value get(Key key){
for(int i = hash(key); keys[i] != null ; i = (i+1)%M){
if(keys[i].equals(key)) return vals[i];
}
return null;
}
}
删除操作
如何从基于线性探测的散列表中删除一个键？仔细想一想，你会发现直接将该键所在的位 置设为 null 是不行的，因为这会使得在此位置之后的元素无法被查找。例如，假设在轨迹图的例子中（图 3.4.6）我们需要用这种方法删除键 C， 然后查找H。H的散列值是4，但它实际存储在这一簇键的结尾，即7号位置。如果我们将5号位置设为null，get()方法将无法找到H。因此，我们需要将簇中被删除键的右侧的所有键**重新插入散列表**。这个过程比想象的要复杂。
public void delete(Key key){
if(!contains(key)) return;
int i = hash(key);
while(!key.equals(keys[i])) i = (i+1)%M;
keys[i] = null;
vals[i] = null;
i = (i+1) % M;
while(keys[i]!=null){
Key keyToRedo = keys[i];
Value valToRedo = vals[i];
keys[i] = null;
vals[i] = null;
N--;
put(keyToRedo,valToRedo);
i = (i+1)%M;
}
N--;
if(N>0 && N==M/8) resize(M/2);
}
键簇
线性探测的平均成本取决于元素在插入数组后聚集成的一组连续的条目，也叫做键簇，如图 3.4.7 所示。例如，在示例中插入键 C 会产生一个长度为 3 的键簇（A C S）。 这意味着插入H需要探测 4 次，因为H的散列值为该键簇的第一个位置。显然，短小的键簇才能保证较高的效率。 随着插入的键越来越多，这个要求很难满足，较长的键簇会越来越多，如图3.4.8所示。另外，因为（基于均匀性假设） 数组的每个位置都有相同的可能性被插入一个新键，长键簇更长的可能性比短键簇更大，因为新键的散列值无论落 在簇中的任何位置都会使簇的长度加 1（甚至更多，如果这个簇和相邻的簇之间只有一个空元素相隔的话）。
调整数组的大小
它会创建一个新的给定大小的LinearProbingHashST，保存原表中的 keys 和 values 变量，然后将原表中所有的键重新散列并插入到新表中。
private void resize(int cap){
LinearProbingHashST<Key, Value> t;
t = new LinearProbingHashST<Key, Value>(cap);
for(int i = 0 ; i < M; i++){
if(keys[i]!=null){
t.put(keys[i],vals[i]);
}
}
keys = t.keys;
vals = t.vals;
M = t.M;
}
5. 应用
若有收获，就点个赞吧
0 人点赞
