一、概念
二叉搜索树（Binary Search Tree，简称BST）也称为二叉查找树或二叉排序树，是一种具有特殊性质的二叉树数据结构。
- 定义和性质：
- 二叉搜索树中的每个节点包含一个键值，习惯上我们说左子树上所有节点的键值均小于其根节点的键值，右子树上所有节点的键值均大于其根节点的键值。
- 二叉搜索树的左右子树也都是二叉搜索树。
- 它能够以 O(\log n) 的时间复杂度进行插入、删除和查找操作。
- 基本操作：
- 插入：将一个新值按照二叉搜索树的性质插入到适当的位置。
- 删除：从树中移除一个值，同时保证二叉搜索树的性质不被破坏。
- 查找：检查树中是否存在某个特定的值。
- 查询排名：查找比给定值小的数的个数加一（即该值在有序序列中的位置）。
- 查询指定排名的元素：找到有序序列中特定位置的元素。
- 求前驱和后继：分别找到小于某值的最大数和大于某值的最小数。
- 优势：
- 相比于数组，二叉搜索树提供了更快的插入和删除操作，因为数组的插入和删除操作需要移动大量元素来维护有序性，时间复杂度为O(n)；而链表虽然可以快速插入和删除，但是查找等其他操作的时间复杂度不够优秀。
- 二叉搜索树结合了两者的优点，对于上述每个操作都拥有较好的时间复杂度。
综上所述，二叉搜索树是计算机科学中一种非常重要的数据结构，它不仅提供了高效的数据检索功能，还允许数据的动态插入和删除，因此在数据库索引、内存管理等领域得到了广泛的应用。
二、图解
1.查找
有如下这样一颗二叉树，我们需要查询9所在节点
这时根节点值为7比目标值小，所以我们一应该去右子树中寻找
当前cur节点的值依旧比目标值9要小，于是我们又去他的右子树中寻找
此时cur节点值比目标值大，我们就可以去他的左边去寻找
此时相等结束寻找
2.插入
首先我们分别将21、1、15、10分别插入这颗二叉搜索树
首先我们需要找到合适的位置，定义一个指针从根节点开始寻找，先模拟插入1
此时值比待插入节点值大，于是去遍历左子树寻找合适的位置
还是比待插入节点大，再次往左走
依旧往左发现往左为空，于是我们就可以将1插入到此处，但是要想插入到这里，我们需要记录父亲节点，所以在遍历的时候我们需要记录父亲节点位置
重复上述步骤插入10
我们发现每次插入都落在了叶子节点上
所以我们只需要找到插入位置的父亲节点即可
3.删除
二叉搜索树的删除操作主要涉及以下几种情况：
- 删除叶子节点：如果待删除的节点是叶子节点，即没有子节点，可以直接删除该节点。
- 删除只有左子树的节点：如果待删除的节点只有一个左子节点，可以用其左子节点替代待删除节点的位置。
- 删除只有右子树的节点：如果待删除的节点只有一个右子节点，可以用其右子节点替代待删除节点的位置。
- 删除左右子树均不空的节点：这种情况最为复杂。通常的做法是找到该节点的右子树中的最小节点（或者左子树中的最大节点），用这个节点的值替换待删除节点的值，然后删除那个最小（或最大）节点。
具体步骤如下：
- 查找节点：首先需要找到要删除的节点。这通常是通过递归搜索完成的，比较待删除值与当前节点值的大小，然后决定是向左子树还是右子树继续搜索。
- 替换节点：一旦找到了要删除的节点，根据上述情况采取相应的替换策略。如果是第四种情况，需要找到合适的替换节点并进行值的交换。
- 维护BST性质：在删除节点后，需要确保树仍然保持二叉搜索树的性质，即任何节点的值都大于其左子树中的所有值，小于其右子树中的所有值。
- 处理替换节点的子树：如果替换节点有子节点，需要将其子节点接到被替换节点的相应位置，以保持树的结构完整性。
总的来说，二叉搜索树的删除操作是一个相对复杂的过程，需要根据不同的情况采取不同的策略，并且在整个过程中保持树的平衡和有序性。
下面将图解上述三种情况：
一、首先是待删除的节点没有左节点：
没有左节点将会分为以下三种情况：下图中节点值未按照二叉搜索树规则，注意节点位置即可其中值可忽略
1.待删除节点是根节点
只需要让根节点root指向root.right即可
2.待删除节点是父亲节点的左孩子
我们只需让parent.left=cur.right。
3.待删除节点是父亲节点右孩子
只需要让parent.right=cur.right
二、待删除节点没有右节点
1.待删除节点是根节点：
这个时候只需让root = root.left即可
2.待删除节点是父亲节点的左孩子
这个时候只需要让parent.left=cur.left
3.待删节点是父亲节点的右孩子
只需要让parent.right=cur.left
三、待删除节点有两个孩子
这种情况最为复杂。通常的做法是找到该节点的右子树中的最小节点（或者左子树中的最大节点），用这个节点的值替换待删除节点的值，然后删除那个最小（或最大）节点。
首先我们可以在待删除节点位置开始去他的左子树中寻找最大值（左子树中都比当前节点值小）然后进行替换，或者去右子树中寻找最小值进行替换
我们只需要在左子树中寻找到最大值，然后进行替换将左子树中最大值删掉即可
三、代码实现
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree extends 余胜军{
static class TreeNode extends 余胜军 {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
private TreeNode root;
public TreeNode search(int key) {
TreeNode cur = root;
while (cur != null) {
if (cur.val > key) {
cur = cur.left;
} else if (cur.val < key) {
cur = cur.right;
} else {
return cur;
}
}
return null;
}
public void display(TreeNode root) {
if (root == null) return;
display(root.left);
System.out.print(root.val + " ");
display(root.right);
}
public boolean insert(int val) {
TreeNode pre = null;
TreeNode cur = root;
if (cur == null) {
root = new TreeNode(val);
return true;
}
while (cur != null) {
if (cur.val < val) {
pre = cur;
cur = cur.right;
} else if (cur.val > val) {
pre = cur;
cur = cur.left;
} else {
return false;
}
}
if (pre.val > val) pre.left = new TreeNode(val);
else pre.right = new TreeNode(val);
return true;
}
public boolean remove(int key) {
TreeNode pre = null;
TreeNode cur = root;
while (cur != null) {
if (cur.val < key) {
pre = cur;
cur = cur.right;
} else if (cur.val > key) {
pre = cur;
cur = cur.left;
} else {
// 开始删除
return removeNode(pre, cur);
}
}
return false;
}
public void level() {
if (root == null) System.out.println("tree is null");
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- != 0) {
TreeNode top = queue.poll();
System.out.print(top.val + " ");
if (top.left != null) queue.offer(top.left);
if (top.right != null) queue.offer(top.right);
}
System.out.println();
}
}
private boolean removeNode(TreeNode pre, TreeNode cur) {
if (cur.left == null) { // 左为空
if (cur == root) {
root = root.right;
} else if (cur == pre.left) {
pre.left = cur.right;
} else {
pre.right = cur.right;
}
} else if (cur.right == null) { // 右为空
if (cur == root) {
root = root.left;
} else if (cur == pre.left) {
pre.left = cur.left;
} else {
pre.right = cur.left;
}
} else { // 左右都为空
// 寻找左左子树的最大值
TreeNode targetParent = cur;
TreeNode target = cur.left;
while (target.right != null) {
targetParent = target;
target = target.right;
}
// 替换
cur.val = target.val;
if (targetParent.left == target) targetParent.left = target.left;
else targetParent.right = target.left;
// TreeNode tp = cur;
// TreeNode t = cur.right;
// while (t.left != null) {
// tp = t;
// t = t.left;
// }
//
// cur.val = t.val;
// if (tp.left == t) tp.left = t.left;
// else tp.right = t.right;
}
return true;
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.insert(80);
tree.insert(30);
tree.insert(48);
tree.insert(60);
tree.insert(90);
tree.insert(56);
tree.display(tree.root);
System.out.println();
tree.remove(80);
tree.display(tree.root);
}
}
![【洛谷 P8748】[蓝桥杯 2021 省 B] 时间显示 题解（数学+模运算+输入输出）](https://img-blog.csdnimg.cn/direct/b0b0be3d726d42d68b51b27c44370020.png)
