欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

詳解Java集合中的基本數(shù)據(jù)結(jié)構(gòu)

 更新時間:2021年06月04日 11:33:21   作者:Liziba  
總有小伙伴讓我總結(jié)一下Java集合中的基本數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識,今天特地整理了本篇文章,文中有非常詳細(xì)的介紹,需要的朋友可以參考下

集合中三大數(shù)據(jù)結(jié)構(gòu)

在這里插入圖片描述

數(shù)組

  • 內(nèi)存地址連續(xù)
  • 可以通過下標(biāo)的成員訪問,下標(biāo)訪問的性能高
  • 增刪操作有較大的性能消耗(需要動態(tài)擴(kuò)容)

在這里插入圖片描述

鏈表(雙向鏈表)

  • 靈活的空間要求,存儲空間不要求連續(xù)
  • 不支持下標(biāo)訪問,支持順序遍歷搜索
  • 針對增刪操作找到對應(yīng)的節(jié)點改變鏈表的頭尾指針指向即可,無需移動元數(shù)據(jù)存儲位置

在這里插入圖片描述

樹(Java中二叉樹特性)

  • 某節(jié)點的左子樹節(jié)點僅包含小于該節(jié)點的值
  • 某節(jié)點的右子樹節(jié)點僅包含大于該節(jié)點的值
  • 節(jié)點必須是二叉樹
  • 順序排列

在這里插入圖片描述

存在問題:樹可以認(rèn)為是介于數(shù)組和鏈表二者之間的一種數(shù)據(jù)結(jié)構(gòu),擁有較快的查詢速度同時擁有較快的插入和刪除速度。但是在樹出現(xiàn)極端或嚴(yán)重的不平衡情況下會導(dǎo)致效率低下

在這里插入圖片描述

基于紅黑樹折中解決二叉樹不平衡帶來的效率低下問題

紅黑樹

  • 紅黑樹,Red-Black Tree [RBT]是一個自平衡(不是絕對平衡)的二叉查找樹(BST),樹上的每個節(jié)點需要遵循下面的規(guī)則
  • 每個節(jié)點要么是黑色,要么是紅色
  • 根節(jié)點為黑色
  • 每個葉子節(jié)點(NIL)是黑色
  • 不能存在兩個連續(xù)的紅色節(jié)點(紅色節(jié)點的兩個子節(jié)點必須是黑色)
  • 任一節(jié)點到葉子節(jié)點的路徑包含相同數(shù)量的黑節(jié)點

在這里插入圖片描述

紅黑樹通過什么自平衡

左旋:以某個節(jié)點作為支點(旋轉(zhuǎn)節(jié)點),其右子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的父節(jié)點,右子節(jié)點的左節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的右子節(jié)點,左子節(jié)點保持不變

在這里插入圖片描述

右旋:以某個節(jié)點作為支點(旋轉(zhuǎn)節(jié)點),其左子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的父節(jié)點,左子節(jié)點的右子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的左子節(jié)點,右子節(jié)點保持不變

在這里插入圖片描述

變色:節(jié)點的顏色由紅色變?yōu)楹谏蛘吆谏優(yōu)榧t色

在這里插入圖片描述

紅黑樹插入場景

1、紅黑樹為空

1.1 插入節(jié)點作為根節(jié)點并把節(jié)點設(shè)置為黑色

2、插入節(jié)點的父節(jié)點為黑節(jié)點\

2.1 直接插入

3、插入節(jié)點的父節(jié)點為紅節(jié)點

3.1 叔叔節(jié)點存在且為紅節(jié)點

  • 1、P節(jié)點和S節(jié)點設(shè)置為黑色
  • 2、PP節(jié)點設(shè)置為紅色
  • 3、PP設(shè)置為當(dāng)前插入節(jié)點
  • 4、再次重復(fù)上述步驟

3.2 叔叔節(jié)點不存在或者叔叔節(jié)點為黑色

3.2.1 P節(jié)點是PP節(jié)點的左節(jié)點

3.2.1.1 插入節(jié)點是P節(jié)點的左節(jié)點

  • 1、P設(shè)置為黑色
  • 2、PP節(jié)點設(shè)置為紅色
  • 3、PP節(jié)點右旋

3.2.1.2 插入節(jié)點是P節(jié)點的右節(jié)點

  • 1、P節(jié)點左旋
  • 2、把P設(shè)置為插入節(jié)點(此時等于上面的場景)
  • 3、PP節(jié)點右旋

3.2.2 P節(jié)點是PP節(jié)點的右節(jié)點

3.2.2.1 插入節(jié)點是P節(jié)點的右節(jié)點

  • 1、P節(jié)點設(shè)置為黑色
  • 2、PP節(jié)點設(shè)置為紅色
  • 3、PP節(jié)點左旋

3.2.2.2 插入節(jié)點是P節(jié)點的左節(jié)點

  • 1、P節(jié)點右旋
  • 2、將P設(shè)置為插入節(jié)點(此時等于上面場景)
  • 3、PP節(jié)點左旋

PP節(jié)點左旋

3.2.2.2 插入節(jié)點是P節(jié)點的左節(jié)點

  • ​ 1、P節(jié)點右旋
  • ​ 2、將P設(shè)置為插入節(jié)點(此時等于上面場景)
  • ​ 3、PP節(jié)點左旋

在這里插入圖片描述

到此這篇關(guān)于詳解Java集合中的基本數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)Java數(shù)據(jù)結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • SpringBoot深入分析運行原理與功能實現(xiàn)

    SpringBoot深入分析運行原理與功能實現(xiàn)

    我們發(fā)現(xiàn)springBoot程序開發(fā)比spring程序編寫起來容易的多。配置簡潔,依賴關(guān)系簡單,啟動運行容易。那么結(jié)下了我們我們就要思考一下入門程序中的這些功能是怎么實現(xiàn)的
    2022-09-09
  • JAVA 多線程編程之CountDownLatch使用詳解

    JAVA 多線程編程之CountDownLatch使用詳解

    當(dāng)多個線程需要協(xié)調(diào)和同步執(zhí)行任務(wù)時,Java中的CountDownLatch(倒計時門閂)是一個常用的工具類,本文將介紹 CountDownLatch 的基本原理、用法以及示例代碼,需要的朋友可以參考下
    2023-05-05
  • Java 中的vector和list的區(qū)別和使用實例詳解

    Java 中的vector和list的區(qū)別和使用實例詳解

    在大家還沒有了解vector,list,deque的知識之前,我先給大家介紹下stl,本文重點給大家介紹vector和list的區(qū)別及使用,感興趣的的朋友一起看看吧
    2017-09-09
  • Java StringBuilder的用法示例

    Java StringBuilder的用法示例

    這篇文章主要給大家介紹了關(guān)于Java StringBuilder用法的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-01-01
  • RequestContextHolder.getRequestAttributes()空指針問題及解決

    RequestContextHolder.getRequestAttributes()空指針問題及解決

    這篇文章主要介紹了RequestContextHolder.getRequestAttributes()空指針問題及解決,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-01-01
  • java實現(xiàn)的滿天星效果實例

    java實現(xiàn)的滿天星效果實例

    這篇文章主要介紹了java實現(xiàn)滿天星效果的方法,涉及Java繪圖的應(yīng)用,非常具有實用價值,需要的朋友可以參考下
    2014-11-11
  • Java客戶端服務(wù)端上傳接收文件實現(xiàn)詳解

    Java客戶端服務(wù)端上傳接收文件實現(xiàn)詳解

    這篇文章主要介紹了Java客戶端服務(wù)端上傳接收文件實現(xiàn)詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-07-07
  • struts2中類型轉(zhuǎn)換實例代碼

    struts2中類型轉(zhuǎn)換實例代碼

    這篇文章主要介紹了struts2中類型轉(zhuǎn)換實例代碼,具有一定參考價值,需要的朋友可以了解下。
    2017-10-10
  • Java 面試題和答案 - (下)

    Java 面試題和答案 - (下)

    本文主要介紹Java 面試題,這里整理了Java面試題關(guān)于JDBC,線程異常處理,Servlet,JSP的知識的整理,幫助大家理解知識點,便于面試,有興趣的小伙伴可以參考下
    2016-09-09
  • SpringBoot集成elasticsearch使用圖文詳解

    SpringBoot集成elasticsearch使用圖文詳解

    Spring Boot集成Elasticsearch其實非常簡單,這篇文章主要給大家介紹了關(guān)于SpringBoot集成elasticsearch使用的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2023-04-04

最新評論