詳解Java集合中的基本數據結構
集合中三大數據結構
數組
- 內存地址連續
- 可以通過下標的成員訪問，下標訪問的性能高
- 增刪操作有較大的性能消耗（需要動態擴容）
鏈表（雙向鏈表）
- 靈活的空間要求，存儲空間不要求連續
- 不支持下標訪問，支持順序遍歷搜索
- 針對增刪操作找到對應的節點改變鏈表的頭尾指針指向即可，無需移動元數據存儲位置
樹（Java中二叉樹特性）
- 某節點的左子樹節點僅包含小於該節點的值
- 某節點的右子樹節點僅包含大於該節點的值
- 節點必須是二叉樹
- 順序排列
存在問題：樹可以認為是介於數組和鏈表二者之間的一種數據結構，擁有較快的查詢速度同時擁有較快的插入和刪除速度。但是在樹出現極端或嚴重的不平衡情況下會導致效率低下
基於紅黑樹折中解決二叉樹不平衡帶來的效率低下問題
紅黑樹
- 紅黑樹，Red-Black Tree [RBT]是一個自平衡（不是絕對平衡）的二叉查找樹（BST）,樹上的每個節點需要遵循下面的規則
- 每個節點要麼是黑色，要麼是紅色
- 根節點為黑色
- 每個葉子節點(NIL)是黑色
- 不能存在兩個連續的紅色節點（紅色節點的兩個子節點必須是黑色）
- 任一節點到葉子節點的路徑包含相同數量的黑節點
紅黑樹通過什麼自平衡
左旋：以某個節點作為支點（旋轉節點），其右子節點變為旋轉節點的父節點，右子節點的左節點變為旋轉節點的右子節點，左子節點保持不變
右旋：以某個節點作為支點（旋轉節點），其左子節點變為旋轉節點的父節點，左子節點的右子節點變為旋轉節點的左子節點，右子節點保持不變
變色：節點的顏色由紅色變為黑色或者黑色變為紅色
紅黑樹插入場景
1、紅黑樹為空
1.1 插入節點作為根節點並把節點設置為黑色
2、插入節點的父節點為黑節點\
2.1 直接插入
3、插入節點的父節點為紅節點
3.1 叔叔節點存在且為紅節點
- 1、P節點和S節點設置為黑色
- 2、PP節點設置為紅色
- 3、PP設置為當前插入節點
- 4、再次重復上述步驟
3.2 叔叔節點不存在或者叔叔節點為黑色
3.2.1 P節點是PP節點的左節點
3.2.1.1 插入節點是P節點的左節點
- 1、P設置為黑色
- 2、PP節點設置為紅色
- 3、PP節點右旋
3.2.1.2 插入節點是P節點的右節點
- 1、P節點左旋
- 2、把P設置為插入節點（此時等於上面的場景）
- 3、PP節點右旋
3.2.2 P節點是PP節點的右節點
3.2.2.1 插入節點是P節點的右節點
- 1、P節點設置為黑色
- 2、PP節點設置為紅色
- 3、PP節點左旋
3.2.2.2 插入節點是P節點的左節點
- 1、P節點右旋
- 2、將P設置為插入節點（此時等於上面場景）
- 3、PP節點左旋
PP節點左旋
3.2.2.2 插入節點是P節點的左節點
- 1、P節點右旋
- 2、將P設置為插入節點（此時等於上面場景）
- 3、PP節點左旋
到此這篇關於詳解Java集合中的基本數據結構的文章就介紹到這瞭,更多相關Java數據結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！