二叉搜索树¶
一、结构定义¶
二叉搜索树（binary search tree），也称为二叉查找树，是一种二叉树，同时还满足了以下的条件：
- 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值
- 任意节点的左、右子树也是二叉搜索树
相比于普通二叉树，二叉搜索树的节点之间带有大小关系，这使得二叉搜索树可以支持快速的查找、插入、删除操作。
比如说，这就是一棵二叉搜索树：
5
/ \
3 6
/ \ \
2 4 7
二、基本操作¶
2.1 遍历¶
二叉搜索树满足「左子节点 < 根节点 < 右子节点」的大小关系，而中序遍历恰好是按照「左 -> 根 -> 右」的顺序遍历：
5
/ \
3 6 中序遍历：2 3 4 5 6 7
/ \ \
2 4 7
因此，对二叉搜索树进行中序遍历的话，可以得到一个递增的有序序列。
利用中序遍历升序的性质，可以用二叉搜索树来实现排序：先将数据插入到二叉搜索树中，再进行中序遍历，就可以得到有序的数据序列。
2.2 查找¶
二叉搜索树满足「左子节点 < 根节点 < 右子节点」的大小关系，因此查找操作与二分查找类似，每次可以将查找区间缩小一半。
比如说，要查找值为 4 的节点：
二叉搜索树 查找 4
5 5 -- 第一轮
/ \ /
3 6 --> 3 -- 第二轮
/ \ \ \
2 4 7 4 -- 第三轮
查找过程就是，比较当前节点的值与目标值，根据判断结果决定向左子树还是右子树查找。
查询过程的伪代码类似这样：
TreeNode search(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (root.val < val) {
return search(root.right, val);
} else {
return search(root.left, val);
}
}
复杂度分析：
- 时间复杂度：O(logn)，查找次数最多是树的高度，平衡的二叉搜索树高度是 logn。
- 空间复杂度：O(1)。
2.3 插入¶
插入操作需要满足几个条件：
- 插入后必须能保持二叉搜索树「左子树 < 根节点 < 右子树」的性质
- 新插入节点必须是叶子节点
比如说，要插入值为 1 的节点：
二叉搜索树 插入 1
5 5
/ \ / \
3 6 --> 3 6
/ \ \ / \ \
2 4 7 2 4 7
/
1
插入的新节点必须是放在叶子节点，因此首先要找到插入位置，找的过程和查找操作类似。
插入过程的伪代码类似这样：
TreeNode insert(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (root.val < val) {
root.right = insert(root.right, val);
} else {
root.left = insert(root.left, val);
}
return root;
}
复杂度分析：
- 时间复杂度：O(logn)，插入需要查找，与查找操作的复杂度相同。
- 空间复杂度：O(1)。
2.4 删除¶
删除操作也需要满足：删除后必须能保持二叉搜索树「左子树 < 根节点 < 右子树」的性质。
因此，删除需要分为 3 种情况：
- 要删除的节点是叶子节点，可以直接删除
- 要删除的节点只有一个子节点，那么将子节点提升到要删除的节点的位置即可
- 要删除的节点有两个子节点，需要找到左子树中最大的节点，或者右子树中最小的节点来接替要删除的节点
(1) 删除叶子节点¶
比如说，要删除值为 4 的节点：
二叉搜索树 删除 4
5 5
/ \ / \
3 6 --> 3 6
/ \ \ / \
2 4 7 2 7
删除叶子节点的过程就是：
- 找到要删除的节点（4）。
- 然后将父节点（3）指向它（4）的指针置为 null。
(2) 删除只有一个子节点的节点¶
比如说，要删除值为 6 的节点：
二叉搜索树 删除 6
5 5
/ \ / \
3 6 --> 3 7
/ \ \ / \
2 4 7 2 4
删除只有一个子节点的节点的过程就是：
- 找到要删除的节点（6）。
- 然后将父节点（5）指向它（6）的指针指向它的子节点（7）。
(3) 删除有两个子节点的节点¶
比如说，要删除值为 5 的节点：
二叉搜索树 删除 5（替换节点4） 删除 5（替换节点6）
5 4 6
/ \ / \ / \
3 6 --> 3 6 或 3 7
/ \ \ / \ / \
2 4 7 2 7 2 4
删除有两个子节点的节点的过程就是：
- 找到要删除的节点（5）。
- 然后找到删除节点左子树中最大的节点（4），或者右子树中最小的节点（6），作为替换节点。
- 将替换节点（4/6）与要删除的节点（5）交换，然后删除要删除的节点（5）。
删除过程的伪代码类似这样（以右子树中最小的节点作为替换节点）：
TreeNode delete(TreeNode root, int val) {
if (root == null) {
return null;
}
if (root.val == val) {
// 找到要删除的节点
// 1. 删除叶子节点
if (root.left == null && root.right == null) {
return null;
}
// 2. 删除只有一个子节点的节点
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
// 3. 删除有两个子节点的节点
// 找到右子树中最小的节点，作为替换节点
TreeNode minNode = getMin(root.right);
// 删除 minNode（等价于交换 root 和 minNode，并删除 root）
root.right = delete(root.right, minNode.val);
// 用 minNode 替换 root
minNode.left = root.left;
minNode.right = root.right;
root = minNode;
} else if (root.val < val) {
// 去右子树删除
root.right = delete(root.right, val);
} else if (root.val > val) {
// 去左子树删除
root.left = delete(root.left, val);
}
return root;
}
因为删除涉及到了二叉搜索树的内部节点，为了保持它的性质，所以操作会稍微有点复杂。
复杂度分析：
- 时间复杂度：O(logn)，删除需要查找，与查找操作的复杂度相同。
- 空间复杂度：O(1)。
三、典型应用¶
- 索引：用作系统中的多级索引，实现高效的查找、插入、删除操作。
- 搜索算法：作为某些搜索算法的底层数据结构。
- 有序数据存储：用于存储数据流，以保持其有序状态。
- 范围查询：BST可用于执行范围查询，例如查找在给定范围内的所有元素。
- 自动补全和拼写检查：BST可用于实现自动补全和拼写检查功能，其中树中的节点存储单词或短语。
参考¶
https://www.hello-algo.com/chapter_tree/binary_search_tree/
https://time.geekbang.org/column/article/68334