目录
一.搜索树
1.1概念
1.2适用场景
2.二叉搜索树的基本操作
2.1二叉搜索树的定义
2.2查找
2.1.1基本思路
2.3插入
2.3.1基本思路
2.4删除
2.4.1基本思路
2.5遍历
2.6性能分析
二.TreeSet
Map和Set
1.概念
2.模型
1.定义
2.基本操作
三.TreeMap
1.定义
2.基本操作
总结:
一.搜索树
1.1概念
二叉搜索树又称二叉排序树,它是一棵空树,或者是具有以下性质的二叉树:
- 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
注意:二叉搜索树中的节点不可重复出现
例子:下图中,这棵二叉树显然满足上面的性质,这是棵二叉搜索树。
不是二叉搜索树的:
1.2适用场景
二叉搜索树有着高效的插入、搜索、删除操作
2.二叉搜索树的基本操作
二叉搜索树有以下基本操作:
- 查找(search):在搜索树中查找特定的节点。
- 插入(insert):在树中找到满足搜索树性质的位置插入新的节点
- 删除(detele):从树中删除指定的节点
- 遍历(traverse):二叉搜索树的遍历,有前中后遍历,中序遍历是有序的
2.1二叉搜索树的定义
public class BinarySea {
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int x) {
this.val = x;
}
}
public TreeNode root;//作为二叉搜素树的根节点
}
2.2查找
假设现在已经有了一棵上图中一棵二叉搜索树,如果要在这颗二叉搜索树中查找相应的键值是否存在,如何进行?(假设查找值为key)
2.1.1基本思路
- 判断二叉搜索树是否为空,若为空,返回false
- 遍历二叉搜索树,判断键值(key)和根节点值的大小,若根节点大于key进入左子树;小于key,进入右子树,若刚好等于根节点的值,则返回true
- 重复上述操作,当遍历完二叉树,没有找到,返回false
代码实现:
public boolean search(int key){
//若二叉搜索树为空,返回false
if(root==null){
return false;
}
//不为空,借助变量进行搜索
TreeNode cur=root;
while (cur!=null){
//如果当前节点的值大于key,则向左子树搜索
if(cur.val>key){
cur=cur.left;
}
//如果当前节点的值小于key,则向右子树搜索
else if(cur.val<key){
cur=cur.right;
}
//如果当前节点的值等于key,则返回true
else{
return true;
}
}
//如果搜索结束,没有找到,则返回false
return false;
}
对于二叉搜索树的查找操作,其时间复杂度:
- 在最好情况下(刚好是根节点):O(1)
- 在最坏情况下(所有节点只有左节点或者只有右子节点):O(n)
- 平均复杂度:O(logn) (n是树中的节点数量,在每次比较后,搜索空间都会减半)
2.3插入
2.3.1基本思路
- 在插入前需要判断二叉搜索树是否为空,若为空,则将以key为值的节点作为根节点,并返回true。
- 若前面条件满足,那么就需要进行判断,判断的条件与查找操作基本相同。当cur的值大于key,那么就进入cur的左子树;若cur的值小于key,则进入cur的右子树;若cur的值和key值相等,说明键值已经存在,插入失败,返回false。插入操作,需要借助一个变量prev,来保存每次cur的父节点。(假设cur=root(cur是要进行判断),prev为cur的父节点。)
假设要插入的节点为8:(以上图作基础)
当找到要插入节点的父节点后,需要判断插入节点的值和父节点prev的值大小,很明显,6<8,所以要插入的节点在prev的右子树。
可以得到:
代码实现:
public boolean insert(int key){
if(root==null){//如果二叉搜索树为空,则直接插入
root=new TreeNode(key);
return true;
}
//二叉搜索树不为空,进行插入操作
TreeNode cur=root;
TreeNode prev=null;
while (cur!=null){
if(cur.val>key) {//如果当前节点的值大于key,则向左子树搜索
prev = cur;
cur = cur.left;
} else if (cur.val<key) {//如果当前节点的值小于key,则向右子树搜索
prev = cur;
cur = cur.right;
}else{//如果当前节点的值等于key,则返回false
return false;
}
}
//创建节点
TreeNode node=new TreeNode(key);
//判断节点与prev值的大小关系
if(prev.val>key) {//如果节点值小于prev,则插入到左子树
prev.left = node;
}else {//如果节点值大于prev,则插入到右子树
prev.right = node;
}
return true;
}
对于插入操作,其时间复杂度:
- 在最好情况下:O(logn)
- 最坏情况下:O(n)
- 平均时间复杂度:O(logn)
2.4删除
2.4.1基本思路
对于想要删除的位置的节点,我们需要考虑三种情况:(假设想要删除节点为key,其父节点为parent)
- key.left==null
1.key刚好是root,则root=key.right;
2.key不是root,key是parent.left,那么parent.left=key.right;
3.key不是root,key是parent.right,那么parent.right=key.right.
2.key.right==null
1.key刚好是root,则root=key.left;
2.key不是root,key是parent.left,那么parent.left=key.left;
3.key不是root,key是parent.right,那么parent.right=key.left.
3.key.left!=null&&key.right!=null
1.需要用替换法进行删除,即在它的右子树中寻找中序遍历中的第一个节点(关键值最小的),用它的值填补到被删除节点中,再处理该节点的删除问题。(或者也可以在待删除节点的左子树中寻找中序遍历的最后一个节点,即左子树中的最大值,填补到待删除节点中,再处理删除问题。)
以下图为例:假设要删除的节点是10,先进行查找,找到待删除节点的位置,和其父节点。
找到之后,需要在其左子树找最大值或者右子树中找最小值进行替换。
这里定义变量target=cur.right,targetParent=null(用来保留target的父节点),寻找待删除节点的右子树,让target往左子树走(每次走的时候,targetParent都要保留此时target,再让其往左子树走),当target的左子树为空时,说明此时已经找到右子树中的最小值,将target的值填补到cur,再让targetParent.left=target.left。此时,删除完成。
代码实现:
/**
* 删除二叉搜索树中指定值的节点
* @param key 需要删除的节点值
*/
public void remove(int key){
if(root==null){
// 树为空,无需删除
return;
}
TreeNode cur=root;
TreeNode prev=null;
while(cur!=null){
if(cur.val<key){
// 向右子树搜索
prev=cur;
cur=cur.right;
}else if(cur.val>key){
// 向左子树搜索
prev=cur;
cur=cur.left;
}else{
// 找到需要删除的节点,调用removeNode进行删除
removeNode(prev,cur);
}
}
}
/**
* 实际删除指定节点的操作
* @param parent 被删除节点的父节点
* @param cur 需要删除的节点
*/
public 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 target=cur.right;
TreeNode targetParent=cur;
while(target.left!=null){
targetParent=target;
target=target.left;
}
cur.val=target.val;
if(target==targetParent.left){
targetParent.left=target.right;
}else{
targetParent.right=target.right;
}
}
}
2.5遍历
对于二叉搜索树树的遍历,其遍历与二叉树相同
二叉树
我们以中序遍历为例:
//搜索树的中序遍历
public void inOrder(TreeNode root) {
if(root==null){
return;
}
//遍历左子树
inOrder(root.left);
System.out.print(root.val+" ");
//遍历右子树
inOrder(root.right);
}
2.6性能分析
对于二叉搜索树,在插入和删除操作之前都必须进行查找,查找效率代表了二叉搜索树中的各个操作的性能。
对于有n个节点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是节点在二叉搜索树的深度的函数,即节点越深,则比较次数越多。
对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树,如图:
最优情况下,二叉搜索树为完全二叉树,其平均比较次数为:log2N
最差情况下,二叉搜索树退化为单支树,其平均比较次数为:N/2
二.TreeSet
Map和Set
1.概念
Map和Set是一种专门用来进行搜索的容器或数据结构,其搜索的小了与其具体的实例化子类有关。Map和Set是一种适合动态查找的容器。
2.模型
把搜索的数据称为关键字(key),和关键字对应的称为值(value),将其称为Key—value的键值对,有两种模型:
- 纯key模型:
例如:有个英语词典,查找某个单词是否在词典中出现
在微信的好友中,查找某个人的名字,是否存在
- Key-value模型:
例如:统计一个字符串中,某个字符与其字符串中出现的次数:<字符,出现次数>.
Map中存储的就是key-value的键值对,而Set只存储了key。
1.定义
TreeSet是java集合框架中的一种类,实现了Set接口,提供了一种有序且不允许有重复元素的集合。TreeSet内部实现基于红黑树,这是一种自平衡的二叉查找树,它保证了插入、删除和查找操作的高效性,通常这些操作的时间复杂度为O(log n)。
2.基本操作
测试:
import java.util.Set;
import java.util.TreeSet;
import java.util.Iterator;
public class test {
public static void main(String[] args) {
Set<String> s=new TreeSet<>();
s.add("孙悟空");
s.add("猪八戒");
s.add("唐僧");
//遍历
for(String str:s){
System.out.print(str+" ");
}
System.out.println();
//查找
System.out.println(s.contains("孙悟空"));
//判断有多少个元素
System.out.println(s.size());
//判断集合是否为空
System.out.println(s.isEmpty());
//删除
s.remove("孙悟空");
//利用迭代器
Iterator<String> it=s.iterator();
while(it.hasNext()){
System.out.print(it.next()+" ");
}
}
}
下面是有关Set 的文档
集 (Java Platform SE 8 ) (oracle.com)
注意:
- Set是继承自Collection的一个接口类
- 唯一性:Set中值存储key,并且要求key一定要唯一
- 有序性:在向TreeSet中添加元素时,会根据元素的自然顺序(如果元素实现了Comparable接口)或提供的Comparator来确定该元素在树中的位置。
- TreeSet的底层是使用Mao实现的,其使用key与Obiect的一个默认对象作为键值插入到Map中的
- Set的最大功能就是对集合中的元素进行去重
- Set中的key不能修改,若要修改,只能将原来的删除,再重新进行插入
- TreeSet中不能插入null的key,HashSet可以
- 实现Set接口的常用类有TreeSet和HashSet,还有一个LinkedHashSet,LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序
Set 底层结构 | TreeSet |
底层结构 | 红黑树 |
插入 / 删除 / 查找时间 复杂度 | O(log N) |
是否有序 | 关于 Key 有序 |
线程安全 | 不安全 |
比较与覆写 | key 必须能够比较,否则会抛出 ClassCastException 异常 |
入/删除/查找区别 | 按照红黑树的特性来进行插入和删除 |
应用场景 | 需要 Key 有序场景下 |
三.TreeMap
1.定义
TreeMap是Java集合框架中的一部分,它实现了SortedMap接口,用于存储键值对(Key-Value对),并能按照键的自然顺序或者自定义比较器(Comparator)排序。TreeMap的底层实现是一个红黑树数据结构,这保证了其高效的查找、插入和删除操作,尤其是查找操作的时间复杂度为O(log n)。
2.基本操作
测试:
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class test {
public static void main(String[] args) {
Map<String,String> map=new TreeMap<>();
map.put("齐天大圣","孙悟空");
map.put("天蓬元帅","猪八戒");
map.put("及时雨","宋江");
//打印key对应value
System.out.println(map.values());
//统计元素个数
System.out.println(map.size());
String s=map.get("及时雨");
System.out.println(s);
//删除元素,返回被删除的元素的value
String re=map.remove("及时雨");
System.out.println(re);
//将map中的key给到Set中
Set<String> t=map.keySet();
for (String str:t){
System.out.print(str+" ");
}
System.out.println();
//将map中的key和value给到Set中
Set<Map.Entry<String,String>> entry=map.entrySet();
System.out.println(entry);
for (Map.Entry<String,String> e:entry){
System.out.println(e.getKey()+"-->"+e.getValue());
}
//判断是否为空
System.out.println(map.isEmpty());
}
}
注意:
- Map是一个接口,不能直接实现化对象,如果要实例化对象只能实例化其实现类TreeMap或者HashMap
- Map中存放键值对的Key是唯一的,value值可以重复
- 在TreeMap中插入键值对时,Key不能为空,否则就会抛出空指针异常,value可以为空。但HashMap的key和value都可以为空。
- Map中的key可以全部分离出来,存储到Set中来进行访问(因为Key不重复)
- Map中的value可以全部分离出来,存储在Collextion的任何一个子类集合中(value可能有重复)
- Map中键值对的Key不能直接修改,value可以修改,如果要修改key,只能先将该key删除掉,然后再来进行 重新插入
总结:
- TreeSet是一种有序的、可排序的集合类。TreeSet底层使用红黑树数据结构实现,能够快速进行插入、删除和查找操作,且能保证元素的有序性。我们可以使用无参构造函数或带有Comparator参数的构造函数创建TreeSet对象,并使用相关方法进行添加、删除和查找操作。
- TreeMap是一种基于红黑树实现的有序映射表,它可以按照key的自然顺序或者自定义顺序进行排序,并具有查找和排序的功能,保证所有操作的时间复杂度为O(logn),但TreeMap的占用内存较大,插入和删除操作可能需要调整红黑树,会消耗较多的时间和资源。
以上就是本章所有内容,若有不足欢迎各位大佬指正~😄