上一篇 <<<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) 也就是查詢(xún)231=21
缺點(diǎn)：
不平衡 和時(shí)間插入的順序有關(guān)系，如果插入第一個(gè)是為0的情況下，最后成為了一條線(xiàn)。時(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)致查詢(xún)效率低下。
紅黑樹(shù)屬于平衡二叉樹(shù)的子集，具有顏色，通過(guò)變色、左旋、右旋等方式調(diào)整二叉樹(shù)的層級(jí)平衡，大大提高查詢(xún)效率。
紅黑樹(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集合類(lèi)圖總覽
<<<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)面試題
