java面試——紅黑樹

首先我們來看下紅黑樹的結構，如圖：

（學習影片分享：java教學影片）

紅黑樹的結構特徵：

（1）每個節點或是黑色，或是紅色。
（2）根節點是黑色。
（3）每個葉子節點（NIL）是黑色。 [註：這裡葉節點，是指為空(NIL或NULL)的葉子節點！ ]
（4）如果一個節點是紅色的，則它的子節點必須是黑色的。
（5）從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

為什麼要用紅黑樹？

1、首先紅黑樹是不符合AVL樹的平衡條件的，即每個節點的左子樹和右子樹的高度最多差1的二叉查找樹。但提出了為節點增加顏色，紅黑樹是用非嚴格的平衡來換取增刪節點時候旋轉次數的降低，任何不平衡都會在三次旋轉之內解決，而AVL是嚴格平衡樹，因此在增加或刪除節點的時候，依不同情況，旋轉的次數比紅黑樹多。所以紅黑樹的插入效率更高

（更多相關面試題推薦：java面試題及答案）

2、紅黑樹能夠以O( log2 (n)) 的時間複雜度進行搜尋、插入、刪除操作

3、簡單來說紅黑樹就是為了解決二元查找樹的缺陷，因為二元查找樹在某些情況下會退化成一個線性結構。

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

1、平衡樹結構更直觀，讀取效能比紅黑樹高；增加和刪除節點恢復平衡的效能不如紅黑樹
2、紅黑樹，讀取效能不如平衡樹；增加和刪除節點恢復平衡效能比平衡樹好

紅黑樹的使用場景：

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

相關推薦：java入門教學

以上是java面試——紅黑樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！