查找

JAVA中用Map实现查找，根据key查找value。下面介绍几种Map数据结构的实现

有序数组的二分查找

用key[]和value[]来保存Key-value，一对key-value的下标也相等
该实现的核心是rank(key)方法，该方法通过二分查找，找到key在key[]里的下标，如果不存在，返回key[]中比key小的key的数目。所以，rank方法返回的就是key在key[]中的下标（无论是已经存在了还是将要插入）
该实现在put，get，delete方法时，均会调用rank方法。而rank方法的时间复杂度因为用了二分，所以是O(logN)

public class BinarySearchST<Key extends Comparable<Key>, Value> {
	private Key keys[];
	private Value values[];
	private int N = 0;// 元素数量

	@SuppressWarnings("unchecked")
	public BinarySearchST(int capacity) {
		keys = (Key[]) new Comparable[capacity];
		values = (Value[]) new Object[capacity];
	}

	public int size() {
		return N;
	}

	public boolean isEmpty() {
		return N == 0;
	}

	/**
	 * 根据Key返回对应的Value
	 */
	public Value get(Key key) {
		if (key == null) {
			throw new RuntimeException("key can't be null");
		}
		if (isEmpty()) {
			return null;
		}

		int i = rank(key);
		if (i < N && keys[i].compareTo(key) == 0) {
			return values[i];
		} else {
			return null;
		}

	}

	/**
	 * 二分查找，如果命中，返回下标，如果未命中，返回小于该值的数目
	 * keys[rank(key)]:大于等于key的最小值
	 * keys[rank(key)-1]:小于等于key的最大值
	 */
	public int rank(Key key) {
		int lo = 0, hi = N - 1;
		while (lo <= hi) {
			int mid = lo + (hi - lo) / 2;
			int t = key.compareTo(keys[mid]);
			if (t > 0) {
				lo = mid + 1;
			} else if (t < 0) {
				hi = mid - 1;
			} else {
				return mid;
			}
		}
		return lo;
	}

	/**
	 * 向符号表中添加键值对
	 */
	public void put(Key key, Value value) {
		if (key == null) {
			throw new RuntimeException("key can't be null");
		}

		// 命中，i为key的下标
		// 未命中，i为key插入到数组后的下标
		int i = rank(key);
		
		// 命中，已存在，更新
		if (i < N && keys[i].compareTo(key) == 0) {
			values[i] = value;
			return;
		}

		// 未命中添加,此时是有序添加
		for (int j = N; j > i; j--) {
			keys[j] = keys[j - 1];
			values[j] = values[j - 1];
		}
		keys[i] = key;
		values[i] = value;
		N++;
	}

	/**
	 * 根据key删除键值对 将该键后面的键前移
	 */
	public void delete(Key key) {
		if (key == null) {
			throw new RuntimeException("key can't be null");
		}
		int i = rank(key);
		// 未命中
		if (i == N || keys[i].compareTo(key) != 0) {
			return;
		}
		
		// 命中，key后面的元素前移
		for (int j = i; j < N - 1; j++) {
			keys[j] = keys[j + 1];
			values[j] = values[j + 1];
		}
		// 最后一位留空
		keys[N - 1] = null;
		values[N - 1] = null;
		N--;

	}

	// 返回最小键
	public Key min() {
		return keys[0];
	}

	public Key max() {
		return keys[N - 1];
	}

	/**
	 * 根据下标找key
	 */
	public Key select(int k) {
		return keys[k];
	}

	/**
	 * 大于等于该键的最小键
	 */
	public Key ceiling(Key key) {
		// key比Keys里的key都大！返回keys[N]应该是null！
		int i = rank(key);
		return keys[i];

	}

	/**
	 * 小于等于该键的最大键
	 */
	public Key floor(Key key) {
		// 有该键
		if (get(key) != null) {
			return keys[rank(key)];
		} else if (get(key) == null && rank(key) != 0) {// 不存在该键且rank(key)不再数组最左边
			return keys[rank(key) - 1];
		} else {
			return null;	// key比keys里的key都小
		}

	}
	
	/**
	 * 迭代器的实现:返回一个将所有的Key都入队的Queue 
	 */
	public Iterable<Key> key(){
		Queue<Key> queue=new Queue<Key>();
		for(int i=0;i<N;i++){
			queue.enqueue(keys[i]);
		}
		return queue;
	}
	

	public static void main(String[] args) {
		BinarySearchST<String, Integer> st = new BinarySearchST<String, Integer>(10);
		st.put("A", 3);
		st.put("C", 2);
		st.put("B", 1);
		System.out.println(st.key());//A B C
		System.out.println(st.get("B"));
		System.out.println(st.ceiling("D"));// null
		st.delete("A");
		System.out.println(st.get("A"));// null
		System.out.println(st.floor("A"));// null
		System.out.println(st.key());// B C

	}

}

二叉查找树

二叉树的实现都是采用递归，将每个操作的逻辑理顺，之后递归就可以了。
注意，有些方法例如put元素、删除元素，会对途经的节点产生影响，注意在递归返回的时候更新节点
向上向下取整的方法比较难理解：向上取整一定最后会访问左子树，如果左子树找到结果，返回结果，否则返回父节点
删除节点：删除节点的做法是用被删节点的右子树中最小的节点代替被删节点

public class BST<Key extends Comparable<Key>, Value> {

	private Node root;// 根结点

	/**
	 * 结点类，用于储存键-值对、左右结点以及结点计数器 size(x)=size(x.left)+size(x.right)+1;
	 * 
	 * @author he
	 *
	 */
	private class Node {
		private Key key;// 键
		private Value value;// 值
		private Node left, right;// 指向左右子树的连接
		private int N;// 以该结点为根的子树中的结点数

		public Node(Key key, Value value, int N) {
			this.key = key;
			this.value = value;
			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) {
		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存在则更新，否则添加新结点
		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);
		} else 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;
	}

	// 返回最小键
	public Key min() {
		return min(root).key;
	}

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

	// 返回最大键
	public Key max() {
		return max(root).key;
	}

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

	// 向下取整，小于等于key的最大键
	public Key floor(Key key) {
		Node x = floor(root, key);
		if (x == null) {
			return null;
		} else {
			return x.key;
		}
	}

	/**
	 * 如果key小于根节点则向下取整一定左子树中， 如果大于根结点，则可能在右子树中,如果没有右子数，则根结点就是满足条件的key
	 */
	private Node floor(Node x, Key key) {
		if (x == null) {
			return null;
		}

		int cmp = key.compareTo(x.key);
		// 如果root.key > key，root = root.left
		if (cmp < 0) {
			return floor(x.left, key);
		}

		// 如果root.key <= key，root = root.right
		Node t = floor(x.right, key);
		// 如果右子节点为空，返回当前节点，否则递归右子节点的结果就是小于等于key的最大值
		if (t != null) {
			return t;
		} else {
			return x;
		}

	}

	// 向上取整,大于等于key的最小键
	public Key ceiling(Key key) {
		Node x = ceiling(root, key);
		if (x == null) {
			return null;
		} else {
			return x.key;
		}
	}

	/**
	 * 求大于key的最小节点
	 * 如果key4大于根结点3则向上取整一定在右子树中，如果key4小于根结点6，则结果可能在节点6的左子树（假设存在大于key4的子节点）
	 * 所以递归左子树返回时，如果找到了（递归返回非空），则返回结果; 如果没找到返回空，则返回根节点6
	 */
	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;
		}

	}

	// 根据索引查找键
	public Key select(int k) {
		if (k < 0 || k >= size())
			throw new IllegalArgumentException();
		return select(root, k).key;
	}

	/**
	 * 如果左子树的结点数t大于k，则递归地在左子树中查找排名为k的键； 如果t等于k，在返回根结点的键；
	 * 如果t小于k，递归地在右子树中查找排名为（k-t-1）的键
	 */
	private Node select(Node x, int k) {
		// 返回排名为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(root, key);
	}

	/**
	 * 如果给定的键和根结点的键相等，返回根节点左子树的结点总数t
	 * 如果给定的键比根结点的键小,递归左子树计算；
	 * 如果给定的键比根结点的键大，返回根结点左子树结点总数t+1+它在右子树的排名
	 */
	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);
		}

	}

	// 删除最小的结点
	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 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;
		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);
		// key < node.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());
	}

	// 遍历指定范围内的键
	public Iterable<Key> keys(Key lo, Key hi) {
		Queue<Key> queue = new Queue<Key>();
		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);
		
		// 如果根节点大于lo，递归左子数组
		if (cmplo < 0) {
			keys(x.left, queue, lo, hi);
		}
		// 左子数组递归完毕，如果根节点在范围内，加入当前节点
		if (cmplo <= 0 && cmphi >= 0) {
			queue.enqueue(x.key);
		}
		// 如果根节点小于hi，递归右子数组
		if (cmphi > 0) {
			keys(x.right, queue, lo, hi);
		}

	}

	public static void main(String[] args) {
		BST<String, Integer> bst = new BST<String, Integer>();
		bst.put("S", 0);
		bst.put("E", 1);
		bst.put("A", 2);
		bst.put("C", 3);
		bst.put("R", 4);
		bst.put("X", 5);
		bst.put("H", 6);
		bst.put("M", 7);
		System.out.println(bst.get("E"));
		bst.deleteMin();
		System.out.println(bst.min());
		System.out.println(bst.max());
		System.out.println(bst.floor("G"));
		System.out.println("ceiling:" + bst.ceiling("A"));
		System.out.println(bst.select(1));
		System.out.println(bst.rank("S"));
		bst.deleteMin();
		System.out.println(bst.select(0));
		bst.deleteMax();
		System.out.println(bst.select(bst.size() - 1));
		bst.delete("X");
		System.out.println(bst.get("X"));
		for (String s : bst.keys()) {
			System.out.print(s + " ");
		}
	}
}

2-3查找树

二叉查找树每个节点都只有一个key，两个子节点
2-3查找树，每个节点有1或2个key，2或3个子节点。当有1个key时，有左右子节点；当有2个key时，有左中右三个子节点

二叉查找树在顺序插入的时候，性能最差，因其已经变成了链表
但2-3查找树在最差的情况下，依然有较好的查找性能
其插入的原则是：保证节点最多有2个key，如果加入造成某个节点有3个key，将中间的节点弹到父节点，递归处理

红黑二叉查找树

红黑树是2-3查找树的二叉版

上面说到，2-3查找树在节点有2个key时，包含3个子节点，这一点不符合二叉树的定义
红黑树是二叉树，它是怎么对2-3查找树改造的呢？

对于2-3查找树中存在2个key的节点，用一条红色链接将2个key分成2个节点，这里红色链接是左链接
链接指向的节点（较小的节点）定义为红色节点，其余节点为黑色节点

因为2-3查找树是平衡树（叶子节点到根节点的距离相等），而2-3查找树中只有“3节点”的较小的key为红黑树中的红色节点，所以一个“3节点”包含一个红色节点一个黑色节点，又因为2-3查找树是平衡树，所以

红黑树中，每条到叶子节点的路径上包含相同数目的黑色节点（就是红黑树转为2-3查找树后，根节点到叶子节点的节点数）

如何向红黑树中插入元素呢？

向红黑树中插入元素，与向查找二叉树插入元素的逻辑一致，只是因为加入了红黑节点的定义，所以需要分别讨论像”3节点”和”2节点”插入元素时的情况。
两者的相同点就是，在对红黑树插入元素时，均将节点当作是红节点！

虽然红色链接是左链接，但在向红黑树添加元素的过程中，也有可能出现两条红色链接连在一起的情况，或者红色链接是右链接，以下就对向“3节点”插入元素的三种情况，做讨论：

• 插入元素小于两个key
  例如，对“3节点”（6，7），如果插入5，则成为（5，6，7），这时红黑树中的5、6均为红节点，但这不符合2-3查找树的定义，所以红黑树中不可能存在两个红节点连接。
  对于这种情况，前面提到， 2-3查找树是通过上弹中间元素6来解决的。对于红黑树，对应的操作是对（6，7）这条红链接做右旋操作！

  右旋操作，会将左链接变为右链接，子节点为红节点，父节点的颜色与原来左链接的父节点颜色一致。

这会导致：5节点和7节点均为红节点

如果一个父节点的子节点均为红节点，则将两个红节点置为黑节点，将父节点设为红色（父节点非根节点时）。原因是，6上弹后，将其左右两个节点变成了"2节点"，而父节点自己变成了"3节点"中的一员

• 插入元素大于两个key
  如果新加入节点8比（6，7）都大呢？，看上去，6、7均是红色节点，但是8加入后，向上弹7构成了一个标准的二叉树，所以：

  这时，会产生两个红色子节点，所以将两个子节点均变为黑节点

• 插入元素在两个key之间
  如果新加入的节点是6.5，介于（6，7）之间呢？

  对红色链接（6，6.5）做左旋操作，这样红黑树出现了之前说的第一种情况，然后再按照第一种情况处理即可

可以将上述情况概括为：

• 如果出现两个左红色链接，做右旋（将上面的左链接变为右链接）后，将两个子节点变为黑节点

• 如果出现一左红链接一右红链接（两个红链接不是对应同一个根节点），做左旋（将右链接变为左链接）后同上
• 如果两条红色链接位于同一个根节点，将两个子节点变为黑节点，父节点变为红节点
  无论是左旋还是右旋，目的都是将弹上去的元素作为根节点！

对于向"2节点"插入元素，比较简单：

• 插入的元素是左子节点，那没毛病，标准的红链接，不用动
• 插入的元素是右子节点，做左旋操作即可