数据结构之二叉搜索树(TreeSetTreeMap)

目录

一.搜索树

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. 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  3. 它的左右子树也分别为二叉搜索树

注意:二叉搜索树中的节点不可重复出现

例子:下图中,这棵二叉树显然满足上面的性质,这是棵二叉搜索树。

不是二叉搜索树的: 

 

1.2适用场景

二叉搜索树有着高效的插入、搜索、删除操作

 2.二叉搜索树的基本操作

二叉搜索树有以下基本操作:

  1. 查找(search):在搜索树中查找特定的节点。
  2. 插入(insert):在树中找到满足搜索树性质的位置插入新的节点
  3. 删除(detele):从树中删除指定的节点
  4. 遍历(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基本思路
  1. 判断二叉搜索树是否为空,若为空,返回false
  2. 遍历二叉搜索树,判断键值(key)和根节点值的大小,若根节点大于key进入左子树小于key,进入右子树,若刚好等于根节点的值,则返回true
  3. 重复上述操作,当遍历完二叉树,没有找到,返回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;
    }

对于二叉搜索树的查找操作,其时间复杂度:

  1. 在最好情况下(刚好是根节点):O(1)
  2. 在最坏情况下(所有节点只有左节点或者只有右子节点):O(n)
  3. 平均复杂度:O(logn) (n是树中的节点数量,在每次比较后,搜索空间都会减半)

2.3插入

2.3.1基本思路
  1. 在插入前需要判断二叉搜索树是否为空,若为空,则将以key为值的节点作为根节点,并返回true。
  2. 若前面条件满足,那么就需要进行判断,判断的条件与查找操作基本相同。当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;
    }

对于插入操作,其时间复杂度:

  1. 在最好情况下:O(logn)
  2. 最坏情况下:O(n)
  3. 平均时间复杂度:O(logn)

2.4删除

2.4.1基本思路

对于想要删除的位置的节点,我们需要考虑三种情况:(假设想要删除节点为key,其父节点为parent)

  1. 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的键值对,有两种模型:

  1. 纯key模型:

例如:有个英语词典,查找某个单词是否在词典中出现

           在微信的好友中,查找某个人的名字,是否存在

  1. 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)

 注意:

  1. Set是继承自Collection的一个接口类
  2. 唯一性:Set中值存储key,并且要求key一定要唯一
  3. 有序性:在向TreeSet中添加元素时,会根据元素的自然顺序(如果元素实现了Comparable接口)或提供的Comparator来确定该元素在树中的位置。
  4. TreeSet的底层是使用Mao实现的,其使用key与Obiect的一个默认对象作为键值插入到Map中的
  5. Set的最大功能就是对集合中的元素进行去重
  6. Set中的key不能修改,若要修改,只能将原来的删除,再重新进行插入
  7. TreeSet中不能插入null的key,HashSet可以
  8. 实现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());
    }
}

注意

  1. Map是一个接口,不能直接实现化对象,如果要实例化对象只能实例化其实现类TreeMap或者HashMap
  2. Map中存放键值对的Key是唯一的,value值可以重复
  3. 在TreeMap中插入键值对时,Key不能为空,否则就会抛出空指针异常,value可以为空。但HashMap的key和value都可以为空。
  4. Map中的key可以全部分离出来,存储到Set中来进行访问(因为Key不重复)
  5. Map中的value可以全部分离出来,存储在Collextion的任何一个子类集合中(value可能有重复)
  6. Map中键值对的Key不能直接修改,value可以修改,如果要修改key,只能先将该key删除掉,然后再来进行 重新插入

 总结:

  1. TreeSet是一种有序的、可排序的集合类。TreeSet底层使用红黑树数据结构实现,能够快速进行插入、删除和查找操作,且能保证元素的有序性。我们可以使用无参构造函数或带有Comparator参数的构造函数创建TreeSet对象,并使用相关方法进行添加、删除和查找操作。
  2. TreeMap是一种基于红黑树实现的有序映射表,它可以按照key的自然顺序或者自定义顺序进行排序,并具有查找和排序的功能,保证所有操作的时间复杂度为O(logn),但TreeMap的占用内存较大,插入和删除操作可能需要调整红黑树,会消耗较多的时间和资源。

以上就是本章所有内容,若有不足欢迎各位大佬指正~😄

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/673115.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C语言笔记第9篇:字符函数和字符串函数

在编程的过程中&#xff0c;我们经常要处理字符和字符串&#xff0c;为了方便操作字符和字符串&#xff0c;C语言标准库中提供了一系列库函数&#xff0c;接下来我们就学习一下这些函数。 一、字符函数 1、字符分类函数 C语言中有一系列的函数是专门做字符分类的&#xff0c;…

MyBatis一、MyBatis简介

MyBatis一、MyBatis简介 MyBatis 简介MyBatis 定义MyBatis 历史MyBatis 特性1. 灵活性和易用性2. 性能优化3. 易于集成4. 支持多种数据库5. 插件机制6. 其他特性 MyBatis 下载和其他持久化层技术对比 MyBatis 简介 MyBatis 定义 MyBatis 是一个优秀的持久层框架&#xff0c;它…

240602-通过命令行实现HuggingFace文件上传

A. 登录显示 A.1 MacOS A.2 Windows B. 操作步骤 B.1 操作细节 要通过命令行将文件上传到 Hugging Face&#xff0c;可以使用 huggingface-cli 工具。以下是详细步骤&#xff1a; 安装 huggingface_hub 包&#xff1a; 首先&#xff0c;确保已经安装了 huggingface_hub 包。可…

MySQL—函数—数值函数(基础)

一、引言 首先了解一下常见的数值函数哪些&#xff1f;并且直到它们的作用&#xff0c;并且演示这些函数的使用。 二、数值函数 常见的数值函数如下&#xff1a; 注意&#xff1a; 1、ceil(x)、floor(x) &#xff1a;向上、向下取整。 2、mod(x,y)&#xff1a;模运算&#x…

Wpf 使用 Prism 开发MyToDo应用程序

MyToDo 是使用 WPF &#xff0c;并且塔配Prism 框架进行开发的项目。项目中进行了前后端分离设计&#xff0c;客户端所有的数据均通过API接口获取。适合新手入门学习WPF以及Prism 框架使用。 首页统计以及点击导航到相关模块功能待办事项增删改查功能备忘录增删改查功能登录注册…

跨模型知识融合:大语言模型的知识融合

大语言模型&#xff08;LLMs&#xff09;在多个领域的应用日益广泛&#xff0c;但确保它们的行为与人类价值观和意图一致却充满挑战。传统对齐方法&#xff0c;例如基于人类反馈的强化学习&#xff08;RLHF&#xff09;&#xff0c;虽取得一定进展&#xff0c;仍面临诸多难题&a…

7-18 对象关系映射(orm_name)---PTA实验C++

一、题目描述 一开始看到对象关系映射&#xff0c;其实我是拒绝的。这三个词凑一块&#xff0c;能是给C初学者的题吗&#xff1f; 再仔细读需求&#xff0c;才发现在课设项目已经用过这功能。Object Relational Mapping&#xff08;ORM&#xff09;就是面向对象&#xff08;O…

大降分!重邮计算机专硕复试线大降50分!重庆邮电计算机考研考情分析!

重庆邮电大学&#xff08;Chongqing University of Posts and Telecommunications&#xff09;简称重邮&#xff0c;坐落于中国重庆市主城区南山风景区内&#xff0c;是中华人民共和国工业和信息化部与重庆市人民政府共建的教学研究型大学&#xff0c;入选国家“中西部高校基础…

【30天精通Prometheus:一站式监控实战指南】第13天:graphite_exporter从入门到实战:安装、配置详解与生产环境搭建指南,超详细

亲爱的读者们&#x1f44b;   欢迎加入【30天精通Prometheus】专栏&#xff01;&#x1f4da; 在这里&#xff0c;我们将探索Prometheus的强大功能&#xff0c;并将其应用于实际监控中。这个专栏都将为你提供宝贵的实战经验。&#x1f680;   Prometheus是云原生和DevOps的…

企业im即时通讯WorkPlus私有化部署适配国产信创环境

在信息化时代&#xff0c;高效的沟通和协作对于企业的运营至关重要。企业IM即时通讯平台提供了一种便捷、实时的沟通工具&#xff0c;旨在改善企业的内部和外部沟通效率。然而&#xff0c;随着企业对数据安全性和隐私保护的要求不断提高&#xff0c;许多企业开始选择私有化部署…

【Qt知识】disconnect

在Qt框架中&#xff0c;disconnect函数用于断开信号与槽之间的连接。当不再需要某个信号触发特定槽函数时&#xff0c;或者为了防止内存泄漏和重复执行问题&#xff0c;你可以使用disconnect来取消这种关联。disconnect函数的基本用法可以根据不同的需求采用多种形式&#xff0…

【ORB_SLAM系列3】—— 如何在Ubuntu18.04中使用自己的单目摄像头运行ORB_SLAM3(亲测有效,踩坑记录)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、ORB_SLAM3源码编译二、ORB_SLAM3实时单目相机测试1. 查看摄像头的话题2. 运行测试 三. 运行测试可能的报错1. 报错一(1) 问题描述(2) 原因分析(3) 解决 2. …

Windows下如何把Oracle从C盘整体迁移到D盘?

&#xff08;一&#xff09;写这篇文章的起因 这篇文章适合刚接触的技术小白follow操作&#xff0c;整理文章不易&#xff0c;大家多多点赞转发 起因是昨天有会员在群里发问&#xff0c;客户要把Oracle整个目录从C盘挪到D盘怎么弄 客户那边的人把Oracle整个程序数据文件都安装…

使用 Kali Linux 实现 Smurf 攻击

一、介绍 Smurf攻击是一种分布式拒绝服务&#xff08;DDoS&#xff09;攻击&#xff0c;利用IP协议中的ICMP&#xff08;Internet Control Message Protocol&#xff09;请求和网络的广播特性&#xff0c;使目标系统被大量ICMP回复包淹没&#xff0c;从而导致系统无法正常提供…

ZDH-数据管理模块

目录 主题 项目源码 预览地址 安装包下载地址 数据管理服务 数据资源管理 数据资源权限 数据资源血缘 总结 感谢支持 主题 本篇文章主要介绍ZDH-数据管理服务及应用场景 项目源码 zdh_web: GitHub - zhaoyachao/zdh_web: 大数据采集,抽取平台 预览地址 后台管理…

【C++】类和对象——构造和析构函数

目录 前言类的六个默认构造函数构造函数1.构造函数的概念2.构造函数的特性 初始化列表1.构造函数整体赋值2.初始化列表 析构函数1.析构函数的概念2.析构函数的特性 前言 类和对象相关博客&#xff1a;【C】类和对象   我们前面一个内容已经讲了关于类好对象的初步的一些知识&…

绿联 安装MariaDB数据库用于Seatable服务

绿联 安装MariaDB数据库用于Seatable服务 1、镜像 mariadb:latest 2、安装 2.1、基础设置 重启策略&#xff1a;容器退出时总是重启容器。 2.2、网络 网络选择桥接(bridge)。 2.3、存储空间 装载路径/var/lib/mysql不可变更。 2.4、端口设置 容器端口3306&#xff0c;本…

7. MySQL 视图、索引

文章目录 【 1. 视图 View 】1.1 视图原理1.2 创建视图 CREATE VIEW1.2.1 创建基于单表的视图1.2.2 创建基于多表的视图 1.3 查看视图1.3.1 查看视图的内容1.3.2 查看视图的详细信息 1.4 修改视图 ALTER VIEW1.4.1 修改视图内容1.4.2 修改视图名称 1.5 删除视图 DORP VIEW 【 2…

Ansys Mechanical|组装 External Mechanical Model

Assembling Finite Element Models 上文中介绍了如何导入外部模型并将其组合到单个模型中的示例。 如果要将外部模型与Workbench环境中已有的一个或多个模型组合在一起&#xff0c;该如何操作&#xff1f;本文将介绍这个工作流程。 Ansys Mechanical支持Mechanical Model和Ex…