[Data Structure]Binary Search Tree

本文主要涉及BST的构造以及order operation方面的内容：

• Structure
• 插入
• 查询
• 删除
• Order Operation
• 统计所有大于查询key的节点数
• 统计所有小于查询key的节点数
• 统计落在查询区间的节点数
• 找到大于查询key的最小节点
• 找到小于查询key的最大节点
• 找到查询key的后继节点
• 找到查询key的前驱结点
• 找到第k个大的节点

BST的节点如下图所示，count是用来统计以node为根的树的size，包括node本身：

	private class Node {
	private Key key;
	private Value value;
	private int count;
	private Node left, right;
	public Node(Key key, Value value) {
	this.key = key;
	this.value = value;
	count = 1;
	left = null;
	right = null;
	}
	}

view raw TreeNode.java hosted with ❤ by GitHub

1. Insert

插入节点我们在Insert Node in BST中已经讨论过了，就不细讲了。

2. Get

跟插入的思路是一样的

代码如下：

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

view raw BST get.java hosted with ❤ by GitHub

3. Delete
我们在 Remove Node' in BST中已经讨论过了，不细说。

4. Larger Than and Lower Than
思路跟二分是一样的，以lowerthan为例，如果在当前节点curr，value < curr.val 那么我们去左子结点继续统计。如果value > curr.val那么左子树size和当前节点都满足条件，然后去右子结点继续寻找。如果value == curr.val直接返回左子树size。largerthan的代码是类似的。

lowerthan代码如下：

	public int lowerThan(Key key) {
	return lowerThan(root, key);
	}
	private int lowerThan(Node node, Key key) {
	if (node == null)
	return 0;
	int comp = key.compareTo(node.key);
	if (comp < 0)
	return lowerThan(node.left, key);
	else if (comp > 0)
	return 1 + size(node.left) + lowerThan(node.right, key);
	else
	return size(node.left);
	}

view raw BST lowerthan.java hosted with ❤ by GitHub

5. Range Query
我们在Search Range in BST已经讨论过，这里只需要返回数量，更简单一些。

6. Floor(小于查询key的最大节点) and Ceiling(大于查询key的最小节点)
思路也是二分, 以ceiling为例，如果在当前节点curr，value >curr.val 那么我们去右子结点继续寻找。如果value <curr.val那么curr可能是可能不熟，我们先去左子树找，找不到的话就返回curr，找到的话就返回找到的。如果value == curr.val直接返回curr。floor的代码是类似的。

ceiling代码如下：

	public Key ceiling(Key key) {
	return ceiling(root, key);
	}
	private Key ceiling(Node node, Key key) {
	if (node == null)
	return null;
	int comp = key.compareTo(node.key);
	if (comp > 0)
	return ceiling(node.right, key);
	else if (comp == 0)
	return node.key;
	else {
	Key k = ceiling(node.left, key);
	return k == null? node.key: k;
	}
	}

view raw BST ceiling.java hosted with ❤ by GitHub

7. Predecessor and Successor
和Floor 和 Ceiling的思路基本上一直，代码只有小小的区别。

successor代码如下:

	public Key successor(Key key) {
	return successor(root, key);
	}
	private Key successor(Node node, Key key) {
	if (node == null)
	return null;
	int comp = key.compareTo(node.key);
	if (comp >= 0)
	return successor(node.right, key);
	else {
	Key x = successor(node.left, key);
	return x == null? node.key: x;
	}
	}

view raw BST sucessor.java hosted with ❤ by GitHub

8. Find Kth
思路也是二分。n = 左子树的size + 1，是curr节点在tree里面排序的位置，从小到大。如果n < k的话，去右子树找第k - n个。如果n > k的话，去左子树找第k个。如果n==k说明curr正是我们要找的。

代码如下:

	public Key findKth(int k) {
	if (k < 1 || k > size())
	return null;
	return findKth(root, k);
	}
	private Key findKth(Node node, int k) {
	if (node == null)
	return null;
	int mid = node.left == null? 1: node.left.count + 1;
	if (mid < k)
	return findKth(node.right, k - mid);
	else if (mid > k)
	return findKth(node.left, k);
	else
	return node.key;
	}

view raw BST findKth.java hosted with ❤ by GitHub

完整代码如下:

	public class BST<Key extends Comparable<Key>, Value> {
	private class Node {
	private Key key;
	private Value value;
	private int count;
	private Node left, right;
	public Node(Key key, Value value) {
	this.key = key;
	this.value = value;
	count = 1;
	left = null;
	right = null;
	}
	}
	private Node root;
	public BST() {
	root = null;
	}
	public Key peek() {
	return root.key;
	}
	public int size() {
	return size(root);
	}
	private int size(Node node) {
	if (node == null)
	return 0;
	return node.count;
	}
	public void put(Key key, Value value) {
	root = put(root, key, value);
	}
	private Node put(Node node, Key key, Value value) {
	if (node == null) {
	node = new Node(key, value);
	return node;
	}
	int comp = key.compareTo(node.key);
	if (comp < 0)
	node.left = put(node.left, key, value);
	else if (comp > 0)
	node.right = put(node.right, key, value);
	else
	node.value = value;
	node.count = 1 + size(node.left) + size(node.right);
	return node;
	}
	public Value get(Key key) {
	return get(root, key);
	}
	private Value get(Node node, Key key) {
	if (node == null)
	return null;
	int comp = key.compareTo(node.key);
	if (comp < 0)
	return get(node.left, key);
	else if (comp > 0)
	return get(node .right, key);
	else
	return node.value;
	}
	public void delete(Key key) {
	root = delete(root, key);
	}
	private Node delete(Node node, Key key) {
	if (node == null)
	return null;
	int comp = key.compareTo(node.key);
	if (comp < 0)
	node.left = delete(node.left, key);
	else if (comp > 0)
	node.right = delete(node.right, key);
	else {
	if (node.left == null)
	return node.right;
	if (node.right == null)
	return node.left;
	//find successor
	Node x = node;
	node = findMin(x.right);
	node.right = deleteMin(x.right);
	node.left = x.left;
	}
	node.count = 1 + size(node.left) + size(node.right);
	return node;
	}
	private Node findMin(Node node) {
	while(node.left != null) {
	node = node.left;
	}
	return node;
	}
	private Node deleteMin(Node node) {
	if (node.left == null)
	return node.right;
	node.left = deleteMin(node.left);
	node.count = 1 + size(node.left) + size(node.right);
	return node;
	}
	//order operations
	public int lowerThan(Key key) {
	return lowerThan(root, key);
	}
	private int lowerThan(Node node, Key key) {
	if (node == null)
	return 0;
	int comp = key.compareTo(node.key);
	if (comp < 0)
	return lowerThan(node.left, key);
	else if (comp > 0)
	return 1 + size(node.left) + lowerThan(node.right, key);
	else
	return size(node.left);
	}
	public int largerThan(Key key) {
	return largerThan(root, key);
	}
	private int largerThan(Node node, Key key) {
	if (node == null)
	return 0;
	int comp = key.compareTo(node.key);
	if (comp > 0)
	return largerThan(node.right, key);
	else if (comp < 0)
	return 1 + size(node.right) + largerThan(node.left, key);
	else
	return size(node.right);
	}
	public int rangeQuery(Key lo, Key hi) {
	if (lo.compareTo(hi) > 0)
	return 0;
	return rangeQuery(root, lo, hi);
	}
	private int rangeQuery(Node node, Key lo, Key hi) {
	if (node == null)
	return 0;
	if (!(lo == null) && lo.compareTo(node.key) > 0)
	return rangeQuery(node.right, lo, hi);
	if (!(hi == null) && hi.compareTo(node.key) < 0)
	return rangeQuery(node.left, lo, hi);
	if (lo == null)
	return size(node.left) + 1 + rangeQuery(node.right, lo, hi);
	if (hi == null)
	return rangeQuery(node.left, lo, hi) + 1 + size(node.right);
	return rangeQuery(node.left, lo, null) + 1 + rangeQuery(node.right, null, hi);
	}
	public Key floor(Key key) {
	return floor(root, key);
	}
	private Key floor(Node node, Key key) {
	if (node == null)
	return null;
	int comp = key.compareTo(node.key);
	if (comp < 0)
	return floor(node.left, key);
	else if (comp == 0)
	return node.key;
	else {
	Key k = floor(node.right, key);
	return k == null? node.key: k;
	}
	}
	public Key ceiling(Key key) {
	return ceiling(root, key);
	}
	private Key ceiling(Node node, Key key) {
	if (node == null)
	return null;
	int comp = key.compareTo(node.key);
	if (comp > 0)
	return ceiling(node.right, key);
	else if (comp == 0)
	return node.key;
	else {
	Key k = ceiling(node.left, key);
	return k == null? node.key: k;
	}
	}
	public Key successor(Key key) {
	return successor(root, key);
	}
	private Key successor(Node node, Key key) {
	if (node == null)
	return null;
	int comp = key.compareTo(node.key);
	if (comp >= 0)
	return successor(node.right, key);
	else {
	Key x = successor(node.left, key);
	return x == null? node.key: x;
	}
	}
	public Key predecessor(Key key) {
	return predecessor(root ,key);
	}
	private Key predecessor(Node node, Key key) {
	if (node == null)
	return null;
	int comp = key.compareTo(node.key);
	if (comp <= 0)
	return predecessor(node.left, key);
	else {
	Key x = predecessor(node.right, key);
	return x == null? node.key: x;
	}
	}
	public Key findKth(int k) {
	if (k < 1 || k > size())
	return null;
	return findKth(root, k);
	}
	private Key findKth(Node node, int k) {
	if (node == null)
	return null;
	int mid = node.left == null? 1: node.left.count + 1;
	if (mid < k)
	return findKth(node.right, k - mid);
	else if (mid > k)
	return findKth(node.left, k);
	else
	return node.key;
	}
	}

view raw BST.java hosted with ❤ by GitHub