集合中三大數(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)文章希望大家以后多多支持腳本之家！

最新評論