（点击
上方公众号
，可快速关注）
来源：ziwenxie，
http://www.ziwenxie.site/2017/03/18/algorithm-binary-search-tree/
如有好文章投稿，请点击 → 这里了解详情
引言
二叉查找树是一种能将链表插入的灵活性和有序数组查找的高效性结合起来的一种重要的数据结构，它是我们后面学习红黑树和AVL树的基础，本文我们就先来看一下二叉查找树的实现原理。
二叉查找树的定义
二叉查找树最重要的一个特征就是：每个结点都含有一个Comparable的键及其相关联的值，该结点的键要大于左子树中所有结点的键，而小于右子树中所有结点的键。
下图就是一个典型的二叉查找树，我们以结点E为例，可以观察到，左子树中的所有结点A和C都要小于E，而右子树中所有的结点R和H都要大于结点E。
二叉查找树
在实现二叉查找树中相关操作之前我们先要来定义一个二叉查找树，由于Java中不支持指针操作，我们可以用内部类Node来替代以表示树中的结点，每个Node对象都含有一对键值(key和val)，两条链接(left和right)，和子节点计数器(size)。另外我们还提前实现了size(), isEmpty()和contains()这几个基础方法，三种分别用来计算二叉树中的结点数目，判断二叉树是否为空，判断二叉树中是否含有包含指定键的结点。
public class BST
, Value> {
private Node root; // root of BST
private class Node {
private Key key; // sorted by key
private Value val; // associated data
private Node left, right; // left and right subtrees
private int size; // number of nodes in subtree
public Node(Key key, Value val, int size) {
this.key = key;
this.val = val;
this.size = size;
}
}
// Returns the number of key-value pairs in this symbol table.
public int size() {
return size(root);
}
// Returns number of key-value pairs in BST rooted at x.
private int size(Node x) {
if(x == null) {
return 0;
} else {
return x.size;
}
}
// Returns true if this symbol table is empty.
public boolean isEmpty() {
return size() == 0;
}
// Returns true if this symbol table contains key and false otherwise.
public boolean contains(Key key) {
if(key == null) {
throw new IllegalArgumentException("argument to contains() is null");
} else {
return get(key) != null;
}
}
}
查找和插入操作的实现
查找操作
我们先来看一下如何在二叉树中根据指定的键查找到它相关联的结点。查找会有两种结果：查找成功或者不成功，我们以查找成功的情形来分析一下整个查找的过程。前面我们提到了二叉查找树的一个重要特征就是：左子树的结点都要小于根结点，右子树的结点都要大于根结点。根据这一性质，我们从根结点开始遍历二叉树，遍历的过程中会出现3种情况：
-
如果查找的键key小于根结点的key，说明我们要查找的键如果存在的话肯定在左子树，因为左子树中的结点都要小于根结点，接下来我们继续递归遍历左子树。
-
如果要查找的键key大于根结点的key，说明我们要查找的键如果存在的话肯定在右子树中，因为右子树中的结点都要大于根节点，接下来我们继续递归遍历右子树。
-
如果要查找的键key等于根结点的key，那么我们就直接返回根结点的val。
二叉树查找流程图
上面的操作我们利用递归可以非常容易的实现，代码如下：
/**
* Returns the value associated with the given key.
*
* @param key the key
* @return the value associated with the given key if the key is in the symbol table
* and null if the key is not in the symbol table
* @throws IllegalArgumentException if key is null
*/
public Value get(Key key) {
if(key == null) {
throw new IllegalArgumentException("first argument to put() is null");
} else {
return get(root, key);
}
}
private Value get(Node x, Key key) {
if(x == null) {
return null;
} else {
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;
}
}
}
插入操作
如果理解了上面的查找操作，插入操作其实也很好理解，我们首先要找到我们新插入结点的位置，其思想和查找操作一样。找到插入的位置后我们就将新结点插入二叉树。只是这里还要加一个步骤：更新结点的size，因为我们刚刚新插入了结点，该结点的父节点，父节点的父节点的size都要加一。
二叉树插入流程图
插入操作的实现同样有多种实现方法，但是递归的实现应该是最为清晰的。下面的代码的思想和get基本类似，只是多了x.N = size(x.left) + size(x.right) + 1;这一步骤用来更新结点的size大小。
/**
* Inserts the specified key-value pair into the symbol table, overwriting the old
* value with the new value if the symbol table already contains the specified key.
* Deletes the specified key (and its associated value) from this symbol table
* if the specified value is null.
*
* @param key the key
* @param val the value
* @throws IllegalArgumentException if key is null
*/
public void put(Key key, Value val) {
if(key == null) {
throw new IllegalArgumentException("first argument to put() is null");
}
if(val == null) {
delete(key);
return;
}
root = put(root, key, val);
// assert check(); // Check integrity of BST data structure.
}
private Node put(Node x, Key key, Value val) {
if(x == null) {
return new Node(key, val, 1);
} else {
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;
}
// reset links and increment counts on the way up
x.size = size(x.left) + size(x.right) + 1;
return x;
}
}
select与rank的实现
select的实现
上面我们的get()操作是通过指定的key去在二叉查找树中查询其关联的结点，二叉查找树的另外一个优点就是它可以一定程度上保证数据的有序性，所以我们可以较高效的去查询第n小的数据。
首先我们来思考一个问题：怎么知道一个二叉查找树中小于指定结点的子结点的个数？这一点根据二叉查找树的性质-左子树中的结点都要小于根结点很容易实现，我们只需要统计左子树的大小就行了。结合下面这幅图，以查找二叉树第4小的结点我们来看一下select操作的具体流程。
依次遍历二叉树，我们来到了下图中的E结点，E结点的左子树有2个结点，它是二叉树中第3小的结点，所以我们可以判断出要查找的结点肯定在E结点的右子树中。由于我们要查找第4小的结点，而E又是二叉树中第3小的结点，所以我们要查找的这个结点接下来肯定要满足一个特征：E的右子树中只有0个比它更小的结点，即右子树中最小的结点H。
二叉树select流程图
select的实现如下，实际就是根据左子树的结点数目来判断当前结点在二叉树中的大小。
/**
* Return the kth smallest key in the symbol table.
*
* @param k the order statistic
* @return the kth smallest key in the symbol table
* @throws IllegalArgumentException unless k is between 0 and n-1
*/
public Key select(int k) {
if (k < 0 || k >= size()) {
throw new IllegalArgumentException("called select() with invalid argument: " + k);
} else {
Node x = select(root, k);
return x.key;
}
}
// Return the key of rank k.
public Node select(Node x, int k) {
if(x == null) {
return null;
} else {
int t = size(x.left);
if(t > k) {
return select(x.left, k);
} else if(t < k) {
return select(x.right, k);
} else {
return x;
}
}
}
rank就是查找指定的键key在二叉树中的排名，实现代码如下，思想和上面一致我就不重复解释了。
/**
* Return the number of keys in the symbol table strictly less than key.
