【数据结构】关于二叉搜索树，你知道如何实现增删模拟吗？？？（超详解）
【数据结构】关于二叉搜索树，你知道如何实现增删模拟吗？？？（超详解）
📚️1.二叉搜索树
1.1概念：
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 • 它的左右子树也分别为二叉搜索树
1.2二叉树图片：
如上图，二叉搜索树的左子树都满足小于根结点的值，而右子树都满足大于根结点的值；并且在中序遍历时可以发现数据是一个由小到大排列的数据。
📚️2.二叉树的查找模拟
2.1思路分析
1.进行根结点的判断: 如果根结点的值正好等于我们要查找的数据，那么直接返回true; 2.进行子节点的判断: 如果子节点的值小于我们要查找的数值，那么就去结点的右边进行查找，反之就去结点 的左边进行查找 3.结束判断: 当没有找到结点时，我们的搜索指针此时指向空结点，那么此时跳出循环，没有找到， 返回false
2.2画图演示
2.3代码实现
public boolean search(int val){
if(root.val==val){
return true;
}
TreeNode cur=root;
while (cur!=null){
if(cur.val<val){
cur=cur.right;
}else if(cur.val>val){
cur=cur.left;
}else {
return true;
}
}
return false;
}注意：在进行操作之前要进行节点的创建，才能进行增删等操作；在查找过程中首先要进行根结点的判断，如果找到了直接返回true，返回进入一下循环查找，这里的cur要不断进行跟新，直到为空结点时才能跳出循环。
📚️3.二叉搜索树的插入模拟
3.1思路分析
1.根结点的判断： 如果根结点为空那么直接插入，root等于插入结点 2.子节点的判断： 如果子结点的值小于插入的数值，那么就进行右边子结点的判断，反之进行左边子节点 的判断 3.插入的结点判断： 执行以上步骤后，超如位置，因该为叶子结点，且满足二叉搜素树的特点
3.2画图演示
3.3代码实现
public void insert(int val){
TreeNode node=new TreeNode(val);
if(root==null){
root=node;
return;
}
TreeNode parent=null;
TreeNode cur=root;
while (cur!=null){
if (cur.val<val){
parent=cur;
cur=cur.right;
}else if (cur.val>val){
parent=cur;
cur=cur.left;
}else {
return;
}
}
if(parent.val<val){
parent.right= node;
}else {
parent.left=node;
}
}注意：这里要根据结点数据，初始化结点；设置parent指针，当cur跳出循环时为空，它的父亲节点为parent，再根据parent所指数据大小进行左边插入还是右边插入；还有当插入的结点数据等于其中某个数据时，就不能进行插入操作。
📚️4.二叉搜索树的删除模拟
4.1思路分析
在删除的过程中我们要讨论如下几点情况： 设待删除结点为 cur, 待删除结点的双亲结点为 parent 1.当 cur.left == null时： 1. cur 是 root，则 root = cur.right 2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.right 3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.right 2. 当cur.right == null时： 1. cur 是 root，则 root = cur.left 2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.left 3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.left 3. 当cur.left != null && cur.right != null时： 需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用 它 的值填补到被删除节点中，再来处理该结点的删除问题
4.2画图演示
4.3代码实现
1.找到要删除的节点cur：
public void remove(int key) {
TreeNode cur = root;
TreeNode parent = null;
while (cur != null) {
if(cur.val < key) {
parent = cur;
cur = cur.right;
}else if(cur.val > key) {
parent = cur;
cur = cur.left;
}else {
removeNode(parent,cur);
return;
}
}
}和上述查找的过程一致，但是这里的parent始终指向cur的双亲结点，当找到要删除的节点之后执行另一个函数即可。
2.实现删除的核心代码：
private void removeNode(TreeNode parent, TreeNode cur) {
if(cur.left == null) {
if(cur == root) {
root = cur.right;
}else if(parent.left == cur) {
parent.left = cur.right;
}else {
parent.right = cur.right;
}
}else if(cur.right == null) {
if(cur == root) {
root = cur.left;
}else if(parent.left == cur) {
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;
}
}
}注意：这里就要根据上述思路分析进行条件判断，除了cur左右孩子是否为空的情况下，还要判断cur属于parent的那边孩子的结点，当然还有删除结点cur是否为根结点的条件判断。
在进行删除操作的时候，如果删除结点的左右树都不为空，那么此时我们要进行找到替罪羊的方法，找到左边或者右边的其中之一的替罪羊，但是由于改变节点，需要管理其子结点，所以这里的删除并不是真正意义上的删除，其实是赋值替罪羊的值过后，在对其替罪羊进行操作，这样大大减少了对删除结点的左右子树的管理 。
📚️5.性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
所以查找时间复杂度 ~~最好情况： O(logN) ~~最坏情况： O(N)
📚️6.总结
💬💬在本期小编讲解了，关于二叉搜索树的概念，以及增删查的重要功能模拟，以及二叉搜索树的性能分析。
关于二叉搜索树来说，模拟情况有助于我们更加深入了解其功能方法的内部实现原理~~~
🌅🌅🌅~~~~最后希望与诸君共勉，共同进步！！！
💪💪💪以上就是本期内容了， 感兴趣的话，就关注小编吧。
😊😊 期待你的关注~~~
腾讯云开发者
