「紅黑樹」意味着什麼：TreeSet將其元素存儲在紅黑樹中，並根據元素的值對元素進行排序;

Question

我在讀Java Tutorial Oracle，我遇到了下面的聲明。

TreeSet將其元素存儲在紅黑樹中，並根據元素的值排列其元素 ;

我被「紅黑樹」這個詞混淆了，我做了一個基本的網頁搜索，沒有找到滿意的答案。

Answer 1

紅黑樹是一種自平衡二叉搜索樹。有幾種自平衡樹，如2-3棵樹，AA樹，AVL樹和紅黑樹。

當您考慮可能存在非自平衡二叉搜索樹的最壞情況時，自平衡樹的目的很明顯。

考慮這種情況：首先在空樹中插入一個整數（非自平衡）。繼續插入每個大於前一個值的整數。您最差的演員檢索時間將是插入時間複雜度爲O（n）的最後一個元素。這是因爲你必須遍歷整個樹才能到達期望的元素，就像鏈表一樣。

這比時間複雜度爲O（lg n）的平衡二叉搜索樹要糟得多。因此，有一些方法，如紅黑樹，試圖確保樹是平衡的（意味着每個孩子的體重是相同的）。

Answer 2

對我來說第三個搜索結果是https://en.wikipedia.org/wiki/Red%E2%80%93black_tree，這很好地解釋了這個概念。

基本上它是一種保持二叉樹幾乎平衡的方法，因此獨立於插入順序，它不退化爲鏈表，同時保持插入（和移除）成本低。

Answer 3

1）每個節點都有紅色或黑色的顏色，而樹的根總是黑色的。

2）沒有兩個相鄰的紅色節點（紅色節點不能有紅色父母或紅色孩子，紅色需要黑色父母）。

3）從根節點到NIL節點的每條路徑具有相同數量的黑色節點。