一、二叉查找树

• 每个结点都含有一个Comparable的键（以及相关的值），每个结点的键都大于左子树中的任意结点的键而小于右子树的任意结点的键
• 每个节点都含有一个键，一个值，一条左链接和一条右链接，一个节点计数器。左链接指向一棵小于该节点的所有键组成的二叉查找树，右链接指向一颗由大于该节点的所有键组成的二叉查找树。
• 查找：从根节点开始，在每个结点中查找的进程都会递归的在他的一个子节点展开，对于命中的查找，路径在含有被查找的键的结点处结束。对于未命中的查找，路径的终点是一个空连接
• 插入：如果树是空的，就返回一个含有键值对的新节点；如果被查找的键小于根节点的键，继续在左子树中插入该键，否则往右子树中插入该键
• 向下取整或向上取整：如果给定的key值小于二叉查找树的根节点的键，那么小于等于key的最大键floor(key)一定在根节点的左子树中；如果给定的key值大于二叉查找树的根节点的键，那么只有当根节点右子树存在且小于等于key的节点是，小于等于key的最大键floor(key)才会出现在右子树中，否则根节点就是小于等于key的最大键。
• 排名：如果给定的键和根节点的键相等，返回左子树的节点总数；如果给定的键小于根节点，返回该键在左子树的排名；如果给定的键大于根节点，返回t+1(根节点)加上他在右子树的排名
• 选择：如果左子树的节点数t大于k，则继续递归的在左子树中查找排名为k的键；如果相等，返回根节点的键；如果t小于k,递归的在右子树中查找排名为（k-t-1）的键。
• 删除最小键：如果被删除的节点只有一个节点，则将该节点的子节点顶上；如果有两个节点，则找到右节点的最小节点，将该节点作为替代节点，该节点的右节点为删除该节点后的右子树，左节点为原来被删除节点的左子树。
• 范围查找：中序遍历方式，打印根节点的左子树的所有键，然后打印根节点，在打印右子树

package 二叉排序树;

import java.util.LinkedList;
import java.util.Queue;

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 n) {
            this.key = key;
            this.val = val;
            N = n;
        }
    }

    public int size() {
        return size(root);
    }

    public int size(Node root) {
        if (root == null) return 0;
        else return root.N;
    }

    public Value get(Key key) {
        return get(root, key);
    }

    public Value get(Node root, Key key) {
        if (root == null) return null;
        int vmp = key.compareTo(root.key);
        if (vmp < 0) return get(root.left, key);
        else if (vmp > 0) return get(root.right, key);
        else return root.val;
    }

    public void put(Key key, Value val) {
        root = put(root, key, val);
    }

    public Node put(Node root, Key key, Value value) {
        if (root == null) return new Node(key, value, 1);
        int cmp = key.compareTo(root.key);
        if (cmp < 0) root.left = put(root.left, key, value);
        else if (cmp > 0) root.right = put(root.right, key, value);
        else root.val = value;
        root.N = size(root.left) + size(root.right) + 1;
        return root;
    }

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

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

    public Key floor(Key key) {
        Node x = floor(root, key);
        if (x == null) return null;
        return x.key;
    }

    //向下取整，小于等于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;
    }

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

    private Node max(Node x) {
        if (x.right == null)
            return x;
        return max(x.right);
    }

    public Key ceiling(Key key) {
        return ceiling(root, key).key;
    }

    private Node ceiling(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp == 0) return x;
        else if (cmp > 0) return ceiling(x.right, key);
        Node t = floor(x.left, key);
        if (t != null) return t;
        else return x;
    }

    public Key select(int k) {
        return select(root, k).key;
    }

    //选择，找到排名为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) {
        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 1 + size(x.left) + rank(key, x.right);
        else return size(x.left);
    }

    //删除最大键
    public void deleteMax() {

    }

    //    删除最小建
    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);
    }

    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.N = size(x.left) + size(x.right) + 1;
        return x;
    }
//    查找范围
    public Iterable<Key> keys(){
        return keys(min(),max());
    }
    private Iterable<Key> keys(Key lo,Key hi){
        Queue<Key> queue=new LinkedList<>();
        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.offer(x.key);
        if(cmphi>0) keys(x.right,queue,lo,hi);
    }

}

二、平衡查找树

• 一棵2-3查找树或为一颗空树，或由以下节点组成：
  • 2-节点：含有一个键（及其对应的值）和两条连接，左连接指向的2-3树中的键都小于该节点，右链接指向的2-3树中的键都大于节点；
  • 3-节点：含有两个键（及其对应的值）和三条连接，左连接指向的2-3树中的键都小于该节点，中链接指向的2-3树中的键都位于该节点的两个键之间，右链接指向的2-3树中的键都大于该节点。
• 插入
  
  • 向2-节点插入新键：把这个2-节点替换成一个3-节点，将要插入的键保存在其中即可
  • 向一棵只含有3-节点的树中插入新键：先临时将新键存入该节点中，使之成为一个4-节点，将这个4-节点转换成3个2-节点的2-3树，其中一个节点（根）含有中键，一个结点含有3个键中的最小者，一个结点含有3个键中的最大者。树的高度加1
  • 向一个父节点为2-节点的3-节点中插入新键：
  • 向一个父节点为3-节点的3-节点插入新键：