写在前面
在之前的一篇文章里介绍了二叉树的遍历操作。事实上我们经常用的二叉树有一种叫做二叉搜索树（Binary Search Tree）， 简称 BST。
二叉搜索树的定义如下：
- 任意节点的左子树中的键值都 小于 此节点的键值。
- 任意节点的右子树中的键值都 大于 此节点的键值。
- 任意节点的左子树和右子树都是二叉搜索树。
可以看到，由于它的特性，二叉搜索树是一个有序的集合。因此我们可以利用二叉搜索树，就。 因此，我们就可以在二叉搜索树中以较低的时间代价执行查询、更新、删除操作。 这些操作的时间复杂度与树的高度成正比，或者说是 O(logN)，N 是树中所有节点数。
与此同时，为了维护这样一个结构，BST 的插入、删除操作也变得更复杂了一点。 后面我们会看一下这两个基本操作，但是首先我们需要了解一下 BST 很有用的一个特点。
有序性与树的构建
不难想象，BST 的中序遍历是很特别的。它中序遍历产生的列表是一个有序的，实际上是递增的列表。 很多时候，我们都是利用这个特性，通过一次中序遍历来完成很多有用的操作。
同样的，我们也可以反过来，通过 BST 中序遍历的列表反向构造一个二叉搜索树。 具体做法也很简单，我们在递增列表当中取一点，那么，索引在它前面的，值都比他小， 也就位于二叉树的左子树上；同理，它右边的值都位于这个节点的右子树上。 如此递归下去便构建了一棵树。事实上我们通常选择列表的中点作为根节点，这样一来， 最后生成的树就比较对称。树的节点均匀分布，在这种情况下树的高度最低，树查询、删除的效率也最高。 这样的树更接近于平衡。否则在最糟糕的情况下，我们始终选择最大值或者最小值， 那么这棵二叉搜索树的右子树或者左子树始终为空，节点的值一边倒，二叉树退化成链表。
如果列表不是有序的话，这个算法表示的就是生成一个较为平衡的普通的树。
class BST {
// 从有序列表中取值构建 BST
fun generateBST(li: List<Int>): TreeNode? {
if (li.isEmpty()) {
return null
}
val mid = li.size / 2
val root = TreeNode(li[mid]) // 取中点作为根节点
root.left = generateBST(li.subList(0, mid))
root.right = generateBST(li.subList(mid + 1, li.size))
return root
}
class TreeNode(var value: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
}
插入操作
事实上，我们也可以选择利用插入操作构建一棵树。我们只要新建一个根节点，然后向其中不断插入值就可以了。 当然了，这种情况下，树的平衡与否，跟我们根结点的选择就有很大关系了。不过在已有的 BST 中插入新值并保证 它还是 BST 是常见的需要，所以我们需要了解一下插入操作。
插入的算法比较简单，我们只要按 BST 的规则来。每次把二叉树根节点的值与待插入的值作比较， 如果待插入的值比当前节点值小，那么它应该插在当前节点的左子树上；如果左子树为空，我们就找到了要插入的地方， 新建一个节点容纳待插入的值，然后把它嫁接到左子树上；如果不为空就递归地调用插入函数处理左子树；右子树同理。
fun insert(root: TreeNode, new: Int) {
if (new < root.value) { // 查看左子树
if (root.left == null) { // 到头了，插入
root.left = TreeNode(new)
return
}
insert(root.left!!, new) // 递归向下
} else {
if (root.right == null) { // 到头了，插入
root.right = TreeNode(new)
return
}
insert(root.right!!, new) // 已经判过空了，可以断言不为 null
}
}
删除操作
删除操作稍微复杂一点。考虑比较简单的情况，如果要删除的节点是叶子节点，那么直接删掉就好了。但是， 如果要删除的节点有孩子，那要怎么办呢？我们可以想办法，把它的子树拼接到它的父树上去吗？ 如果只有一个孩子的话，好像是可以的，但如果有两个孩子呢？我们就得想办法给他们找一个新的节点当父节点， 然后把这个新节点接回原来删除的节点的父节点。我们想到了，因为二叉搜索树是有序的， 那么我们可以找值大小与它相近的节点来替代它。比如下面这棵二叉搜索树
7
/ \
4 10
/ \ \
2 6 12
\ /
3 5
它的中序遍历集合是 [2, 3, 4, 5, 6, 7, 10, 12]，如果我们要删除 4，那么我们可以找节点 3 和 5 来代替他的位置。 然后我们会发现，这个算法也适用于只有一个孩子的情况。所以我们对删除操作采用这个统一的算法。而且， 这个算法不大会破坏二叉搜索树的平衡性。
先给邻近的节点做一个明确的定义：
- Successor 代表的是中序遍历序列的下一个节点。即比当前节点大的最小节点，简称后继节点。
- Predecessor 代表的是中序遍历序列的前一个节点。即比当前节点小的最大节点，简称前驱节点。
我们先放一放前驱和后继结点具体是怎样找到的。先假设我们已经实现了这样的功能，让我们来实现二叉搜索树的删除功能吧。 这里用 Java 代码来写。
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.value == key) { // 找到了要删除的点
if (root.left == null && root.right == null) {
// 要删除的节点为叶子节点，可以直接删除
root = null;
} else if (root.right != null) {
// 要删除的几点不是叶子节点且拥有右节点，则该节点可以由该节点的后继节点进行替代，
// 该后继节点位于右子树中较低的位置。然后可以从后继节点的位置递归向下操作以删除后继节点。
root.value = successor(root); // 不是真的删除节点，只要把它的值替换掉就好了
root.right = deleteNode(root.right, root.value); // 递归地，我的右子树是删除了替换节点的新子树
} else {
// 要删除的节点不是叶子节点，且没有右节点但是有左节点。这意味着它的后继节点在它的上面，
// 但是我们并不想返回。我们可以使用它的前驱节点进行替代，然后再递归的向下删除前驱节点
root.value = predecessor(root);
root.left = deleteNode(root.left, root.value);
}
} else if (root.value < key) { // 向右子树方向二叉搜索
root.right = deleteNode(root.right, key);
} else { // 向左子树方向二叉搜索
root.left = deleteNode(root.left, key);
}
return root; // we make use of side-effects to delete node, so always return root
}
接下来具体考虑一下前驱结点和后继结点究竟怎么找。
// 返回 successor 的值
private int successor(TreeNode node) {
// 先取当前节点的右节点，然后一直取该节点的左节点，直到左节点为空，则最后指向的节点为后继节点
node = node.right; // node.right wouldn't be null
while (node.left != null) {
node = node.left;
}
return node.value;
}
// 返回 predecessor 的值
private int predecessor(TreeNode node) {
// 先取当前节点的左节点，然后取该节点的右节点，直到右节点为空，则最后指向的节点为前驱节点
node = node.left; // node.right wouldn't be null
while (node.right != null) {
node = node.right;
}
return node.value;
}
这样二叉搜索树的基本操作也就讲完了。
最后附上GitHub：https://github.com/gonearewe
