# 查找算法 - 二叉查找树 - 《Yao' Blog》

#定义
#基本实现
- #查找
- #插入
- #递归
#有序性相关的方法与删除操作
#复杂度分析

#定义

一颗二叉查找树（BST）是一个二叉树，树中的每一个结点都含有一个Comparable的键和值。二叉树的每个结点至多连接一颗左子树和一颗右子树，左子树中结点的键都小于根结点的键，右子树中结点的键都大于根结点的键。

#基本实现

二叉树通过Node对象实现，每个Node对象包含了一个key、一个value、一条左链接、一条右链接和一个结点计数器。左链接指向结点的左子树，右链接指向结点的右子树。

结点计数器计算了根为该结点的所有子树中含有的结点数量，任意结点x总满足：size(x) = size(x.left) + size(x.right) + 1;

public class BST<Key extends Comparable<Key>, Value> {
    private Node root;             // 二叉查找树的根节点
    private class Node {
        private Key key;           // 键
        private Value val;         // 值
        private Node left, right;  // 指向子树的左链接、右链接
        private int N;             // 以该节点为根的子树中的节点总数
        public Node(Key key, Value val, int size) {
            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;
        else return x.N;
    }
    //实现见下文
    public Value get(Key key)
    //实现见下文
    public void put(Key key, Value val)
    //其它有序性相关的方法及删除操作见下文
}

同一个集合可以使用多棵不同的二叉查找树表示，如果将二叉查找树的所有键映射到一条直线上，可以得到一条有序的键列。

#查找

如果树是空的，则查找为命中；如果被查找的键和根结点的键相等，查找命中；否则就递归在子树中查找，如果被查找的键较小就选择左子树，如果被查找的键较大就选择右子树。

public Value get(Key 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.value;
}

#插入

如果树是空的，就返回一个含有该键值对的新结点；如果被查找的键小于根结点的键，继续在左子树插入该键，否则就在右子树中插入该键。

public void put(Key key, Value value) {
    root = put(root, key, value);
}
private Node put(Node x, Key key, Value value) {
    // 如果key存在于以x为根结点的子节点则更新它的值；
    // 否则将以key和value为键值对的新结点插入到该子树中
    if (x == null) return new Node(key, value, 1);
    int cmp = key.compareTo(x.key);
    if (cmp < 0) x.left = put(x.left, key, value);         // 可以重置链接
    if (cmp > 0) x.right = put(x.right, key, value);     // 可以重置链接
    else x.value = value;
    x.N = size(x.left) + size(x.right) + 1;                // 更新结点计数器的值
    return x;
}

#递归

递归调用前的代码可以当作沿着树向下走：它会将给定的键和每一个结点的键相比较并根据结果向左或者向右移动到下一个结点。
递归调用后的代码可以当作沿着树向上走：对于get()方法，对应这一系列的返回指令（return）；对于put()重置搜索路径上的每个父结点指向子结点的链接，并增加路径上每个结点中的计数器的值。

#有序性相关的方法与删除操作

#最大键和最小键

最小键：如果根结点的左链接为空，那么二叉查找树中的最小键就是根结点；如果左链接非空，那么最小键就是左子树中的最小键。
最大键：类似于最小键，右链接为空，那么二叉查找树中的最大键就是跟结点；如果右链接非空，那么最大键就是右子树中的最大键。

public Key max() {
    return max(root).key;
}
public Key min() {
    return min(root).key;
}
private Node max(Node x) {
    if (x.right == null) return x;
    return max(x.right); // 递归调用，直到右链接为空
}
private Node min(Node x) {
    if (x.left == null) return x;
    return min(x.left); // 递归调用，直到左链接为空
}

#向上取整和向下取整

向下取整：如果给定的键key小于二叉查找树的根结点的键，那么小于等于key的最大键floor(key)一定在根结点的左子树中；如果给定的键key大于二叉查找树的根结点，那么floor(key)要么存在于右子树中否在就是当前的根结点。
向上取整：和向下取整相反；
二叉查找树 - 图3

public Key floor(Key key) {
    Node x = floor(root, key);
    if (x == null) return null;
    return x.key;
}
public Key ceiling(Key key) {
    Node x = ceiling(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;
}
private Node ceiling(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x;
    // 在右子树中寻找
    if (cmp > 0) return ceiling(x.right, key);
    // 在左子树中寻找
    Node t = ceiling(x.left, key);
    if (t != null) return t;
    else return x;
}

#选择操作

假设找到排名为k的键（树中有k个小于它的键）。如果左子树中的结点数量t大于k，在左子树中递归寻找排名为k的键；如果t等于k，返回当前该根结点中的键；如果t小于k，在右子树中递归寻找排名为（k-t-1）的键。
二叉查找树 - 图4

public Key select(int k) {
    return select(root, k).key;
}
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;                                         // 找到直接返回
}

#排名操作

rank()是select()的逆方法；
二叉查找树 - 图5

public int rank(Key key) {
    return rank(key, root);
}
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 rank(key, x.right) + size(x.left) + 1;    // 递归返回右子树中的排名 + t + 1
    else return size(x.left);                            // 返回左子树中的结点总数t
}

#删除最大键和最小键

将指向最小结点的链接指向最小结点的右子树。

public void deleteMin() {
    root = deleteMin(root);
}
private Node deleteMin(Node x) {
    if (x.left == null) return x.right;     // 没有左链接时，返回最小结点的右子树
    x.left = deleteMin(x.left);                // 指向最小结点的链接指向最小结点的右子树
    x.N = size(x.left) + size(x.right) + 1;    // 更新每个结点的size
    return x;
}
public void deleteMax() {
    root = deleteMax(root);
}
private Node deleteMax(Node x) {
    if (x.right == null) return x.left;        // 没有右链接时，说明此结点为最大值，返回此结点的左子结点
    x.right = deleteMax(x.right);            // 指向最大结点的链接指向最大结点的左子树
    x.N = size(x.left) + size(x.right) + 1; // 更新每个结点的size
    return x;
}

#删除操作

如果待删除的结点只有一个子树，那么直接将指向该待删除结点的链接指向唯一子树；否则，可以使用前趋结点或者后继结点替换待删除结点。
前趋结点：左子树中的最大结点；
后继结点：右子树中的最小结点。

public void delete(Key key) {
    root = delete(root, key);
}
private Node delete(Node x, Key key) {
    if (x == null) return null;
    // 先找到key所在的结点在哪里
    int cmp = key.compareTo(x.key);
    if (cmp < 0) x.left = delete(x.left, key); // key < x.key时，到左子树中去寻找
    else if (cmp > 0) x.right = delete(x.right, key); // key > x.key时，到右子树中去寻找
    else { // key == x.key时，删除key结点
        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.right) + size(x.left) + 1;
    return x;
}

#范围查找

利用二叉查找树中key遍历结果为递增的特点对其进行指定范围的查找

public Iterable<Key> keys(Key start, Key end) {
    Queue<Key> queue = new Queue<Key>();
    keys(root, queue, start, end);
    return queue;
}
private void keys(Node x, Queue<Key> queue, Key start, Key end) {
    if (x == null) return;
    int cmp_start = start.compareTo(x.key);
    int cmp_end = end.compareTo(x.key);
    /*
        在左子树中查找，直到找到最小的（最左的结点）；
        将最小的结点放入queue中；
        从最小的结点的右子树中继续开始，不断重复；
    */
    if (cmp_start < 0) keys(x.left, queue, start, end);
    if (cmp_start <= 0 && cmp_end >= 0) queue.enqueue(x.key);
    if (cmp_end > 0) keys(x.right, queue, start, end);
}

为了确保在给定结点为根的子树中的所有在指定范围之内的键加入队列，keys()会不断递归查找根结点的左子树，直到左子树为空，然后查找此时的根结点，然后递归查找该根结点的右子树。

#复杂度分析

命题E 在一个二叉查找树中，所有操作在最坏的情况下所需要的时间都和树的高度成正比。

在最好的情况下，一颗含有N个结点的树是完全平衡的，每条空链接和根结点的距离都为lgN，插入和查找的时间复杂度均为O(1.39lgN)；在最坏的情况下，路径上可能会有N个结点，此时插入和查找的时间复杂度为O(N)。