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

數(shù)組

• 內(nèi)存地址連續(xù)
• 可以通過(guò)下標(biāo)的成員訪(fǎng)問(wèn)，下標(biāo)訪(fǎng)問(wèn)的性能高
• 增刪操作有較大的性能消耗（需要?jiǎng)討B(tài)擴(kuò)容）

鏈表（雙向鏈表）

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

樹(shù)（Java中二叉樹(shù)特性）

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

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

基于紅黑樹(shù)折中解決二叉樹(shù)不平衡帶來(lái)的效率低下問(wèn)題

紅黑樹(shù)

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

紅黑樹(shù)通過(guò)什么自平衡

左旋：以某個(gè)節(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)保持不變

右旋：以某個(gè)節(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色

紅黑樹(shù)插入場(chǎng)景

1、紅黑樹(shù)為空

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)（此時(shí)等于上面的場(chǎng)景）
• 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)（此時(shí)等于上面場(chǎng)景）
• 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)（此時(shí)等于上面場(chǎng)景）
• ​ 3、PP節(jié)點(diǎn)左旋

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

最新評(píng)論