動态查找---->紅黑樹（Red-Black Tree）

紅黑樹 （Red-Black Tree）

紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種資料結構，典型的用途是實作關聯數組。它是複雜的，但它的操作有着良好的最壞情況運作時間，并且在實踐中是高效的: 它可以在O(logn)時間内做查找，插入和删除，這裡的n是樹中元素的數目。包含n個内部節點的紅黑樹的高度是 O(log(n))。

一、性質

紅黑樹是每個節點都帶有顔色屬性的二叉查找樹，顔色為紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:

性質1. 節點是紅色或黑色。

性質2. 根是黑色。

性質3. 所有葉子都是黑色（葉子是NIL節點）。

性質4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

性質5. 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。

這些限制強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這個樹大緻上是平衡的。因為操作比如插入、删除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。

要知道為什麼這些特性確定了這個結果，注意到性質4導緻了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。

二、操作

因為每一個紅黑樹也是一個特化的二叉查找樹，是以紅黑樹上的隻讀操作與普通二叉查找樹上的隻讀操作相同。然而，在紅黑樹上進行插入操作和删除操作會導緻不再符合紅黑樹的性質。恢複紅黑樹的屬性需要少量(O(logn))的顔色變更(實際是非常快速的)和不超過三次樹旋轉(對于插入操作是兩次)。雖然插入和删除很複雜，但操作時間仍可以保持為 O(log n) 次。

2.1插入：

2.2删除：