`

TreeeMap的底层实现

阅读更多
treeMap插入元素的图解法:
插入前:




插入过程:
1



2



3





4





5




6




代码分析(转)


public V put(K key, V value) 
 { 
    // 先以 t 保存链表的 root 节点
    Entry<K,V> t = root; 
    // 如果 t==null,表明是一个空链表,即该 TreeMap 里没有任何 Entry 
    if (t == null) 
    { 
        // 将新的 key-value 创建一个 Entry,并将该 Entry 作为 root 
        root = new Entry<K,V>(key, value, null); 
        // 设置该 Map 集合的 size 为 1,代表包含一个 Entry 
        size = 1; 
        // 记录修改次数为 1 
        modCount++; 
        return null; 
    } 
    int cmp; 
    Entry<K,V> parent; 
    Comparator<? super K> cpr = comparator; 
    // 如果比较器 cpr 不为 null,即表明采用定制排序
    if (cpr != null) 
    { 
        do { 
            // 使用 parent 上次循环后的 t 所引用的 Entry 
            parent = t; 
            // 拿新插入 key 和 t 的 key 进行比较
            cmp = cpr.compare(key, t.key); 
            // 如果新插入的 key 小于 t 的 key,t 等于 t 的左边节点
            if (cmp < 0) 
                t = t.left; 
            // 如果新插入的 key 大于 t 的 key,t 等于 t 的右边节点
            else if (cmp > 0) 
                t = t.right; 
            // 如果两个 key 相等,新的 value 覆盖原有的 value,
            // 并返回原有的 value 
            else 
                return t.setValue(value); 
        } while (t != null); 
    } 
    else 
    { 
        if (key == null) 
            throw new NullPointerException(); 
        Comparable<? super K> k = (Comparable<? super K>) key; 
        do { 
            // 使用 parent 上次循环后的 t 所引用的 Entry 
            parent = t; 
            // 拿新插入 key 和 t 的 key 进行比较
            cmp = k.compareTo(t.key); 
            // 如果新插入的 key 小于 t 的 key,t 等于 t 的左边节点
            if (cmp < 0) 
                t = t.left; 
            // 如果新插入的 key 大于 t 的 key,t 等于 t 的右边节点
            else if (cmp > 0) 
                t = t.right; 
            // 如果两个 key 相等,新的 value 覆盖原有的 value,
            // 并返回原有的 value 
            else 
                return t.setValue(value); 
        } while (t != null); 
    } 
    // 将新插入的节点作为 parent 节点的子节点
    Entry<K,V> e = new Entry<K,V>(key, value, parent); 
    // 如果新插入 key 小于 parent 的 key,则 e 作为 parent 的左子节点
    if (cmp < 0) 
        parent.left = e; 
    // 如果新插入 key 小于 parent 的 key,则 e 作为 parent 的右子节点
    else 
        parent.right = e; 
    // 修复红黑树
    fixAfterInsertion(e);                               // ①
    size++; 
    modCount++; 
    return null; 
 } 


排序二叉树:
删除节点元素的时候,需要考虑的因素就比较多了比如删除一个节点后,得考虑这个节点是否有子节点,有几个子节点等等。

一般分为如下几个情况处理。

1):被删除的节点是叶子节点,没关系,不会影响大局,直接删除即可

2):被删节点只有左子树或者只有右子树,被删除的节点只有单子树的。直接将被删节点的子树赋给被删节点的父节点即可,也就是说被删节点的左子树代替被删节点成为被删结点父亲的左子树,而被删节点的右子树代替被删节点成为被删结点父亲的右子树。

3):被删节点既有左子树又有右字数,这种是比较麻烦的,也就是当不当、正不正只删除中间的节点。这个时候就要用被删节点最大左子树的节点或者用最小右子树的的节点代替被删节点。

添加节点:添加节点的过程实际上就是构建排序二叉树的过程。原理如下

1):首先有一个根节点

2):以根节点作为当前节点开始检索

3):新增节点和当前节点进行值比较

4):如果新节点比当前节点大,那么当前节点的右子节点作为新的当前节点,如果当前节点比当前节点小,那么当前节点的左子节点作为新的当前节点。

5):重复3和4步骤直到当前节点没有了子节点,那么新节点作为当前节点的子节点,具体作为左子节点还是有子节点得看新节点的值和当前节点值得比较。

treeMap删除节点的代码分析:
private void deleteEntry(Entry<K,V> p) 
 { 
    modCount++; 
    size--; 
    // 如果被删除节点的左子树、右子树都不为空
    if (p.left != null && p.right != null) 
    { 
        // 用 p 节点的中序后继节点代替 p 节点
        Entry<K,V> s = successor (p); 
        p.key = s.key; 
        p.value = s.value; 
        p = s; 
    } 
    // 如果 p 节点的左节点存在,replacement 代表左节点;否则代表右节点。
    Entry<K,V> replacement = (p.left != null ? p.left : p.right); 
    if (replacement != null) 
    { 
        replacement.parent = p.parent; 
        // 如果 p 没有父节点,则 replacemment 变成父节点
        if (p.parent == null) 
            root = replacement; 
        // 如果 p 节点是其父节点的左子节点
        else if (p == p.parent.left) 
            p.parent.left  = replacement; 
        // 如果 p 节点是其父节点的右子节点
        else 
            p.parent.right = replacement; 
        p.left = p.right = p.parent = null; 
        // 修复红黑树
        if (p.color == BLACK) 
            fixAfterDeletion(replacement);       // ①
    } 
    // 如果 p 节点没有父节点
    else if (p.parent == null) 
    { 
        root = null; 
    } 
    else 
    { 
        if (p.color == BLACK) 
            // 修复红黑树
            fixAfterDeletion(p);                 // ②
        if (p.parent != null) 
        { 
            // 如果 p 是其父节点的左子节点
            if (p == p.parent.left) 
                p.parent.left = null; 
            // 如果 p 是其父节点的右子节点
            else if (p == p.parent.right) 
                p.parent.right = null; 
            p.parent = null; 
        } 
    } 
 } 

  • 大小: 12.3 KB
  • 大小: 14.4 KB
  • 大小: 14.9 KB
  • 大小: 15.7 KB
  • 大小: 15.7 KB
  • 大小: 16.4 KB
  • 大小: 14 KB
分享到:
评论

相关推荐

    毕业设计物联网实战项目基于Eclipse Theia开源框架开发的物联网在线编程IDE.zip

    【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    Android毕设实战项目基于Android的医院挂号系统.zip

    【项目资源】: 适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    (源码)基于Python的KMeans和EM算法结合图像分割项目.zip

    # 基于Python的KMeans和EM算法结合图像分割项目 ## 项目简介 本项目结合KMeans聚类和EM(期望最大化)算法,实现对马赛克图像的精准分割。通过Gabor滤波器提取图像的多维特征,并利用KMeans进行初步聚类,随后使用EM算法优化聚类结果,最终生成高质量的分割图像。 ## 项目的主要特性和功能 1. 图像导入和预处理: 支持导入马赛克图像,并进行灰度化、滤波等预处理操作。 2. 特征提取: 使用Gabor滤波器提取图像的多维特征向量。 3. 聚类分析: 使用KMeans算法对图像进行初步聚类。 利用KMeans的聚类中心初始化EM算法,进一步优化聚类结果。 4. 图像生成和比较: 生成分割后的图像,并与原始图像进行比较,评估分割效果。 5. 数值比较: 通过计算特征向量之间的余弦相似度,量化分割效果的提升。 ## 安装使用步骤 ### 假设用户已经下载了项目的源码文件 1. 环境准备:

    HCIP第一次作业:静态路由综合实验

    HCIP第一次作业:静态路由综合实验

    毕设单片机实战项目基于stm32、esp8266和Android的智能家居系统-设备端.zip

    【项目资源】: 单片机项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    统计学基于Python的Johnson-SU分布参数计算与优化:数据拟合及弹性网络参数优化方法实现(复现论文或解答问题,含详细可运行代码及解释)

    内容概要:本文详细介绍了Johnson-SU分布的参数计算与优化过程,涵盖位置参数γ、形状参数δ、尺度参数ξ和伸缩参数λ的计算方法,并实现了相应的Python代码。文中首先导入必要的库并设置随机种子以确保结果的可复现性。接着,分别定义了四个参数的计算函数,其中位置参数γ通过加权平均值计算,形状参数δ基于局部均值和标准差的比值,尺度参数ξ结合峰度和绝对偏差,伸缩参数λ依据偏态系数。此外,还实现了Johnson-SU分布的概率密度函数(PDF),并使用负对数似然函数作为目标函数,采用L-BFGS-B算法进行参数优化。最后,通过弹性网络的贝叶斯优化展示了另一种参数优化方法。; 适合人群:具有Python编程基础,对统计学和机器学习有一定了解的研究人员或工程师。; 使用场景及目标:①需要对复杂数据分布进行建模和拟合的场景;②希望通过优化算法提升模型性能的研究项目;③学习如何实现和应用先进的统计分布及优化技术。; 阅读建议:由于涉及较多数学公式和编程实现,建议读者在阅读时结合相关数学知识,同时动手实践代码,以便更好地理解和掌握Johnson-SU分布及其优化方法。

    TSP问题的3种智能优化方法求解(研究生课程《智能优化算法》结课大作业).zip

    TSP问题的3种智能优化方法求解(研究生课程《智能优化算法》结课大作业).zip

    毕业设计物联网实战项目基于Rtthread和MQTT搭建的物联网网关.zip

    【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    基于STM32F103C8T6的温湿度传感器(HAL库版),通过串口向电脑端反馈数据(附通过ESP8266-01s模块连接WIFI上传云平台的资料代码-固件库版本).zip

    【项目资源】: 单片机项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    自动发布Java项目(Tomcat)Shell脚本

    自动发布Java项目(Tomcat)Shell脚本

    (源码)基于webpack和Vue的前端项目构建方案.zip

    # 基于webpack和Vue的前端项目构建方案 ## 项目简介 本项目是基于webpack和Vue构建的前端项目方案,借助webpack强大的打包能力以及Vue的开发特性,可用于快速搭建现代化的前端应用。项目不仅完成了基本的webpack与Vue的集成配置,还在构建速度优化和代码规范性方面做了诸多配置。 ## 项目的主要特性和功能 1. 打包功能运用webpack进行模块打包,支持将scss转换为css,借助babel实现语法转换。 2. Vue开发支持集成Vue框架,能使用Vue单文件组件的开发模式。 3. 构建优化采用threadloader实现多进程打包,cacheloader缓存资源,极大提高构建速度开启热更新功能,开发更高效。 4. 错误处理与优化提供不同环境下的错误映射配置,便于定位错误利用webpackbundleanalyzer分析打包体积。

    Hands-On Large Language Models - Jay Alammar 袋鼠书 《动手学大语言模型》

    Hands-On Large Language Models - Jay Alammar 袋鼠书 《动手学大语言模型》PDF

    《基于YOLOv8的舞蹈动作分析系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    (源码)基于Arduino Feather M0和Raspberry Pi的传感器数据采集与监控系统.zip

    # 基于Arduino Feather M0和Raspberry Pi的传感器数据采集与监控系统 ## 项目简介 本项目是一个基于Arduino Feather M0和Raspberry Pi的传感器数据采集与监控系统。系统通过Arduino Feather M0采集传感器数据,并通过WiFi将数据传输到Raspberry Pi。Raspberry Pi运行BalenaOS,集成了MySQL、PHP、NGINX、Apache和Grafana等工具,用于数据的存储、处理和可视化。项目适用于环境监测、物联网设备监控等场景。 ## 项目的主要特性和功能 1. 传感器数据采集使用Arduino Feather M0和AM2315传感器采集温度和湿度数据。 2. WiFi数据传输Arduino Feather M0通过WiFi将采集到的数据传输到Raspberry Pi。

    《基于YOLOv8的音响设备识别系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    Android毕设实战项目这是一个android 图书管理系统.zip

    【项目资源】: 适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    毕业设计物联网实战项目基于智龙2.0开发板和窄带物联网模块BC95。操作系统为RTT2.1。.zip

    【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    (源码)基于Arduino的WiFi按钮项目.zip

    # 基于Arduino的WiFi按钮项目 ## 一、项目简介 本项目是一个基于ESP8266芯片的Arduino项目,主要实现WiFi连接、电压检测、LED灯控制以及向服务器发送POST请求等功能。通过简单的按钮操作,可以实现与服务器通信并获取相关信息,同时能检测电池电压并提示用户。 ## 二、项目的主要特性和功能 1. WiFi连接项目能够自动连接到指定的WiFi网络。 2. 电压检测通过ADC(模数转换器)检测电池电压,并在电压低于阈值时发出警告。 3. LED灯控制通过控制LED灯的亮灭来提示用户不同的状态信息(如连接成功、电压低等)。 4. 服务器通信项目可以向指定的服务器发送POST请求并处理返回的HTTP响应。 ## 三、安装使用步骤 1. 环境准备确保已安装Arduino IDE和ESP8266插件。 2. 下载源码下载项目的源码文件并解压。 3. 打开项目在Arduino IDE中打开解压后的main.cpp文件。

    scipy-0.10.1-cp26-cp26mu-manylinux1_x86_64.whl

    该资源为scipy-0.10.1-cp26-cp26mu-manylinux1_x86_64.whl,欢迎下载使用哦!

    计算机毕业设计;计算机毕设;Java毕业设计;小程序毕业设计

    计算机毕业设计;计算机毕设;Java毕业设计;小程序毕业设计;企业、旅游、党建、学校、人事、酒店、民宿、预约、考试、外卖、点餐、外贸、宠物、图书、销售、商城、就业、助农、仓储、交易、美食、博客、婚庆、二手、养老、医院、医疗、药品、招聘、考勤、宿舍、物流、租赁、公益等

Global site tag (gtag.js) - Google Analytics