二叉查找数
定义
一个二叉查找数（BST）是一颗二叉树，其中每个结点都含有一个Comparable的键以及相关联的值，且每个结点的键都大于其左子树的任意结点的键，小于其右子树的任意结点的键
基本实现
- 数据表示
键+ 值+ 左链接+右链接+结点计数器 - 查找
如果树是空的，则查找未命中；如果查找的键小于当前结点的键，则继续查找其左子树；如果查找的键大于当前结点的键，则继续查找其右子树；如果查找的键等于当前结点的键，则查找命中。 - 插入
如果树是空的，则返回一个含有该键值对的新结点。如果被查找的键小于根节点的键，则继续在左子树中插入该键，否则在右子树中插入该键。（记得更新节点计数器） - 性能分析
二叉查找数的算法的运行时间依赖于树的形状，而树的形状则取决于键的插入顺序。如果插入一个有序的键值对，则会出现最坏情况。
由N个随机键构造的二叉查找数，查找命中和插入命中的平均所需比较次数为~2lnN(1.39lgN)。
二叉查找和插入的成本都是对数级别的（相比于二分查找的优势）
有序性相关的方法实现
- 最大键和最小键
最小键：如果左链接为空，最小键就是根节点；如果左链接非空，最小键就是左子树的最小键
最大键：如果右链接为空，最大键就是根节点；如果右链接非空，最大键就是右子树的最大键 - 向上取整和向下取整
floor(key) : key等于二叉树的根节点，返回根节点的值
2.1 key小于二叉树的根节点，floor（key）一定在根节点的左子树中
2.2 key大于二叉树的根节点
2.2.1 右子树中存在小于等于key的结点时，floor（key）在右子树中
2.2.2 否则返回根节点 - 选择操作
查找排名为k的键（树中有k个小于它的节点），假设左子树的结点数为t
3.1 如果t > k 在左子树中查找排名为k的键
3.2 如果t < k 在右子树中查找排名为k-t-1的键
3.3 如果t=k 返回根节点 - 排名
返回给定键在树中的排名
4.1 如果给定的键小于根节点的键，则返回该键在左子树中的排名
4.2 如果给定的键大于根节点的键，则返回该键在右子树中的排名+左子树的节点个数+1
4.3 如果给定的键等于根节点的键，则返回左子树的节点个数 - 删除最大值和最小值
deleteMin():如果左子树不为空，则要删除的节点在左子树；如果左子树为空，则返回该节点的右子树 - 删除操作
如果某个节点左右子树都不为空，删除节点以后，会产生两个子树而被删除的节点的父节点只空出了一个链接。可以使用被删除节点的后继节点（右子树中的最小节点）补充它的位置。
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;
}
}
