查找算法——二叉查找树
darlingtangli 2019-06-28
一、二叉查找树的定义与特性
二叉查找树（Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,为O(log n)。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即将无序序列中元素逐个插入到二叉查找树的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望 O(log n)，最坏O(n)（数列有序，树退化成线性表）。
下面构造的二叉查找树因为要实现选择(select)和排名(rank)两个操作，所以在Node中新增加了一个int类型字段size，表示该结点所作为根节点所代表的树当中所有结点的个数(包括其本身)，则对任意结点总有size(x)=size(x.left)+size(x.right)+1(1代表的是x结点本身)，当我们后面在进行插入、删除相关操作的都要考虑到了对N的进行更新。还设置了size函数来返回size，如下所示
public int size() {
return size(root);
}
// return number of key-value pairs in BST rooted at x
private int size(Node x) {
if (x == null) return 0;
else return x.size;
}二、 二叉查找树的查找与插入
1.查找操作
//Returns the value associated with the given key.
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("calls get() with a null key");
return get(root, key);
}
private Value get(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key);
else if (cmp > 0) return get(x.right, key);
else return x.val;
}查找操作的递归实现：如果树是空的，则查找未命中；如果被查找的键与根节点的键相等，查找命中。如果被查找的键较小就选择在左子树中(递归地)继续查找，较大则选择右子树。
2.插入操作
public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException("calls put() with a null key");
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, val);
else if (cmp > 0) x.right = put(x.right, key, val);
else x.val = val;
//下面两行时总会执行的
x.size = 1 + size(x.left) + size(x.right);
return x;
}函数功能：在node作为根节点所表示的二叉查找树当中，将key和val生成新结点插入进去，已有相同key时则是更新对应的值为val，然后将根节点返回。其实这个函数当中并不会有下面在删除操作中存在的根节点被更换的问题，而插入操作本身也不需要像查找(要返回查找到的结点)或者选择(返回排名为k的结点)、排名(返回key对应结点在树中的排名)、取整(要返回一个key取整在树中能够找到的结点)的要有一个返回值，之所以返回根节点只是为了更新结点当中的size,在Node不需要size属性时，完全可以将返回值设置成为void即可代码留待后面写下
传入参数：node、key和val。
返回值：返回一个根节点，该根节点可能是只是根据参数key找到了子树上某个结点更新了值或者根据key在该根节点子树上的相应位置插入了一个新结点。
其中1234主要是逻辑实现，0是主要为了逻辑实现与完善递归。
- 如果当前树为null则返回以key和val为键值对的新节点
- 如果key小于当前节点的键，则将键值对放到当前节点的左子树当中去，因为左子树可能是null,到达会被插入新结点，所以还要接收一下
- 如果key大于当前节点的键，则将键值对放到当前节点的右子树当中去，因为右子树可能是null,到达会被插入新结点，所以还要接收一下
- 如果key等于当前节点的键，则将当前节点的值更新为要插入的键值对中的值
- 不管key是大于小于等于，都要讲当前节点的结点数目进行更新一下，以防进行了插入后，左或者右子树的结点数目发生了变化。然后将当前结点返回。
三、 二叉查找树的向上取整和向下取整
1.向下取整
public Key floor(Key key) {
Node x = floor(root, key);
if (x == null) return null;
return x.key;
}
private Node floor(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp == 0) return x;
if (cmp < 0) return floor(x.left, key);
Node t = floor(x.right, key);
if (t != null) return t;
else return x;
}向下取整是得到键相比给定的key变小了一点的结点，向上取整是得到键相比给定的key变大了一点的结点
向下取整：如果给定键的key小于二叉树的根节点的键，那么小于等于key的最大键floor(key)一定在根节点的左子树当中，这是因为本来就小于了你再变小一点那就只能是根节点左子树当中的结点了，所以在左子树当中；如果给定键的key大于二叉树的根节点的键，那么只有当根节点右子树当中存在小于等于key的结点时，小于等于key的最大键才会出现在右子树当中，这是因为本来是大于的，如果变小了一点，那么可能会变成根节点或者根节点左子树中的结点。并且当小于的时候向下取整可能不存在，而当大于的时候向下取整一定存在。
函数功能：在根节点x所代表的二叉查找树当中找到 键值等于向下取整后的key 的结点，找不到则返回null
传入参数：二叉查找树根节点x和要进行向下取整的键key
返回值：在根节点x代表的树中找到的key向下取整的结点或者null(未找到)
向下取整函数的递归逻辑(向上取整类似就不在重复，上下互换、左右互换、大小互换即可):
- 根节点为null则返回null
- 如果key小于x.key，因为向下取整一定存在左子树的结点当中或者在左子树中不存在也是整颗子树中不存在，所以那么就返回在左子树中找到的key的向下取整。
- 如果key大于x.key，这个时候向下取整一定存在了，在右子树中找不到的话那就是x本身了，所以先接收在右子树当中找到的key的向下取整，接受完判断是否为null，如不是则返回，如是则将x返回。
四、 二叉查找树的选择与排名
public Key select(int k) {
if (k < 0 || k >= size()) {
throw new IllegalArgumentException("argument to select() is invalid: " + k);
}
Node x = select(root, k);
return x.key;
}
// Return key of rank k.
private Node select(Node x, int 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, k-t-1);
else return x;
}
public int rank(Key key) {
if (key == null) throw new IllegalArgumentException("argument to rank() is null");
return rank(key, root);
}
// Number of keys in the subtree less than key.
private int rank(Key key, Node x) {
if (x == null) return 0;
int cmp = key.compareTo(x.key);
if (cmp < 0) return rank(key, x.left);
else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
else return size(x.left);
}1.选择操作
函数功能：在根节点所代表的二叉查找树当中找到名次为k的结点，然后将其返回，如找不到则返回的是null
传入参数：排名名次k，二叉查找树根节点x
返回值：找到的排名为k的键，找不到则返回null
方法思路：假设我们想找到排名为k的键(即对于该键而言在树中正好有k个小于它的键)。如果左子树中的结点数t大于k，那么我们就继续(递归地)在左子树中查找排名为k的键；如果t等于k，我们就返回根节中的键；如果t小于k，我们就(递归地)在右子树中查找排名为(k-t-1，因为要除去原本的根节点及其左子树上的结点个数之和)的键。
2.排名操作
传入参数：要进行排名的键值Key(如果输入的不是二叉树中存在的结点的键那么就会返回0，其实改成-1应该更好些)
返回值：给定键的排名
方法思路：实现与select()类似：如果给定键和根节点的键相等，我们返回左子树的结点总数t；如果给定的键小于根节点，我们会返回该键在左子树中的排名(递归计算)；如果给定的键大于根节点，我们会返回t+1(根节点)加上它在右子树当中的排名(递归计算)。
五、 二叉查找树的删除操作
1.删除最大键和最小键
对于delMin()方法(删除最小键所对应的键值对)，递归方法接收一个指向结点的引用，并返回指向一个结点的引用，这样的话我们就能将这个返回值赋给被作为参数传进来的那个引用变量，就能将对树结构进行的删除正确地反映。
什么意思呢，我们在删除的过程中可能会删除掉根节点，也就是说根节点换了，但函数外部那个原本的根节点的引用变量还是指向被删除的那个根节点，怎么办？就是只能将新的根节点(当然根节点也可能没被删掉，还是旧的，被删掉的情况是更少的但是是必须考虑的)返回赋值给那个根节点引用变量，如下面的root = deleteMin(root)，这样就能正确地将删除操作反映出来了。
//Removes the smallest key and associated value from the symbol table.
public void deleteMin() {
if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
root = deleteMin(root);
assert check();
}
private Node deleteMin(Node x) {
if (x.left == null) return x.right;
x.left = deleteMin(x.left);
x.size = size(x.left) + size(x.right) + 1;
return x;
}函数功能：删除根节点x代表的二叉查找树中键值最小的结点，然后将“新”的根节点x返回
传入参数：根节点x
返回值：进行删除键值最小的结点之后的"新"的根节点
- 判断当前结点有没有左子树，没有的话，那么当前结点就是最小结点，那么删去之后的新的根节点就是当前结点的右子树所以直接返回该结点的右子树即可。有的话继续下面的步骤。
- 左子树存在，则要删除的结点就在左子树上，所以直接删除左子树的最小结点然后将左子树的"新"的根节点返回并重新给当前结点的左子树进行赋值。
- 左子树既然删除了一个结点，那么结点数目肯定发生了变化，所以要更新一下结点个数。
- 删除并且更新结点数目完毕，可以返回“新结点”了。
删除最大键与删除最小键的原理和实现均相似，在此不再赘述。
2.删除指定键
对于删除指定键而言，如果指定键对应的结点x只有一个子结点或者没有子结点，我们就可以采用和上面删除最大键最小键的方式一样来删除。但对于有两个子结点的结点x，要采用在删除结点x后用它的后继结点填补它的位置。因为x有一个右子结点，因此它的后继结点就是其右子树中的最小结点，这样的替换仍能保证树的有序性，因为x.key和它的后继结点之间不存在其他的键。我们能用四个简单的步骤完成将x替换为它的后继结点的任务
ps:对于左右子树任一或者同时不存在的情况已经用删除最大最小键的方法解决，在这里不用再考虑了，一定是有右子树的。
//Removes the specified key and its associated value from this symbol table
public void delete(Key key) {
if (key == null) throw new IllegalArgumentException("calls delete() with a null key");
root = delete(root, key);
assert check();
}
private Node delete(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = delete(x.left, key);
else if (cmp > 0) x.right = delete(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.size = size(x.left) + size(x.right) + 1;
return x;
}找到要删除的结点后的操作：
- 如果结点左子树为空，则直接将右子树作为新的根节点返回即可。如结点右子树为空，则直接将左子树作为新的根节点返回即可。以下流程都是在左右子树都存在的情况下进行的了。
- 将指向x即将被删除的结点的链接保存为t;
- 将x指向他的后继结点min(t.right);
- 将x的右链接(原本指向一颗所有结点都大于x.key的二叉查找树)指向deleteMin(t.right)，也就是在删除后的所有结点都仍然大于x.key的子二叉查找树。其实这个时候ｘ已经是min(t.right)了，但还未从t.right这棵树中删去并指向删除后的t.right。
- 将x的左连接(本为空，因为它原本是min(t.right))设为t.left(其下所有键都小于被删除的结点和它的后继结点)。
以上就是在找到指定键值相应节点后的操作，可以看出是一个顺序化流程，并不涉及递归，但在找到这个相应结点的过程中还是用到了递归，并在找到后对结点的N进行了更新,删除操作总体流程如下：
函数功能：对指定根结点x所表示的树，删除指定key在树中对应的结点，然后将该树“新”的根节点返回
传入参数：根节点x，要删除的结点的指定键key
返回值：进行删除之后的"新"的根节点(也可能并没有进行任何删除操作，在没找到指定键的情况下)
- 如果根结点为空则返回null，否则继续。
- 判断指定键与根结点的键的大小，指定键更大，则将右子树在删除key对应结点后的新的根结点赋值给x.right(因为有可能删除的就是x.right本身)。
- 指定键更小，则将左子树在删除key对应结点后的新的根节点赋值给x.left(因为有可能删除的就是x.left本身)。
- 指定键与根结点的键值相等，则说明当前结点就是要删除的结点，去执行找到要删除的结点后的操作。
- 对根节点的N进行更新，然后返回根节点x。
