定义
二叉查找树（Binary Search Tree）是一个二叉树（Binary Tree），其中每个节点上都存储着一个键值对（key-value），并且每个节点的键都大于它左子树中所有节点的键、小于它右子树中所有节点的键。
如下是一个二叉查找树：
在这个二叉查找树示例中，每个节点上都存储着一个键值对，其中 : 左边的是键（key）、右边的是值（value）。
操作
二叉查找树支持以下几个基本操作：
- 插入：给定一个键值对，将其插入到二叉查找树中
- 删除：给定一个键，将其对应的键值对从二叉查找树中删除
- 查找：给定一个键，从二叉查找树中查找得到对应的值
由于二叉查找树是一个有序的数据结构，节点中键的大小决定了节点顺序，因此在二叉查找树的插入和删除操作中，必须维持好节点的顺序，不能破坏二叉查找树的性质。
插入操作
给定一个键值对，将其插入到二叉查找树中，完整的流程如下：
graph TD
start([开始])
finish([结束])
subgraph insert[ ]
givenAKeyValue[/给定一个键值对/]
noRoot{判断根节点<br>是否为空}
setRoot[创建一个新节点<br>作为根节点]
setKeyValue[将键值对存入新节点]
compare{比较给定的键<br>与节点的键的大小}
insertToLeft[["插入到左子树<br>（递归）"]]
insertToRight[["插入到右子树<br>（递归）"]]
replaceValue[用给定的值替换掉<br>当前节点的值]
givenAKeyValue-->noRoot
noRoot--是-->setRoot-->setKeyValue
noRoot--否-->compare
compare--小于-->insertToLeft
compare--大于-->insertToRight
compare--等于-->replaceValue
end
start-->givenAKeyValue
setKeyValue-->finish
replaceValue-->finish
其中，“插入到左子树”和“插入到右子树”两个操作是需要递归执行的，流程和上图相同。
在插入时，如果二叉查找树中已存在给定的键，那么它原先对应的值会被直接替换。否则，就需要创建一个新的节点来存储给定键值对，并且这个新节点一定是一个叶子节点。
删除操作
给定一个键，将其对应的键值对从二叉查找树中删除，完整的流程如下：
graph TD
start([开始])
finish([结束])
subgraph remove[ ]
givenAKey[/给定一个键/]
noRoot{判断根节点<br>是否为空}
compare{比较给定的键<br>与节点的键的大小}
removeFromLeft[["从左子树删除<br>（递归）"]]
removeFromRight[["从右子树删除<br>（递归）"]]
hasLeft{是否有左子树}
hasRight{是否有右子树}
removeNode1[删除当前节点]
removeNode2[删除当前节点]
setRightAsRoot[将右子树替换到<br>当前节点位置]
setLeftAsRoot[将左子树替换到<br>当前节点位置]
findSuccessor["找到右子树中最小的键<br>所在的节点（后继节点）"]
replaceValueWithSuccessor[用后继节点中的键值对<br>替换掉当前节点的键值对]
removeSuccessor[从右子树中删除后继节点]
givenAKey-->noRoot--否-->compare
compare--小于-->removeFromLeft
compare--大于-->removeFromRight
compare--等于-->hasLeft
hasLeft--否-->removeNode1-->setRightAsRoot
hasLeft--是-->hasRight
hasRight--否-->removeNode2-->setLeftAsRoot
hasRight--是-->findSuccessor-->replaceValueWithSuccessor-->removeSuccessor
end
start-->givenAKey
noRoot--是-->finish
setRightAsRoot-->finish
setLeftAsRoot-->finish
removeSuccessor-->finish
其中，“从左子树删除”和“从右子树删除”两个操作是需要递归执行的，流程和上图相同。
在删除时，如果二叉查找树中不存在给定的键，那么就不需要做任何操作。否则，就需要从二叉查找树中删除该键所在的节点。而此时该节点的左右子树存在情况，具体可划分成四种类型：
无左子树、无右子树
例如下面的二叉查找树：
假如要删除的键是 9，我们发现该节点既没有左子树、也没有右子树。这种情况我们直接将该节点删除即可，二叉查找树变为：
无左子树、有右子树
例如下面的二叉查找树：
假如要删除的键是 1，我们发现该节点没有左子树、但是有右子树。这种情况我们直接将该节点删除，并将右子树替换到该节点位置即可，二叉查找树变为：
有左子树、无右子树
例如下面的二叉查找树：
假如要删除的键是 5，我们发现该节点有左子树、但是没有右子树。这种情况我们直接将该节点删除，并将左子树替换到该节点位置即可，二叉查找树变为：
有左子树、有右子树
例如下面的二叉查找树：
假如要删除的键是 2，我们发现该节点既有左子树、也有右子树。这种情况我们不能简单地将该节点删除，而是需要通过以下步骤来完成：
- 找到该节点右子树中最小的键所在的节点（即后继节点）。在这个例子中，就是
3:D 所在的节点。
- 用后继节点中的键值对替换掉该节点的键值对。在这个例子中，就是将
2:A 替换成 3:D。
- 从该节点的右子树中删除后继节点。
最终二叉查找树变为：
查找操作
给定一个键，从二叉查找树中查找得到对应的值，完整的流程如下：
graph TD
start([开始])
finish([结束])
subgraph search[ ]
givenAKey[/给定一个键/]
noRoot{判断根节点<br>是否为空}
returnValue[/返回对应的值/]
returnNull[/返回空/]
compare{比较给定的键<br>与节点的键的大小}
searchFromLeft[["从左子树中查找<br>（递归）"]]
searchFromRight[["从右子树中查找<br>（递归）"]]
givenAKey-->noRoot
noRoot--是-->returnNull
noRoot--否-->compare
compare--小于-->searchFromLeft
compare--大于-->searchFromRight
compare--等于-->returnValue
end
start-->givenAKey
returnNull-->finish
returnValue-->finish
其中，“从左子树中查找”和“从右子树中查找”两个操作是需要递归执行的，流程和上图相同。
在查找时，如果二叉查找树中存在给定的键，那么就返回其对应的值。否则，返回空。
实现
由于二叉查找树只是在二叉树定义的基础上增加了几个操作，因此，我们可以基于二叉树来实现二叉查找树，二叉树的实现可以看我的另一篇文章：Java实现二叉树（Binary Tree）。
首先，我们需要定义两个接口（二叉查找树及其节点）：
接口类
二叉查找树及其节点的接口定义如下：
/**
* 二叉查找树接口
*
* @param <K> 存储的键类型
* @param <V> 存储的值类型
*/
public interface IBinarySearchTree<K extends Comparable<? super K>, V> extends IBinaryTree<V> {
@Override
INode<K, V> getRoot();
/**
* 插入给定键值对
*
* @param key 键
* @param value 值
*/
void insert(K key, V value);
/**
* 删除给定的键
*
* @param key 键
*/
void remove(K key);
/**
* 查找给定的键对应的值
*
* @param key 键
* @return 对应的值，找不到则返回null
*/
V search(K key);
/**
* 二叉查找树节点接口
*
* @param <K> 存储的键类型
* @param <V> 存储的值类型
*/
interface INode<K extends Comparable<? super K>, V> extends IBinaryTree.INode<V> {
/**
* @return 存储的键
*/
K getKey();
@Override
INode<K, V> getLeft();
@Override
INode<K, V> getRight();
}
}
由于二叉查找树需要根据键来比较大小，因此键必须是 Comparable 接口的子类。
其中，IBinarySearchTree 接口继承了二叉树的接口：IBinaryTree，并重写了其中的 getRoot 函数，用来获取二叉查找树根节点。
为了方便，我们将二叉查找树节点接口 INode 定义成了 IBinarySearchTree 的内部接口，它继承了二叉树节点的接口：IBinaryTree.INode，并重写了其中的 getLeft 和 getRight 函数，用来获取左右子节点。
实现类
二叉查找树的实现如下：
/**
* 二叉查找树实现
*
* @param <K> 存储的键类型
* @param <V> 存储的值类型
*/
public class BinarySearchTree<K extends Comparable<? super K>, V> implements IBinarySearchTree<K, V> {
private Node<K, V> root;
// 以下省略构造函数以及getter和setter
@Override
public void insert(K key, V value) {
// 具体实现见后续
}
@Override
public void remove(K key) {
// 具体实现见后续
}
@Override
public V search(K key) {
// 具体实现见后续
return null;
}
/**
* 二叉查找树节点实现
*
* @param <K> 存储的键类型
* @param <V> 存储的值类型
*/
public static class Node<K extends Comparable<? super K>, V> implements INode<K, V> {
private K key;
private V value;
private Node<K, V> left;
private Node<K, V> right;
// 以下省略构造函数以及getter和setter
}
}
类似的，为了方便，我们将 Node 类定义成了 BinarySearchTree 的内部类。
插入操作实现
insert 接口的实现如下：
@Override
public void insert(K key, V value) {
root = insertTo(key, value, root);
}
/**
* 将给定键值对插入到以node为根节点的二叉查找树中
*
* @param key 键
* @param value 值
* @param node 一个二叉查找树节点
* @return 操作完成之后的二叉查找树根节点
*/
private Node<K, V> insertTo(K key, V value, Node<K, V> node) {
if (node == null) {
return new Node<>(key, value);
}
int compareResult = key.compareTo(node.getKey());
if (compareResult < 0) {
node.setLeft(insertTo(key, value, node.getLeft()));
} else if (compareResult > 0) {
node.setRight(insertTo(key, value, node.getRight()));
} else {
node.setValue(value);
}
return node;
}
上面我们定义了一个私有方法 insertTo，其作用已经在注释中说明，其中包含了递归调用。然后，在 insert 方法中，我们通过调用 insertTo 将给定键值对插入到 root 中，从而实现二叉查找树的插入操作。
删除操作实现
remove 接口的实现如下：
@Override
public void remove(K key) {
root = removeFrom(key, root);
}
/**
* 从以node为根节点的二叉查找树中，删除给定的键
*
* @param key 键
* @param node 一个二叉查找树节点
* @return 操作完成之后的二叉查找树根节点
*/
private Node<K, V> removeFrom(K key, Node<K, V> node) {
if (node == null) {
return null;
}
int compareResult = key.compareTo(node.getKey());
if (compareResult < 0) {
node.setLeft(removeFrom(key, node.getLeft()));
} else if (compareResult > 0) {
node.setRight(removeFrom(key, node.getRight()));
} else {
Node<K, V> left = node.getLeft();
Node<K, V> right = node.getRight();
if (left == null) {
return right;
}
if (right == null) {
return left;
}
// 找到当前节点的后继节点
Node<K, V> successor = findMin(right);
// 用后继节点中的键值对替换掉当前节点的键值对
node.setKey(successor.getKey());
node.setValue(successor.getValue());
// 将后继节点从右子树删除
node.setRight(removeFrom(successor.getKey(), right));
}
return node;
}
/**
* 从以node为根节点的二叉查找树中，找到最小的键所在的节点
*
* @param node 一个二叉查找树节点
* @return 最小的键所在的节点
*/
private Node<K, V> findMin(Node<K, V> node) {
Node<K, V> left = node.getLeft();
return left == null ? node : findMin(left);
}
上面我们定义了两个私有方法 removeFrom 和 findMin，其作用已在注释中说明。removeFrom 方法中包含了递归调用。然后，在 remove 方法中，我们通过调用 removeFrom 从 root 中删除给定的键，从而实现二叉查找树的删除操作。
查找操作实现
search 接口的实现如下：
@Override
public V search(K key) {
Node<K, V> result = searchFrom(key, root);
return result == null ? null : result.getValue();
}
/**
* 从以node为根节点的二叉查找树中，找到给定的键所在的节点
*
* @param key 键
* @param node 一个二叉查找树节点
* @return 给定的键所在的节点
*/
private Node<K, V> searchFrom(K key, Node<K, V> node) {
if (node == null) {
return null;
}
int compareResult = key.compareTo(node.getKey());
if (compareResult < 0) {
return searchFrom(key, node.getLeft());
} else if (compareResult > 0) {
return searchFrom(key, node.getRight());
} else {
return node;
}
}
上面我们定义了一个私有方法 searchFrom，其作用已经在注释中说明，其中包含了递归调用。然后，在 search 方法中，我们通过调用 searchFrom 从 root 中找到给定的键所在的节点，从而实现二叉查找树的查找操作。
测试示例
下面通过一段Demo程序来测试和展示二叉查找树的功能：
public class Demo {
public static void main(String[] args) {
System.out.println("初始化一个空二叉查找树：");
BinarySearchTree<Integer, Character> tree = new BinarySearchTree<>();
PrintUtil.print(tree);
System.out.println("插入一个键值对7:A");
tree.insert(7, 'A');
PrintUtil.print(tree);
System.out.println("依次插入键值对3:B、 5:C、 9:D、 1:E");
tree.insert(3, 'B');
tree.insert(5, 'C');
tree.insert(9, 'D');
tree.insert(1, 'E');
PrintUtil.print(tree);
System.out.println("依次插入键值对4:F、 8:G、 2:H、 6:I");
tree.insert(4, 'F');
tree.insert(8, 'G');
tree.insert(2, 'H');
tree.insert(6, 'I');
PrintUtil.print(tree);
System.out.println("删除键1");
tree.remove(1);
PrintUtil.print(tree);
System.out.println("删除键9");
tree.remove(9);
PrintUtil.print(tree);
System.out.println("删除键3");
tree.remove(3);
PrintUtil.print(tree);
System.out.println("查找键5对应的值：" + tree.search(5));
System.out.println("查找键9对应的值：" + tree.search(9));
}
}
上面代码调用了我们前面实现的操作接口，并通过工具类中的方法 PrintUtil.print 将每一步的二叉查找树打印出来，最终输出的结果如下：
