1.二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
从上述概念以及图中可以看出，二叉搜索树具有以下特性：
- 二叉搜索树中最左侧的节点是树中最小的节点，最右侧节点一定是树中最大的节点
- 采用中序遍历遍历二叉搜索树，可以得到一个有序的序列
二叉搜索树的结构代码
public static class TreeNode {
// 定义节点的三个属性
int val; // 节点的值
TreeNode left; // 子节点的引用，指向左子树
TreeNode right; // 子节点的引用，指向右子树
// 构造函数，用于创建一个具有指定值的节点
public TreeNode(int val) {
this.val = val;
}
}
2.二叉搜索树的查找
既然将其称之为二叉搜索树，因此这棵树最主要的作用是进行查询，而且其查询原理特别简单，具体如下:
假如要查找一个值val，
- 首先从根节点开始查找，如果根节点为空，返回null
- 如果根节点不为空，则将val与根节点的值进行比较，此时会分为3种情况
a. 根节点的值 等于 val ，返回当前引用。
b. 根节点的值 大于 val，由于根节点右边的值都比根节点的值大，所以我们去根节点的左子树进行查找。
c. 根节点的值 小于 val，由于根节点左边的值都比根节点的值小，所以我们去根节点的右子树进行查找。
举个例子：在以下二分搜索树中寻找 43 元素
- 根节点的42元素小于43元素，向右查找
- 当前节点的59元素大于43元素，向左查找
- 当前节点的51元素大于41元素，向左查找
- 当前节点的43元素等于43元素，找到了！
二叉搜索树的查找代码
//查找
public TreeNode search(int key) {
// 初始化一个指针cur，指向根节点root
TreeNode cur = root;
// 开始一个while循环，只要cur不为null，就继续查找
while (cur != null) {
// 如果cur节点的值小于key，说明key应该在cur的右子树中
if (cur.val < key) {
// 将cur更新为其右子节点，继续在右子树中查找
cur = cur.right;
// 如果cur节点的值大于key，说明key应该在cur的左子树中
} else if (cur.val > key) {
// 将cur更新为其左子节点，继续在左子树中查找
cur = cur.left;
// 如果cur节点的值等于key，说明找到了匹配的节点
} else {
// 直接返回当前节点
return cur;
}
}
//没找到，返回null
return null;
}
3.二叉搜索树的插入
关于二叉搜索树的插入，我们首先要知道：
- 新插入的节点一定在叶子节点上。
- 二叉搜索树中不能插入重复的元素
原因：
- 新插入的节点最终会位于叶子节点上。这是因为插入操作会从根节点开始，沿着树向下寻找合适的位置来放置新节点。新节点会与路径上的每个节点进行比较，直到找到一个空的位置（即叶子节点），然后将新节点插入到这个位置。
- 如果允许插入重复的元素，那么这些重复的元素既可以放在左子树也可以放在右子树，这会破坏二叉搜索树的性质，导致树的结构混乱，从而影响搜索、插入和删除等操作的效率。
二叉搜索树插入新节点的一般步骤：
- 从根节点开始，比较新节点的值与当前节点的值。
- 如果新节点的值小于当前节点的值，则移动到当前节点的左子节点；如果新节点的值大于当前节点的值，则移动到当前节点的右子节点。
- 重复步骤2，直到找到一个空的位置（即叶子节点）。
- 将新节点插入到这个空位置。
举个例子：向如下二分搜索树中插入元素 61
- 需要插入的元素 61 比 42 大，比较 42 的右子树根节点。
- 61 比 59 大，所以需要把 61 移动到 59 右子树相应位置，而此时为空，直接插入作为 59 的右子节点。
二叉搜索树的插入代码
// 插入操作，将给定值插入到二叉搜索树中
public void insert(int val) {
// 创建一个新节点
TreeNode node = new TreeNode(val);
// 如果根节点为空，则将新节点作为根节点
if (root == null) {
root = node;
return;
}
// 定义当前节点为根节点，父节点初始化为空
TreeNode cur = root;
TreeNode parent = null;
// 在二叉搜索树中查找插入位置
while (cur != null) {
parent = cur;
if (cur.val < val) {
// 如果当前节点值小于插入值，则向右子树移动
cur = cur.right;
} else if (cur.val > val) {
// 如果当前节点值大于插入值，则向左子树移动
cur = cur.left;
} else {
//在二叉搜索树中相同的值不能重新插入
return;
}
}
// 将新节点插入到找到的位置
if (parent.val < val) {
// 如果父节点值小于插入值，则将新节点作为右子节点
parent.right = node;
} else {
// 如果父节点值大于插入值，则将新节点作为左子节点
parent.left = node;
}
}
4.二叉搜索树的删除
对于二叉搜索树的删除，相对来说就比较麻烦了。因为要考虑以下三种情况：
1.要删除的是叶子结点
2.要删除的结点只有一个孩子结点
3.要删除的结点有左、右两棵子树
一. 删除只有左孩子的节点，如下图节点 58。
删除掉元素 58，让左子树直接代替 58 的位置，整个二分搜索树的性质不变。
二. 删除只有右孩子的节点，如下图节点 58。
删除掉元素 58，让右子树直接代替 58 的位置，整个二分搜索树的性质不变。
三.删除左右都有孩子的节点，如下图节点 58。
a.找到右子树中的最小值，为节点 59（替罪羊）
b.节点 59 代替待删除节点 58，并删除掉节点59
小小的总结一下：
根据该节点的子节点情况，分三种情况进行删除：
- 如果要删除的节点没有左子节点，则将该节点的右子节点替换该节点。
- 如果要删除的节点没有右子节点，则将该节点的左子节点替换该节点。
- 如果要删除的节点既有左子节点又有右子节点，则找到该节点右子树中最小的节点（替罪羊），将该节点的值替换为要删除的节点的值，然后删除该节点。
二叉搜索树的删除代码
// 删除给定值的节点
public boolean remove(int key) {
TreeNode cur = root; // 从根节点开始查找
TreeNode parent = null; // 记录当前节点的父节点
while (cur != null) { // 循环直到找到节点或者遍历完整棵树
if (cur.val > key) { // 如果当前节点值大于要删除的值
parent = cur; // 记录当前节点为父节点
cur = cur.left; // 向左子树移动
} else if (cur.val < key) { // 如果当前节点值小于要删除的值
parent = cur; // 记录当前节点为父节点
cur = cur.right; // 向右子树移动
} else { // 如果当前节点值等于要删除的值
// 找到了要删除的节点，开始删除
removeNode(cur, parent);
return true; // 返回删除成功
}
}
return false; // 没有找到要删除的值，返回删除失败
}
// 删除节点的具体操作
public void removeNode(TreeNode cur, TreeNode parent) {
if(cur.left == null) { // 如果要删除的节点没有左子树
if(cur == root) { // 如果要删除的节点是根节点
root = cur.right; // 将根节点指向其右子节点
} else if (cur == parent.right) { // 如果要删除的节点是父节点的右子节点
parent.right = cur.right; // 将父节点的右子节点指向要删除节点的右子节点
} else { // 如果要删除的节点是父节点的左子节点
parent.left = cur.right; // 将父节点的左子节点指向要删除节点的右子节点
}
} else if (cur.right == null){ // 如果要删除的节点没有右子树
if(cur == root) { // 如果要删除的节点是根节点
root = cur.left; // 将根节点指向其左子节点
} else if (cur == parent.left) { // 如果要删除的节点是父节点的左子节点
parent.left = cur.left; // 将父节点的左子节点指向要删除节点的左子节点
} else { // 如果要删除的节点是父节点的右子节点
parent.right = cur.left; // 将父节点的右子节点指向要删除节点的左子节点
}
} else { // 如果要删除的节点既有左子树又有右子树
// 找到要删除节点的右子树中的最小节点，即右子树中的最左节点
TreeNode remove = cur.right;
TreeNode prev = cur;
while (remove.left != null) { // 循环找到最左节点
prev = remove; // 记录当前节点为前一个节点
remove = remove.left; // 向左移动
}
cur.val = remove.val; // 将当前节点的值替换为最小节点的值
if(cur == prev) { // 如果要删除的节点的右子树只有一个节点
cur.right = remove.right; // 将当前节点的右子树指向最小节点的右子树
} else { // 如果要删除的节点的右子树有多个节点
prev.left = remove.right; // 将最小节点的父节点的左子树指向最小节点的右子树
}
}
}
5.二叉搜索树的查询性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为: l o g 2 ( N ) log_2(N) log2(N)
最差情况下，二叉搜索树退化为单支树，其平均比较次数为:
N / 2 N/2 N/2
6. 全部代码
public class BinarySearchTree {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode root = null;
//插入
public void insert(int val) {
TreeNode node = new TreeNode(val);
if (root == null) {
root = node;
return;
}
TreeNode cur = root;
TreeNode parent = null;
while (cur != null) {
parent = cur;
if (cur.val < val) {
cur = cur.right;
} else if (cur.val > val) {
cur = cur.left;
} else {
//在二叉搜索树中相同的值不能重新插入
return;
}
}
if (parent.val < val) {
parent.right = node;
} else {
parent.left = node;
}
}
//查找
public TreeNode search(int key) {
TreeNode cur = root;
while (cur != null) {
if (cur.val < key) {
cur = cur.right;
} else if (cur.val > key) {
cur = cur.left;
} else {
return cur;
}
}
return null;
}
//删除key的值
public boolean remove(int key) {
TreeNode cur = root;
TreeNode parent = null;
while (cur != null) {
if (cur.val > key) {
parent = cur;
cur = cur.left;
} else if (cur.val < key) {
parent = cur;
cur = cur.right;
} else {
//找到了，开始删除
removeNode(cur, parent);
return true;
}
}
return false;
}
public void removeNode(TreeNode cur, TreeNode parent) {
if(cur.left == null) {
if(cur == root) {
root = cur.right;
} else if (cur == parent.right) {
parent.right = cur.right;
} else {
parent.left = cur.right;
}
} else if (cur.right == null){
if(cur == root) {
root = cur.left;
} else if (cur == parent.left) {
parent.left = cur.left;
} else {
parent.right = cur.left;
}
} else {
//都不为空
TreeNode remove = cur.right;
TreeNode prev = cur;
while (remove.left != null) {
prev = remove;
remove = remove.left;
}
cur.val = remove.val;
if(cur == prev) {
cur.right = remove.right;
} else {
prev.left = remove.right;
}
}
}
}
