在一组排好序的数中查找某个值是否在，有一种常用的方法叫做二分查找。二分查找的思想是，先判断这组数中间位置的那个元素是否和目标值相等，如果相等，则这个元素就是要查找的元素；否则，将数组从中间位置分成两半，假设数组是升序的，那么左半部分小于（等于）中间值，右半部分大于（等于）中间值，可以根据目标值和中间元素的大小比较，在对应的那一半数组中继续按这个方法递归查找。
有这样一种数据结构，他的构造方式和二分查找的思想类似。考虑一棵二叉树，对于其中的每一个节点，他的左子树中节点的值都比他的值小，右子树中节点的值都比他的值大。如果我们要查找一个值是否在这棵树中，可以从根节点开始，若当前节点的值和目标值相等，则该节点的值就是我们要查找的值；否则，若当前节点的值比目标值大，那么就在该节点的左子树中继续查找；若当前节点的值比目标值小，那么就在该节点的右子树中继续查找。这样的一棵二叉树被称为二叉查找树(Binary Search Tree, BST)。
向 BST 中插入值时，我们需要从根节点开始，向下找到一个满足二叉查找树条件成立的位置，把新的节点添加在这个位置即可。如果插入值小于当前节点的值，那插入值的位置一定在当前节点的左边，否则就在他的右边。
下面我们构造一棵二叉查找树，并实现他的插入和查找方法，默认没有值重复的节点。
// 节点类
public class Node {
// 节点的值
public int value;
// 左子节点
public Node left;
// 右子节点
public Node right;
public Node(int value) {
this.value = value;
}
}
// 二叉查找树
public class BST {
public Node root;
// 节点个数
public int size = 0;
public BST() {}
// 由数组构建 BST
public BST(int[] ary) {
for (int elem : ary) {
insert(elem);
}
}
// 插入值
public void insert(int elem) {
// 插入第一个值，作为根节点
if (root == null) root = new Node(elem);
// 当前节点的父节点
Node parent = null;
// 当前节点，从根节点开始
Node current = root;
// 遍历树，找到插入值的位置
while (current != null) {
// 若插入值小于当前节点的值，则从其左子树继续遍历
if (elem < current.value) {
parent = current;
current = current.left;
} else {
// 若插入值大于当前节点的值，则从其右子树继续遍历
parent = current;
current = current.right;
}
}
// 已遍历至叶节点，
// 比较插入值和叶节点的值，
// 在其左子节点或右子节点插入
if (elem < parent.value) {
parent.left = new Node(elem);
} else {
parent.right = new Node(elem);
}
++size;
}
// 查找目标值是否在树中
public boolean search(int target) {
// 从根节点开始
Node current = root;
while (current != null) {
// 如果目标值等于当前节点的值，表示已找到
if (target == current.value) return true;
// 若目标值小于当前节点的值，
// 在当前节点的左子树中继续找
if (target < current.value) {
current = current.left;
} else {
// 若目标值大于当前节点的值，
// 在当前节点的右子树中继续找
current = current.right;
}
}
// 遍历完还是没有找到
return false;
}
}
从 BST 中删除一个节点的时候就要小心了，如果删除的是叶节点，那么直接删除即可，不影响二叉查找树的成立条件；如果删除的是其他节点，我们就需要移动部分节点，使得这棵树能继续满足成立条件。
当我们删除 BST 中的某个节点时，由于他的左子树中的节点值都比他的值小，右子树中的节点值都比他大，就需要这样考虑：如果该节点有左子树，就从其左子树中找到一个最大值，把这个最大值的节点移到该节点的位置；如果该节点没有左子树，就把他的右子节点移到该节点的位置。删除方法如下：
// 删除 BST 中的节点
public boolean delete(int target) {
Node parent = null;
Node current = root;
// 查找值为目标值的节点
while (current != null) {
if (target == current.value) break;
if (target < current.value) {
parent = current;
current = current.left;
} else {
parent = current;
current = current.right;
}
}
// 没有找到目标值
if (current == null) return false;
// 当前节点没有左子树
if (current.left == null) {
// 删除的是根节点
if (parent == null) {
root = current.right;
} else {
// 当前节点是其父节点的左子节点
if (current.value < parent.value) {
parent.left = current.right;
} else {
// 当前节点是其父节点的右子节点
parent.right = current.right;
}
}
} else {
// 当前节点有左子树
// 找到左子树中的最大值，
// 移到当前节点的位置
// 左子树最大值节点的父节点
Node parentOfMax = current;
// 左子树中最大值节点
Node max = current.left;
// 遍历左子树，找到最大值的节点
while (max.right != null) {
parentOfMax = max;
max = max.right;
}
// 当前节点的左子树只有一个节点
if (current.left.value == max.value) {
// 把最大值赋给当前节点
current.value = max.value;
// 当前节点的左子树清空
current.left = null;
} else {
// 把最大值赋给当前节点
current.value = max.vlaue;
// 清空最大值节点
parentOfMax.right = null;
}
}
--size;
return true;
}