⭐️前言⭐️
本篇文章——二叉搜索树既是对之前的文章【树与二叉树】的一些补充，也是给后续文章TreeMap和TreeSet接口介绍的铺垫。
博客主页： 【如风暖阳】
精品Java专栏【JavaSE】、【备战蓝桥】、【JavaEE初阶】、【MySQL】、【数据结构】
欢迎点赞 收藏 ⭐留言评论 私信必回哟本文由 【如风暖阳】 原创，首发于 CSDN
博主将持续更新学习记录收获，友友们有任何问题可以在评论区留言
博客中涉及源码及博主日常练习代码均已上传码云(gitee)、GitHub
在这里给大家推荐博主常用到的刷题网站【牛客网】,剑指Offer专栏是面试笔试题目高频题单，赶快刷起来吧！
内容导读
- 二叉搜索树
- 1.概念
- 2.查找操作
- 3.插入操作
- 4.删除操作
- 5.性能分析
二叉搜索树又称作二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
- 二叉搜索树的中序遍历结果是有序的
如下图所示就是一棵二叉搜索树
先通过代码完成二叉搜索树的基本构造：
public class BinarySearchTree {
static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode root;
}
2.查找操作
在搜索树中查找关键值，因为二叉搜索树的特性，所以可以将关键值与根节点值比较，如果比根节点值小，就去左子树中寻找，反之去右子树中寻找。
public TreeNode search(int key) {
TreeNode cur=root;
while (cur!=null) {
if(cur.val
cur=cur.right;
}else if(cur.val>key) {
cur=cur.left;
}else {
return cur;
}
}
//走到这里说明没有找到关键字
return null;
}
3.插入操作
插入操作依然遵循二叉搜索树的特性，与根节点值进行比较，如果比它小就往左子树中插入，如果比它大就往右子树中插入，可以发现，最后都是插入到了叶子节点上。因为插入操作需要让上一个节点有引用指向插入节点，所以需要使用两个节点。
public boolean insert(int key) {
TreeNode node=new TreeNode(key);
//空树直接插入
if(root==null) {
root=node;
return true;
}
TreeNode cur=root;
TreeNode parent=null;//用于存储上一个节点的引用
while (cur!=null) {
if(cur.val
parent=cur;
cur=cur.right;
}else if(cur.val>key) {
parent=cur;
cur=cur.left;
}else {
//存在相同的元素 则不能插入成功
return false;
}
}
//代码走到这里，cur==null，根据与上一个节点parent的val的比较，确定插入该结点的左还是右
if(parent.val
parent.right=node;
}else {
parent.left=node;
}
return true;
}
4.删除操作
二叉搜索树的删除操作十分复杂，首先需要找到要删除的节点，但是该结点可能有左右子树，所以不能直接删除，需要分情况来确定具体的删除方式，如下：
设待删除结点为 cur, 待删除结点的父结点为 parent
1.cur.left == null
- cur 是 root，则 root = cur.right
- cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
- cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
2.cur.right == null
- cur 是 root，则 root = cur.left
- cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
- cur 不是 root，cur 是 parent.right，则 parent.right = cur.left
3.cur.left != null && cur.right != null
需要使用替换法进行删除，即在它的右子树中寻找最小值（它一定没有左树）【或者在它的左子树中寻找最大值，它一定没有右树】，用它的值填补到被删除节点中，再来处理该结点的删除问题（处理该结点就和情况1相同，没有左子树）
代码实现：
public void remove(int key) {
//先找到该节点
TreeNode cur=root;
TreeNode parent=null;
while (cur!=null) {
if(cur.val
parent=cur;
cur=cur.right;
}else if(cur.val>key) {
parent=cur;
cur=cur.left;
}else {
//代码走到此处说明找到了要删除的节点
removeNode(cur,parent);
}
}
}
private void removeNode(TreeNode cur,TreeNode parent) {
if(cur.left==null) {
if(cur==root) {
root=root.right;
}else if(cur==parent.left) {
parent.left=cur.right;
}else {
parent.right=cur.right;
}
}else if(cur.right==null) {
if(cur==root) {
root=root.left;
}else if(cur==parent.left) {
parent.left=cur.left;
}else {
parent.right=cur.left;
}
}else {
TreeNode targetParent=cur;//记录用于替换的节点的上一个节点
TreeNode target=cur.right;//记录用于替换的节点
//在右子树中寻找最小值，就是一直往左走，走到尽头的节点就是最小值
while (target.left!=null) {
targetParent=target;
target=target.left;
}
//找到用于替换的节点，完成值的替换，再去处理删除这个替换节点
cur.val=target.val;
//此时该节点一定没有左子树，与之前没有左子树的删除方法相同
if(targetParent.left==target) {
targetParent.left=target.right;
}else {
targetParent.right=target.right;
}
}
}
5.性能分析
二叉搜索树的插入和删除操作都需要先进性查找，查找效率代表了二叉搜索树中各个操作的性能，根据不同的插入次序，得到的二叉树结构也可能不同。
最优情况：
得到一棵完全二叉树
查找的时间复杂度为O（
l
o
g
2
N
log_2N
log2N）
最差情况：
得到一棵单分支的树
查找的时间复杂度为O(N)
TreeMap 和 TreeSet (这两个接口在后边的文章中介绍)即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证，关于红黑树的内容后序再进行讲解。
⭐️最后的话⭐️
总结不易，希望uu们不要吝啬你们的哟(＾Ｕ＾)ノ~ＹＯ！！如有问题，欢迎评论区批评指正
