上一篇 <<<ConcurrentHashMap在JDK1.8版本比1.7改進(jìn)了什么
下一篇 >>>基于LinkedHashMap手寫(xiě)LRU淘汰策略
二叉樹(shù)特點(diǎn)
1晋被、以第一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)，所有小于根節(jié)點(diǎn)的數(shù)據(jù)放置在左邊蹦浦，所有大于等于根節(jié)點(diǎn)的數(shù)據(jù)放置在右邊
2正驻、所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)
3畜埋、時(shí)間復(fù)雜度：2x=n>x=log2n=logn谦屑，查找效率：20億個(gè)點(diǎn) 也就是查詢231=21
缺點(diǎn)：
不平衡 和時(shí)間插入的順序有關(guān)系流妻，如果插入第一個(gè)是為0的情況下蛹屿，最后成為了一條線。時(shí)間復(fù)雜度其實(shí)就是為樹(shù)的深度放钦，也就是變?yōu)镺(n)
tips:數(shù)據(jù)結(jié)構(gòu)連接可訪問(wèn)https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
紅黑樹(shù)與二叉搜索樹(shù)的實(shí)現(xiàn)的區(qū)別
二叉搜索樹(shù)是簡(jiǎn)單的二叉樹(shù)色徘，小于根節(jié)點(diǎn)的在左子樹(shù)恭金，大于根節(jié)點(diǎn)的在右子樹(shù)操禀，不會(huì)自動(dòng)調(diào)整二叉樹(shù)的層級(jí)，容易出現(xiàn)鏈表形式横腿，導(dǎo)致查詢效率低下颓屑。
紅黑樹(shù)屬于平衡二叉樹(shù)的子集斤寂，具有顏色，通過(guò)變色揪惦、左旋遍搞、右旋等方式調(diào)整二叉樹(shù)的層級(jí)平衡，大大提高查詢效率器腋。
紅黑樹(shù)基本特征
1溪猿、每個(gè)節(jié)點(diǎn)的顏色不是紅色就是黑色
2、根節(jié)點(diǎn)一定為黑色
3纫塌、新增節(jié)點(diǎn)默認(rèn)顏色為紅色
4诊县、不允許兩個(gè)紅色節(jié)點(diǎn)連在一起
5、每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都必須是黑色
自我修復(fù)方式：【變色措左、左旋依痊、右旋】
相關(guān)文章鏈接：
<<<Java集合類圖總覽
<<<ArrayList的添加和刪除操作實(shí)現(xiàn)原理圖解
<<<ArrayList的動(dòng)態(tài)擴(kuò)容、ModCount及fail-fast原理
<<<LinkedList增刪改查操作底層實(shí)現(xiàn)原理
<<<數(shù)組拷貝的幾種方式及和鏈表結(jié)構(gòu)的對(duì)比
<<<Jdk1.7HashMap源碼分析
<<<Jdk1.7HashMap如何擴(kuò)容及解決死循環(huán)問(wèn)題
<<<JDK1.8HashMap源碼分析
<<<ConcurrentHashMap在JDK1.8版本比1.7改進(jìn)了什么
<<<基于LinkedHashMap手寫(xiě)LRU淘汰策略
<<<HashSet集合底層實(shí)現(xiàn)原理
<<<HashTable底層實(shí)現(xiàn)原理及和ConcurrentHashMap區(qū)別
<<<java集合常見(jiàn)面試題
