複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/紅黑樹/2413209
複製
複製成功

紅黑樹

鎖定
紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。 [1] 
紅黑樹是在1972年由Rudolf Bayer發明的，當時被稱為平衡二叉B樹（symmetric binary B-trees）。後來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的“紅黑樹”。 [2] 
紅黑樹是一種特化的AVL樹（平衡二叉樹），都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。 [2] 
它雖然是複雜的，但它的最壞情況運行時間也是非常良好的，並且在實踐中是高效的： 它可以在O(log n)時間內做查找，插入和刪除，這裏的n 是樹中元素的數目。 [2] 
中文名
紅黑樹
外文名
RED-BLACK-TREE
別    名
對稱二叉B樹
性    質
平衡二叉查找樹 [3] 
用    途
實現關聯數組 [1] 
發明人
魯道夫·貝爾
發明時間
1972年
學    科
計算機

目錄

  1. 1 簡介
  2. 2 特徵
  3. 3 樹的旋轉
  4. ▪ 1.結點插入算法
  5. ▪ 2.結點刪除算法
  1. 4 操作
  2. 5 用途
  3. ▪ 1.Linux非實時任務調度中的應用
  4. ▪ 2.Linux虛擬內存中的應用
  1. ▪ 3.檢測樹的平衡性上的應用
  2. 6 數據結構簡述

紅黑樹簡介

紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。 [4] 
紅黑樹是一種平衡二叉查找樹的變體，它的左右子樹高差有可能大於 1，所以紅黑樹不是嚴格意義上的平衡二叉樹（AVL），但 對之進行平衡的代價較低， 其平均統計性能要強於 AVL 。 [2] 
由於每一棵紅黑樹都是一顆二叉排序樹，因此，在對紅黑樹進行查找時，可以採用運用於普通二叉排序樹上的查找算法，在查找過程中不需要顏色信息。 [5] 

紅黑樹特徵

紅黑樹是每個結點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。 [3]  在二叉查找樹強制一般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求:
性質1. 結點是紅色或黑色。 [3] 
性質2. 根結點是黑色。 [3] 
性質3. 所有葉子都是黑色。（葉子是NIL結點） [3] 
性質4. 每個紅色結點的兩個子結點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的紅色結點）
性質5. 從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點。 [3] 
這些約束強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二叉查找樹。 [3] 
是性質4導致路徑上不能有兩個連續的紅色結點確保了這個結果。最短的可能路徑都是黑色結點，最長的可能路徑有交替的紅色和黑色結點。因為根據性質5所有最長的路徑都有相同數目的黑色結點，這就表明了沒有路徑能多於任何其他路徑的兩倍長。 [3] 
因為紅黑樹是一種特化的二叉查找樹，所以紅黑樹上的只讀操作與普通二叉查找樹相同。 [2] 

紅黑樹樹的旋轉

樹的左旋
樹的左旋(2張)
當我們在對紅黑樹進行插入和刪除等操作時，對樹做了修改，那麼可能會違背紅黑樹的性質。
為了保持紅黑樹的性質，我們可以對相關結點做一系列的調整，通過對樹進行旋轉（例如左旋和右旋操作），即修改樹中某些結點的顏色及指針結構，以達到對紅黑樹進行插入、刪除結點等操作時，紅黑樹依然能保持它特有的性質（五點性質）。 [3] 
如右圖。

紅黑樹1.結點插入算法

插入過程首先是根據一般二叉查找樹的插入步驟， 把新結點 插入到 某個葉結點的位置上，然後將 z 着 為紅色。 為了保證紅黑樹的性質能繼續保 持，再對有關結點重點着色並旋轉，其插入算法如下： [2] 
RB-INSERT (T,z) {
1 按二叉查找樹的插入步驟將結點 z 插入到 T 中；
2 color[z]=RED；
3 while(z 不是根結點 &&color[z->parent]= =RED) {Insert-Fixup(T,z);}
4 color[root[T]]=BLACK； } [2] 
對上述算法分析，如果新插入的是黑色結點，那麼它所在的路徑上就多出一個黑色的結點，所以新插入的結點一定要設成紅 色。 但是如果 z 的父結點也是紅色，這就違反了每個紅色結點的兩個子結點都黑色的性質。 [2] 

紅黑樹2.結點刪除算法

與紅黑樹的的插入算法一樣，對一個結點的刪除算法要花 O(log n)時間，只是刪 除算法略微複雜些，刪除算法如下： [2] 
RB-DELETE(T,z) {
1 if (z 的左右子結點均為 NIL)
2 { NIL 結點代替 z 的位置； delete(z); }
3 else if (z 有一個子結點為 NIL)
4 {z 的非 NIL 子結點代替 z 的位置；delete(z); }
5 else
6 {將紅黑樹中序遍歷中 z 的後繼結點 s 的值賦給 z; delete(s); }
7 if (刪除的結點是黑色的) Delete-Fixup(T,x); /*x 指向代替刪除結點的結點 */ } [2] 
對以上算法分析，若刪除的結點是紅色，則不做任何操作，紅黑樹的任何屬性都不會被破壞；若刪除的結點是黑色的，顯然它所 在的路徑上就少一個黑色結點，紅黑樹的性質就被破壞了，這時執行一個 Delete-Fixup（）來修補這棵樹。 一個結點被刪除之後，一定 有一個它的結點代替了它的位置，即使是葉結點被刪除後，也會有一個空結點來代替它的位置。 設指針 x 指向這個代替位置的結點，同時引入指向 x 兄弟的指針 w，這裏均假設 x 是 x->parent 的左子結點，則 w 是 x->parent 的右子結點，如果實際遇到相反的情 況，只要把所有操作中的左、右 互反一下就可以了。
（圖一圖二如下）
圖2 Delete-Fixup（T,x）修補過程示意圖 圖2 Delete-Fixup（T,x）修補過程示意圖
圖1 Insert-Fixup(T,z)修補過程示意圖 圖1 Insert-Fixup(T,z)修補過程示意圖

紅黑樹操作

在紅黑樹上只讀操作不需要對用於二叉查找樹的操作做出修改，因為它也是二叉查找樹。但是，在插入和刪除之後，紅黑屬性可能變得違規。恢復紅黑屬性需要少量(O(log n))的顏色變更（這在實踐中是非常快速的）並且不超過三次樹旋轉（對於插入是兩次）。這允許插入和刪除保持為 O（log n)）次，但是它導致了非常複雜的操作。 [3] 

紅黑樹用途

紅黑樹1.Linux非實時任務調度中的應用

Linux 的穩定內核版本在 2． 6． 24 之後，使用了新的調度程序 CFS，所有非實時可運行進程都以虛擬運行時間為 key 值掛在一棵紅黑樹上，以完成更公平高效地調度所有任務。CFS 棄用 active /expired 數組和動態計算優先級，不再跟蹤任務的睡眠時間和區別是否交互任務，並且在調度中採用基於時間計算鍵值的紅黑樹來選取下一個任務，根據所有任務佔用 CPU 時間的狀態來確定調度任務優先級。 [3] 

紅黑樹2.Linux虛擬內存中的應用

32 位 Linux 內核虛擬地址空間劃分 0 － 3G 為用户空間，3 － 4G 為內核空間，因此每個進程可以使用 4GB的虛擬空間。同時，Linux 定義了虛擬存儲區域( VMA) 以便於更好表示進程所使用的虛擬空間，每個 VMA是某個進程的一段連續虛擬空間，其中的單元具有相同的特徵，所有的虛擬區域按照地址排序由指針鏈接為一個鏈表。當發生缺頁中斷時搜索 VMA 到指定區域時，則需要頻繁操作，因此選用了紅黑樹以減少查找時間。 [3] 

紅黑樹3.檢測樹的平衡性上的應用

紅黑樹是一種自平衡二叉搜索樹，它的每個結點都被“着色”為紅色或者黑色，這些結點的顏色被用來檢測樹的平衡性。紅黑樹作為嵌入式數據庫中的索引機制，可以獲得更好的性能，對於SQLite數據庫，可以採用紅黑樹實現索引機制的優化。 [6] 

紅黑樹數據結構簡述

紅黑樹 紅黑樹
它的統計性能要好於平衡二叉樹（有些書籍根據作者姓名，Adelson-Velskii和Landis，將其稱為AVL-樹），因此，紅黑樹在很多地方都有應用。目前，基於擁有上述特性，紅黑樹已廣泛應用Linux 的進程管理、內存管理，設備驅動及虛擬內存跟蹤等一系列場景中。 [3]  其他平衡樹還有：AVL，SBT，伸展樹，TREAP等等。
參考資料