首先我們來看下紅黑樹的結(jié)構(gòu)，如圖：

（學(xué)習(xí)視頻分享：java教學(xué)視頻）

紅黑樹的結(jié)構(gòu)特點(diǎn)：

立即學(xué)習(xí)“Java免費(fèi)學(xué)習(xí)筆記（深入）”；

（1）每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。
（2）根節(jié)點(diǎn)是黑色。
（3）每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。 [注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！]
（4）如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
（5）從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

為什么要要用紅黑樹？

1、首先紅黑樹是不符合AVL樹的平衡條件的，即每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度最多差1的二叉查找樹。但是提出了為節(jié)點(diǎn)增加顏色，紅黑樹是用非嚴(yán)格的平衡來換取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低，任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決，而AVL是嚴(yán)格平衡樹，因此在增加或者刪除節(jié)點(diǎn)的時(shí)候，根據(jù)不同情況，旋轉(zhuǎn)的次數(shù)比紅黑樹要多。所以紅黑樹的插入效率更高

（更多相關(guān)面試題推薦：java面試題及答案）

2、紅黑樹能夠以O(shè)(log2 (n)) 的時(shí)間復(fù)雜度進(jìn)行搜索、插入、刪除操作

3、簡單來說紅黑樹就是為了解決二叉查找樹的缺陷，因?yàn)槎娌檎覙湓谀承┣闆r下會(huì)退化成一個(gè)線性結(jié)構(gòu)。

紅黑樹和平衡樹的對比和選擇

1、平衡樹結(jié)構(gòu)更加直觀，讀取性能比紅黑樹要高；增加和刪除節(jié)點(diǎn) 恢復(fù)平衡的性能不如紅黑樹
2、紅黑樹，讀取性能不如平衡樹；增加和刪除節(jié)點(diǎn) 恢復(fù)平衡性能比平衡樹好

紅黑樹的使用場景：

TreeMap、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹。

相關(guān)推薦：java入門教程

以上就是java面試——紅黑樹的詳細(xì)內(nèi)容，更多請關(guān)注php中文網(wǎng)其它相關(guān)文章！