集合中三大數據結構

數組

• 內存地址連續(xù)
• 可以通過下標的成員訪問，下標訪問的性能高
• 增刪操作有較大的性能消耗（需要動態(tài)擴容）

鏈表（雙向鏈表）

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

樹（Java中二叉樹特性）

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

存在問題：樹可以認為是介于數組和鏈表二者之間的一種數據結構，擁有較快的查詢速度同時擁有較快的插入和刪除速度。但是在樹出現極端或嚴重的不平衡情況下會導致效率低下

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

紅黑樹

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

紅黑樹通過什么自平衡

左旋：以某個節(jié)點作為支點（旋轉節(jié)點），其右子節(jié)點變?yōu)樾D節(jié)點的父節(jié)點，右子節(jié)點的左節(jié)點變?yōu)樾D節(jié)點的右子節(jié)點，左子節(jié)點保持不變

右旋：以某個節(jié)點作為支點（旋轉節(jié)點），其左子節(jié)點變?yōu)樾D節(jié)點的父節(jié)點，左子節(jié)點的右子節(jié)點變?yōu)樾D節(jié)點的左子節(jié)點，右子節(jié)點保持不變

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

紅黑樹插入場景

1、紅黑樹為空

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

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

2.1 直接插入

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

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

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

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

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

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

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

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

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

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

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

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

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

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

PP節(jié)點左旋

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

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

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

最新評論