Java数据结构超详细分析二叉搜索树
作者：未见花闻 发布时间：2022-12-01 01:34:20
1.搜索树的概念
二叉搜索树是一种特殊的二叉树，又称二叉查找树，二叉排序树，它有几个特点：
如果左子树存在，则左子树每个结点的值均小于根结点的值。
如果右子树存在，则右子树每个结点的值均大于根结点的值。
中序遍历二叉搜索树，得到的序列是依次递增的。
二叉搜索树的左右子树均为二叉搜索树。
二叉搜索树的结点的值不能发生重复。
2.二叉搜索树的简单实现
我们来简单实现以下搜索树，就不使用泛型了，二叉搜索树基本结构：
public class BinarySearchTree {
static class Node {
public int val;
public Node left;
public Node right;
public Node(int val) {
this.val = val;
}
}
public Node root;
//其他方法
}
2.1查找
二叉搜索树最擅长的就是查找，根据二叉搜索树的定义，左子树的元素比根小，右子树的元素比根大，所以我们只需要根据根结点的值与目标元素的值比较，就能实现查找功能。
根与目标元素相等，表示找到了。
根比目标元素大，去左子树找。
根比目标元素小，去右子树找。
左右子树找不到，那就找不到了。
参考实现代码：
public Node search(int key) {
Node cur = this.root;
while (cur != null) {
//根与目标元素相等，表示找到了。
if (cur.val == key) return cur;
//根比目标元素大，去左子树找。
else if (cur.val > key) cur = cur.left;
//根比目标元素小，去右子树找。
else cur = cur.right;
}
//此时cur = null, 左右子树找不到，那就找不到了。
return cur;
}
2.2插入
需要在二叉搜索树中插入一个元素，首先得找到一个合适的插入位置，如何找呢？其实就是利用搜索树查找的方式，找到一个空位，如何将目标结点插入到这个位置。
根与插入元素相等，插入元素不能与搜索树中的元素相等，插入失败。
根比插入元素大，去左子树找。
根比插入元素小，去右子树找。
找到的结点为空，那这个位置就是我们要找的空位。
由于你找到空位时，无法获取该空位的前一个位置，所以每次查找的时候都需要保存上一次查找的位置。
找到位置后，将目标结点插入到该位置。
参考实现代码：
public boolean insert(int val) {
//结点为空，直接插
if(root == null) {
root = new Node(val);
return true;
}
Node cur = this.root; //当前查找位置
Node parent = null; //查找的上一个位置
while (cur != null) {
parent = cur;
if (val > cur.val) cur = cur.right;
else if (val < cur.val) cur = cur.left;
else return false;
}
//开始插入，找到空位前一个位置，比插入元素小，空位在右边，插入右边
if (val > parent.val) {
parent.right = new Node(val);
} else {
//比插入元素大，空位在左边，插入左边
parent.left = new Node(val);
}
return true;
}
2.3删除
删除是搜索树基本操作中最麻烦的一个操作，需要考虑多种情况。
不妨设需要删除的结点为cur，cur的父结点为parent，搜索树的根结点为root。首先需要删除结点，那就得找到结点，所以第一步是找结点，思路与查找的思路一模一样。
第二步那就是删除了，删除结点大概有下面几种情况：
情况1：cur.left == null
cur == root，让root = cur.right;
cur != root且parent.left == cur，让parent.left = cur.right;
cur != root且parent.right == cur，让parent.right = cur.right。
情况2：cur.right == null
cur == null，让root = cur.left;
cur != root且parent.left == cur，让parent.left = cur.left;
cur != root且parent.right == cur，让parent.right = cur.left。
情况3：cur.left != null && cur.right != null
方案1：找到cur右子树中最小的元素target，然后将该元素的值覆盖到cur处（可以理解为交换），此时等价于删除target处的结点，即该结点的父结点为preTarget。
因为target为cur右子树最小的一个结点，所以target.left == null，此时preTarget.left == target，所以删除时按照上面的情况1去进行删除。
但是还有一种特殊情况，那就是cur.right就是最小结点，此时preTarget==cur，即preTarget.right == target，这时删除时要将 preTarget.right = target.right。
方案2：找到cur左子树中最大的元素target，然后将该元素的值覆盖到cur处（可以理解为交换），此时等价于删除target处的结点，即该结点的父结点为preTarget。
因为target为cur左子树最大的一个结点，所以target.right == null，此时preTarget.right == target，所以删除时按照上面的情况2去进行删除。
但是还有一种特殊情况，那就是cur.left就是左子树最大结点，此时preTarget==cur，即preTarget.left == target，这时删除时要将 preTarget.left = target.left。
参考实现代码：
public void remove(int key) {
Node cur = root;
Node parent = null;
while (cur != null) {
if(cur.val == key) {
//这里开始删除
removeNode(cur,parent);
break;
}else if(cur.val < key) {
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
}
removeNode方法（方案1）：
public void removeNode(Node cur,Node parent) {
if(cur.left == null) {
if(cur == root) {
root = cur.right;
}else if(cur == parent.left) {
parent.left = cur.right;
}else {
parent.right = 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 {
Node preTarget = cur ;
Node target = cur.right;
while (target.left != null) {
preTarget = target;
target = target.left;
}
cur.val = target.val;
if (target == preTarget.left) {
preTarget.left = target.right;
} else {
preTarget.right = target.right;
}
}
}
removeNode方法（方案2）：
public void removeNode(Node cur,Node parent) {
if(cur.left == null) {
if(cur == root) {
root = cur.right;
}else if(cur == parent.left) {
parent.left = cur.right;
}else {
parent.right = 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 {
Node preTarget = cur ;
Node target = cur.left;
while (target.right != null) {
preTarget = target;
target = target.right;
}
cur.val = target.val;
if (target == preTarget.left) {
preTarget.left = target.left;
} else {
preTarget.right = target.left;
}
}
}
2.4修改
搜索树的修改可以基于删除和插入，先删除目标元素，然后再插入修改元素。
参考实现代码：
public void set(int key, int val) {
remove(key);
insert(val);
}
3.二叉搜索树的性能
在平衡二叉树的情况下（左右子树高度差不超过1），假设有n个结点，此时时间复杂度为二叉树的高度，即 O ( l o g 2 n ) O(log_2n) O(log2n)，但是这只是例行情况，最不理想的情况就是二叉树化为单分支树，时间复杂为 O ( n ) O(n) O(n)。
为了解决这个问题，后面引申出AVL树，红黑树，其中TreeMap与TreeSet的底层就是红黑树。具体红黑树是什么，这里就不多说了。
本文到底了，你学会了吗？
来源：https://weijianhuawen.blog.csdn.net/article/details/123044815
0
投稿猜你喜欢
通常在一份Excel文档中可能包含多个内容不同的工作表，而他们的默认名都为Sheet1、Sheet2、Sheet3等。为了方便我们的查找和操- 程序如下: public static string 英汉(string english,翻译结果 一个或多个) { string 英汉辞典
- 前言最近在看王清培前辈的.NET框架设计时,当中有提到扩展方法 .开头的一句话是:扩展方法是让我们在不改变类原有代码的情况下动态地添加方法的
- 1、打开代码管理器2、打开后就可以看到如下图所示3、复制粘贴该路径，转到该文件夹下新加一个txt文件，把下面的文本复制粘贴<?xml
- 写作原因：跨进程通信的实现和理解是Android进阶中重要的一环。下面博主分享IPC一些相关知识、操作及自己在学习IPC过程中的一些理解。这
- maven的配置文件settings.xml存在于两个地方：1.安装的地方：${M2_HOME}/conf/settings.xml2.用户
- 要说this和super就不得不说Java的封装和继承了，首先说封装，这是一种思想，算不上一种技术，核心思想就是将对象的同一行为和状态看成是
- 前言MyBatis中也提供了注解式开发⽅式，采⽤注解可以减少Sql映射⽂件的配置。 当然，使⽤注解式开发的话，sql语句是写在java程序中
- 一、前言在java中，异常机制是非常有用的构成部分，异常信息对于查找错误来说是必不可少至关重要的信息，因此我们希望在发生错误的时候先看到捕捉
- seata的部署和集成1.部署Seata的tc-server1)下载首先我们要下载seata-server包，地址在http/seata.i
- 对象持久化是指将内存中的对象保存到可永久保存的存储设备中（如磁盘）的一种技术。本文介绍的是除数据库之外的几种对象持久化方式。具体如下：保存成
- 在java中，可以根据Class类的对象，知道某个类（接口）的一些属性（成员 ，方法，注释，注解）等。由于最近的工作中用到了这些，其中需要在
- 比如要获取打开摄像头的应用程序名称，只需要在frameworks/base/core/android/hardware/Camera.jav
- 本文实例讲述了C语言实现的猴子分桃问题算法。分享给大家供大家参考，具体如下：问题:海滩上有一堆桃子，五只猴子来分。第一只猴子把这堆桃子凭据分
- 用户提出一个需求：当修改产品价格的时候，需要记录操作日志，什么时候做了什么事情。想必这个案例，只要是做过应用系统的小伙伴们，都应该遇到过吧？
- android:id 为控件指定相应的ID android:text 指定控件的文本，置尽量使用strings.xml android:gr
- kafka是什么？Kafka是由Apache软件基金会开发的一个开源流处理平台，由Scala和Java编写。Kafka是一种高吞吐量的分布式
- JAVA基础八股文Switch能支持哪些类型？jdk5之前，switch能够作用在byte，short，char，int（实际上都是提升为i
- 项目需要从其他网站获取数据，因为是临时加的需求，在开始项目时没想到需要多数据源于是百度了一下，发现只需要改动一下Spring 的applic
- 学会了Paint，Canvas的基本用法之后，我们就可以动手开始实践了，先写个简单的图片加载进度条看看。按照惯例，先看效果图，再决定要不要往
