詳解Java集合中的基本數(shù)據(jù)結(jié)構(gòu)
集合中三大數(shù)據(jù)結(jié)構(gòu)
數(shù)組
- 內(nèi)存地址連續(xù)
- 可以通過下標(biāo)的成員訪問,下標(biāo)訪問的性能高
- 增刪操作有較大的性能消耗(需要動態(tài)擴(kuò)容)
鏈表(雙向鏈表)
- 靈活的空間要求,存儲空間不要求連續(xù)
- 不支持下標(biāo)訪問,支持順序遍歷搜索
- 針對增刪操作找到對應(yīng)的節(jié)點(diǎn)改變鏈表的頭尾指針指向即可,無需移動元數(shù)據(jù)存儲位置
樹(Java中二叉樹特性)
- 某節(jié)點(diǎn)的左子樹節(jié)點(diǎn)僅包含小于該節(jié)點(diǎn)的值
- 某節(jié)點(diǎn)的右子樹節(jié)點(diǎn)僅包含大于該節(jié)點(diǎn)的值
- 節(jié)點(diǎn)必須是二叉樹
- 順序排列
存在問題:樹可以認(rèn)為是介于數(shù)組和鏈表二者之間的一種數(shù)據(jù)結(jié)構(gòu),擁有較快的查詢速度同時擁有較快的插入和刪除速度。但是在樹出現(xiàn)極端或嚴(yán)重的不平衡情況下會導(dǎo)致效率低下
基于紅黑樹折中解決二叉樹不平衡帶來的效率低下問題
紅黑樹
- 紅黑樹,Red-Black Tree [RBT]是一個自平衡(不是絕對平衡)的二叉查找樹(BST),樹上的每個節(jié)點(diǎn)需要遵循下面的規(guī)則
- 每個節(jié)點(diǎn)要么是黑色,要么是紅色
- 根節(jié)點(diǎn)為黑色
- 每個葉子節(jié)點(diǎn)(NIL)是黑色
- 不能存在兩個連續(xù)的紅色節(jié)點(diǎn)(紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)必須是黑色)
- 任一節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑包含相同數(shù)量的黑節(jié)點(diǎn)
紅黑樹通過什么自平衡
左旋:以某個節(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)節(jié)點(diǎn)),其右子節(jié)點(diǎn)變?yōu)樾D(zhuǎn)節(jié)點(diǎn)的父節(jié)點(diǎn),右子節(jié)點(diǎn)的左節(jié)點(diǎn)變?yōu)樾D(zhuǎn)節(jié)點(diǎn)的右子節(jié)點(diǎn),左子節(jié)點(diǎn)保持不變
右旋:以某個節(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)節(jié)點(diǎn)),其左子節(jié)點(diǎn)變?yōu)樾D(zhuǎn)節(jié)點(diǎn)的父節(jié)點(diǎn),左子節(jié)點(diǎn)的右子節(jié)點(diǎn)變?yōu)樾D(zhuǎn)節(jié)點(diǎn)的左子節(jié)點(diǎn),右子節(jié)點(diǎn)保持不變
變色:節(jié)點(diǎn)的顏色由紅色變?yōu)楹谏蛘吆谏優(yōu)榧t色
紅黑樹插入場景
1、紅黑樹為空
1.1 插入節(jié)點(diǎn)作為根節(jié)點(diǎn)并把節(jié)點(diǎn)設(shè)置為黑色
2、插入節(jié)點(diǎn)的父節(jié)點(diǎn)為黑節(jié)點(diǎn)\
2.1 直接插入
3、插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅節(jié)點(diǎn)
3.1 叔叔節(jié)點(diǎn)存在且為紅節(jié)點(diǎn)
- 1、P節(jié)點(diǎn)和S節(jié)點(diǎn)設(shè)置為黑色
- 2、PP節(jié)點(diǎn)設(shè)置為紅色
- 3、PP設(shè)置為當(dāng)前插入節(jié)點(diǎn)
- 4、再次重復(fù)上述步驟
3.2 叔叔節(jié)點(diǎn)不存在或者叔叔節(jié)點(diǎn)為黑色
3.2.1 P節(jié)點(diǎn)是PP節(jié)點(diǎn)的左節(jié)點(diǎn)
3.2.1.1 插入節(jié)點(diǎn)是P節(jié)點(diǎn)的左節(jié)點(diǎn)
- 1、P設(shè)置為黑色
- 2、PP節(jié)點(diǎn)設(shè)置為紅色
- 3、PP節(jié)點(diǎn)右旋
3.2.1.2 插入節(jié)點(diǎn)是P節(jié)點(diǎn)的右節(jié)點(diǎn)
- 1、P節(jié)點(diǎn)左旋
- 2、把P設(shè)置為插入節(jié)點(diǎn)(此時等于上面的場景)
- 3、PP節(jié)點(diǎn)右旋
3.2.2 P節(jié)點(diǎn)是PP節(jié)點(diǎn)的右節(jié)點(diǎn)
3.2.2.1 插入節(jié)點(diǎn)是P節(jié)點(diǎn)的右節(jié)點(diǎn)
- 1、P節(jié)點(diǎn)設(shè)置為黑色
- 2、PP節(jié)點(diǎn)設(shè)置為紅色
- 3、PP節(jié)點(diǎn)左旋
3.2.2.2 插入節(jié)點(diǎn)是P節(jié)點(diǎn)的左節(jié)點(diǎn)
- 1、P節(jié)點(diǎn)右旋
- 2、將P設(shè)置為插入節(jié)點(diǎn)(此時等于上面場景)
- 3、PP節(jié)點(diǎn)左旋
PP節(jié)點(diǎn)左旋
3.2.2.2 插入節(jié)點(diǎn)是P節(jié)點(diǎn)的左節(jié)點(diǎn)
- 1、P節(jié)點(diǎn)右旋
- 2、將P設(shè)置為插入節(jié)點(diǎn)(此時等于上面場景)
- 3、PP節(jié)點(diǎn)左旋
到此這篇關(guān)于詳解Java集合中的基本數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)Java數(shù)據(jù)結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringBoot深入分析運(yùn)行原理與功能實(shí)現(xiàn)
我們發(fā)現(xiàn)springBoot程序開發(fā)比spring程序編寫起來容易的多。配置簡潔,依賴關(guān)系簡單,啟動運(yùn)行容易。那么結(jié)下了我們我們就要思考一下入門程序中的這些功能是怎么實(shí)現(xiàn)的2022-09-09Java 中的vector和list的區(qū)別和使用實(shí)例詳解
在大家還沒有了解vector,list,deque的知識之前,我先給大家介紹下stl,本文重點(diǎn)給大家介紹vector和list的區(qū)別及使用,感興趣的的朋友一起看看吧2017-09-09RequestContextHolder.getRequestAttributes()空指針問題及解決
這篇文章主要介紹了RequestContextHolder.getRequestAttributes()空指針問題及解決,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01java實(shí)現(xiàn)的滿天星效果實(shí)例
這篇文章主要介紹了java實(shí)現(xiàn)滿天星效果的方法,涉及Java繪圖的應(yīng)用,非常具有實(shí)用價值,需要的朋友可以參考下2014-11-11Java客戶端服務(wù)端上傳接收文件實(shí)現(xiàn)詳解
這篇文章主要介紹了Java客戶端服務(wù)端上傳接收文件實(shí)現(xiàn)詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-07-07SpringBoot集成elasticsearch使用圖文詳解
Spring Boot集成Elasticsearch其實(shí)非常簡單,這篇文章主要給大家介紹了關(guān)于SpringBoot集成elasticsearch使用的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-04-04