查找（二叉查找数）

二叉查找数

定义

一个二叉查找数（BST）是一颗二叉树，其中每个结点都含有一个Comparable的键以及相关联的值，且每个结点的键都大于其左子树的任意结点的键，小于其右子树的任意结点的键

基本实现

1. 数据表示
   键+ 值+ 左链接+右链接+结点计数器
2. 查找
   如果树是空的，则查找未命中；如果查找的键小于当前结点的键，则继续查找其左子树；如果查找的键大于当前结点的键，则继续查找其右子树；如果查找的键等于当前结点的键，则查找命中。
3. 插入
   如果树是空的，则返回一个含有该键值对的新结点。如果被查找的键小于根节点的键，则继续在左子树中插入该键，否则在右子树中插入该键。（记得更新节点计数器）
4. 性能分析
   二叉查找数的算法的运行时间依赖于树的形状，而树的形状则取决于键的插入顺序。如果插入一个有序的键值对，则会出现最坏情况。
   由N个随机键构造的二叉查找数，查找命中和插入命中的平均所需比较次数为~2lnN(1.39lgN)。
   二叉查找和插入的成本都是对数级别的（相比于二分查找的优势）

有序性相关的方法实现

1. 最大键和最小键
   最小键：如果左链接为空，最小键就是根节点；如果左链接非空，最小键就是左子树的最小键
   最大键：如果右链接为空，最大键就是根节点；如果右链接非空，最大键就是右子树的最大键
2. 向上取整和向下取整
   floor(key) : key等于二叉树的根节点，返回根节点的值
   2.1 key小于二叉树的根节点，floor（key）一定在根节点的左子树中
   2.2 key大于二叉树的根节点
   2.2.1 右子树中存在小于等于key的结点时，floor（key）在右子树中
   2.2.2 否则返回根节点
3. 选择操作
   查找排名为k的键（树中有k个小于它的节点），假设左子树的结点数为t
   3.1 如果t > k 在左子树中查找排名为k的键
   3.2 如果t < k 在右子树中查找排名为k-t-1的键
   3.3 如果t=k 返回根节点
4. 排名
   返回给定键在树中的排名
   4.1 如果给定的键小于根节点的键，则返回该键在左子树中的排名
   4.2 如果给定的键大于根节点的键，则返回该键在右子树中的排名+左子树的节点个数+1
   4.3 如果给定的键等于根节点的键，则返回左子树的节点个数
5. 删除最大值和最小值
   deleteMin():如果左子树不为空，则要删除的节点在左子树；如果左子树为空，则返回该节点的右子树
6. 删除操作
   如果某个节点左右子树都不为空，删除节点以后，会产生两个子树而被删除的节点的父节点只空出了一个链接。可以使用被删除节点的后继节点（右子树中的最小节点）补充它的位置。
   6.1 将指向即将被删除的结点的链接保存为t
   6.2 将x指向它的后继结点min（t.right）
   6.3 将x的右链接指向deleteMin（t.right）
   6.4 将x的左链接设为t.left

代码实现

package edu.princeton.cs.algs4.chapter3;

/**
 * 使用二叉查找树实现的符号表
 * Created by tianxianhu on 2017/3/6.
 */
public class BST<Key extends Comparable<Key>, Value> {
    private Node root;
    private class Node{
        private Key key;
        private Value val;
        private Node left;
        private Node 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;
        else return x.N;
    }

    /**
     * 获取指定键的值，从根节点开始，比较键值
     * 小于当前键值则在左子树中继续寻找，大于则在右子树中继续寻找，等于则返回当前节点的值
     * @param key
     * @return
     */
    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.val;
        }
    }

    /**
     * 寻找key，找到则更新它的值，否则为它创建一个新节点，同时更新节点数量
     * @param key
     * @param val
     * @return
     */
    public Node put(Key key, Value val) {
        return 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.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    public Key min() {
        return min(root).key;
    }

    private Node min(Node x) {
        if (x.left == null)
            return x;
        return min(x.left);
    }

    /**
     * 将要查询的键值和根节点的键值进行比较
     * 1. 与根节点键值相等，返回当前节点的键
     * 1. 小于根节点键值，则在左子树中继续寻找
     * 2. 大于根节点键值，则在右子树中寻找（可能在右子树中，也可能是根节点）
     * 2.1 如果右子树中寻找返回null，则返回根节点
     * 2.2 如果在右子树中寻找到，则返回找到的节点
     * @param key
     * @return
     */
    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;
    }

    /**
     * 查询排名为k的键（0-based）
     * 计算做子树的节点数量t，与排名k进行比较
     * 1. 如果t>k, 就继续在左子树中查找排名为k的键
     * 2. 如果k>t, 就在右子树中查找排名为k-t-1的键
     * 3. 如果k=t， 就返回当前节点
     * @param k
     * @return
     */
    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 (k < t) {
            return select(x.left, k);
        } else if (t < k) {
            return select(x.right, k - t - 1);
        } else {
            return x;
        }
    }

    /**
     * 查询键key的排名
     * 将要查询的键与当前的键值进行比较
     * 1.如果相等，则返回根节点左子树的节点数
     * 2.小于根节点，则返回该键在左子树中的排名
     * 3.大于根节点，则返回size(x.left)+1+右子树中的排名
     * @param key
     * @return
     */
    public int rank(Key key) {
        return rank(root, key);
    }

    private int rank(Node x, Key key) {
        if (x == null)
            return 0;

        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            return rank(x.left, key);
        else if (cmp > 0)
            return 1 + size(x.left) + rank(x.right, key);
        else
            return size(x.left);
    }

    /**
     * 1.不断检索左子树，直到遇见空的左子树
     * 2.返回该节点的右链接
     * 3.递归调用结束后更新节点计数器
     */
    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;
        return x;
    }

    public void delete(Key key) {
        root = delete(root, key);
    }

    /**
     * 1.寻找到要删除节点t的后继节点min(t.right)
     * 2.将后继节点x.right指向deleteMin(x.right),即删除后继节点以后的子树，该子树大于后继节点
     * 3.将后继节点x.left指向t.left
     * @param x
     * @param key
     * @return
     */
    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.left == null)
                return x.right;
            if (x.right == null)
                return x.left;
            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;
    }

}