紅黑樹如何工作？

Question

關於紅黑樹有很多問題，但他們都沒有回答他們如何工作。爲什麼叫做紅黑色？這如何保持樹平衡（從而提高不平衡的普通二叉搜索樹的性能）？我只是在尋找如何和爲什麼它的作品的概述。

Answer 1

對於搜索和遍歷，它與任何二叉樹相同。

對於插入和刪除操作，應用了更復雜的算法，旨在確保樹不會太不平衡。這些保證了所有的單項操作總是在最差的O（log n）時間運行，而在一個簡單的二叉樹中，二叉樹可能變得非常不平衡以至於它實際上是一個鏈表，給出了O（n）最壞情況下的性能每個單項操作。

紅黑樹的基本思想是模仿一個B樹，每個節點最多3個密鑰和4個孩子。 B樹（或諸如B +樹之類的變體）主要用於數據庫索引和存儲在硬盤上的數據。

每個二叉樹節點都有一個「顏色」 - 紅色或黑色。在B樹類比中，每個黑色節點是適合該B樹節點的子樹的子樹根。如果此節點具有紅色子節點，則它們也被視爲同一個B樹節點的一部分。所以有可能（雖然在實踐中沒有這樣做）將紅黑樹轉換爲B樹並返回，並保留（大部分）結構。唯一可能的原因是，當一個B樹節點有兩個鍵和三個子節點時，你可以選擇在同等紅黑樹中的黑節點中選擇哪個鍵。

例如，對於紅黑樹，從根到葉的每條線具有相同數量的黑節點。該規則是從所有葉節點處於相同深度的B樹規則導出的。

儘管這是導出紅黑樹的基本思想，但在實踐中用於插入和刪除的算法被修改爲強制執行所有B樹規則（可能有一個小例外 - 我忘記了）更新，但是爲二叉樹形式量身定製。這意味着做一個紅黑樹插入或刪除可能會給出一個不同於你期望的與做B樹插入或刪除比較的結果。

有關更多詳細信息，請按照MigDus已提供的Wikipedia link。

Answer 2

紅黑樹是一個有序的二叉樹，其中每個頂點都是紅色或黑色。 直覺是紅色頂點應該被看作與其父母處於同一高度（即紅色頂點的邊緣被認爲是「水平」而不是「下降」）。

[我不相信維基百科條目說明了這一點清楚了。]

爲紅黑樹通常的規則要求一個紅色的頂點永遠指向另一個紅色頂點。這意味着對於以黑色頂點爲根的任何子樹（bbb，bbr，rbb，rbr - 對於[左邊的子] [root] [右邊的子]），可能的頂點排列對應於234棵樹。

搜索紅黑樹就像搜索普通的二叉樹一樣。插入和刪除是相似的，除了可能需要在某個點進行「修正」旋轉以保留紅黑不變。

乾杯！