紅黑樹

紅黑樹是一種自平衡二叉查詢樹，是在計算機科學中用到的一種資料結構，典型用途是實現關聯陣列。它在1972年由魯道夫·貝爾發明，被稱為「對稱二叉B樹」，它現代的名字源於Leo J. Guibas和羅伯特·塞奇威克於1978年寫的一篇論文。紅黑樹的結構複雜，但它的操作有著良好的最壞情況執行時間，並且在實踐中高效：它可以在formula_1時間內完成查詢、插入和刪除，這裡的formula_2是樹中元素的數目。歷史.1972年，魯道夫·拜爾發明瞭一種資料結構，那是一個B樹的四階特殊情況。此結構會維持所有從根到樹葉的路徑都具有相同數量的節點，創造了一個完美的平衡樹。然而，他們並不是二元搜尋樹。拜爾在他的論文中稱呼他們為「對稱二元B樹」，後來他們以2-3-4樹或是2-4樹的形式開始流行。在一篇1972年的論文〈A Dichromatic Framework for Balanced Trees〉中，Leonidas J. Guibas 和 Robert Sedgewick從對稱二元B樹工作時用彩色雷射列印機可以產生的最好看的顏色。另一種說法來自Guibas，是因為紅色和黑色的筆是他們當時可用來繪製樹的顏色。用途和好處.紅黑樹和AVL樹一樣都對插入時間、刪除時間和查詢時間提供了最好可能的最壞情況擔保。這不只是使它們在時間敏感的應用，如實時應用中有價值，而且使它們有在提供最壞情況擔保的其他資料結構中作為基礎模板的價值；例如，在計算幾何中使用的很多資料結構都可以基於紅黑樹實現。紅黑樹在函數語言程式設計中也特別有用，在這裡它們是最常用的持久資料結構之一，它們用來構造關聯陣列和集合，每次插入、刪除之後它們能保持為以前的版本。除了formula_1的時間之外，紅黑樹的持久版本對每次插入或刪除需要formula_1的空間。紅黑樹是2-3-4樹的一種等同。換句話說，對於每個2-3-4樹，都存在至少一個數據元素是同樣次序的紅黑樹。在2-3-4樹上的插入和刪除操作也等同於在紅黑樹中顏色翻轉和旋轉。這使得2-3-4樹成為理解紅黑樹背後的邏輯的重要工具，這也是很多介紹演算法的教科書在紅黑樹之前介紹2-3-4樹的原因，儘管2-3-4樹在實踐中不經常使用。紅黑樹相對於AVL樹來說，犧牲了部分平衡性以換取插入和刪除操作時少量的旋轉操作，整體來說效能要優於AVL樹。性質.紅黑樹是每個節點都帶有顏色屬性的二叉查詢樹，顏色為紅色或黑色。在二叉查詢樹強制一般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求：下面是一個具體的紅黑樹的圖例：這些約束確保了紅黑樹的關鍵特性：從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查詢某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二叉查詢樹。要知道為什麼這些性質確保了這個結果，注意到性質4導致了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多於任何其他路徑的兩倍長。在很多樹資料結構的表示中，一個節點有可能只有一個子節點，而葉子節點包含資料。用這種範例表示紅黑樹是可能的，但是這會改變一些性質並使演算法複雜。為此，本文中我們使用「nil葉子」，如上圖所示，它不包含資料而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，導致了這些樹好像同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點，儘管其中的一個或兩個可能是空葉子。操作.因為每一個紅黑樹也是一個特化的二叉查詢樹，因此紅黑樹上的只讀操作與普通二叉查詢樹上的只讀操作相同。然而，在紅黑樹上進行插入操作和刪除操作會導致不再符合紅黑樹的性質。恢復紅黑樹的性質需要少量。雖然插入和刪除很複雜，但操作時間仍可以保持為formula_1次。插入.我們首先以二叉查詢樹的方法增加節點並標記它為紅色。下面要進行什麼操作取決於其他臨近節點的顏色。同人類的家族樹中一樣，我們將使用術語"叔父節點"來指一個節點的父節點的兄弟節點。注意：在下面的示意圖中，將要插入的節點標為N，N的父節點標為P，N的祖父節點標為G，N的叔父節點標為U。在圖中展示的任何顏色要麼是由它所處情形這些所作的假定，要麼是假定所暗含的。對於每一種情形，我們將使用C示例程式碼來展示。透過下列函式，可以找到一個節點的叔父和祖父節點：node* grandparent(node *n){return n-&gt;parent-&gt;parent;node* uncle(node *n){if(n-&gt;parent == grandparent(n)-&gt;left)return grandparent (n)-&gt;right;elsereturn grandparent (n)-&gt;left;情形1:新節點N位於樹的根上，沒有父節點。在這種情形下，我們把它重繪為黑色以滿足性質2。因為它在每個路徑上對黑節點數目增加一，性質5符合。void insert_case1(node *n){if(n-&gt;parent == NULL)n-&gt;color = BLACK;elseinsert_case2 (n);情形2:新節點的父節點P是黑色，所以性質4沒有失效。在這種情形下，樹仍是有效的。性質5也未受到威脅，儘管新節點N有兩個黑色葉子子節點；但由於新節點N是紅色，透過它的每個子節點的路徑就都有同透過它所取代的黑色的葉子的路徑同樣數目的黑色節點，所以依然滿足這個性質。void insert_case2(node *n){if(n-&gt;parent-&gt;color == BLACK)return; /* 樹仍舊有效*/elseinsert_case3 (n);注意：在下列情形下我們假定新節點的父節點為紅色，所以它有祖父節點；因為如果父節點是根節點，那父節點就應當是黑色。所以新節點總有一個叔父節點，儘管在情形4和5下它可能是葉子節點。void insert_case3(node *n){if(uncle(n) != NULL &amp;&amp; uncle (n)-&gt;color == RED) {n-&gt;parent-&gt;color = BLACK;uncle (n)-&gt;color = BLACK;grandparent (n)-&gt;color = RED;insert_case1(grandparent(n));elseinsert_case4 (n);注意：在餘下的情形下，我們假定父節點P是其祖父G的左子節點。如果它是右子節點，情形4和情形5中的"左"和"右"應當對調。void insert_case4(node *n){if(n == n-&gt;parent-&gt;right &amp;&amp; n-&gt;parent == grandparent(n)-&gt;left) {rotate_left(n);n = n-&gt;left;} else if(n == n-&gt;parent-&gt;left &amp;&amp; n-&gt;parent == grandparent(n)-&gt;right) {rotate_right(n);n = n-&gt;right;insert_case5 (n);void insert_case5(node *n){n-&gt;parent-&gt;color = BLACK;grandparent (n)-&gt;color = RED;if(n == n-&gt;parent-&gt;left &amp;&amp; n-&gt;parent == grandparent(n)-&gt;left) {rotate_right(n-&gt;parent);} else {/* Here, n == n-&gt;parent-&gt;right &amp;&amp; n-&gt;parent == grandparent (n)-&gt;right */rotate_left(n-&gt;parent);注意插入實際上是原地演算法，因為上述所有呼叫都使用了尾部遞迴。刪除.如果需要刪除的節點有兩個兒子，那麼問題可以被轉化成刪除另一個只有一個兒子的節點的問題，不違反任何性質，這就把問題簡化為如何刪除最多有一個兒子的節點的問題。它不關心這個節點是最初要刪除的節點還是我們從中複製出值的那個節點。在本文餘下的部分中，我們只需要討論刪除只有一個兒子的節點，它的父親和兒子一定是黑色的。所以我們可以簡單的用它的黑色兒子替換它，並不會破壞性質3和性質4。透過被刪除節點的所有路徑只是少了一個紅色節點，這樣可以繼續保證性質5。另一種簡單情況是在被刪除節點是黑色而它的兒子是紅色的時候。如果只是去除這個黑色節點，用它的紅色兒子頂替上來的話，會破壞性質5，但是如果我們重繪它的兒子為黑色，則曾經透過它的所有路徑將透過它的黑色兒子，這樣可以繼續保持性質5。需要進一步討論的是在要刪除的節點和它的兒子二者都是黑色的時候，這是一種複雜的情況為S。在下面的示意圖中，我們還是使用P稱呼N的父親，SL稱呼S的左兒子，SR稱呼S的右兒子。我們將使用下述函式找到兄弟節點：struct node *sibling(struct node *n)if(n == n-&gt;parent-&gt;left)return n-&gt;parent-&gt;right;elsereturn n-&gt;parent-&gt;left;我們可以使用下列程式碼進行上述的概要步驟，這裡的函式codice_1替換codice_2到codice_3在樹中的位置。出於方便，在本章節中的程式碼將假定空葉子被用不是NULL的實際節點物件來表示。voiddelete_one_child(struct node *n)/** Precondition: n has at most one non-null child.struct node *child = is_leaf(n-&gt;right)? n-&gt;left : n-&gt;right;replace_node(n, child);if(n-&gt;color == BLACK){if(child-&gt;color == RED)child-&gt;color = BLACK;elsedelete_case1 (child);free (n);如果N和它初始的父親是黑色，則刪除它的父親導致透過N的路徑都比不透過它的路徑少了一個黑色節點。因為這違反了性質5，樹需要被重新平衡。有幾種情形需要考慮：情形1: N是新的根。在這種情形下，我們就做完了。我們從所有路徑去除了一個黑色節點，而新根是黑色的，所以性質都保持著。voiddelete_case1(struct node *n)if(n-&gt;parent != NULL)delete_case2 (n);注意：在情形2、5和6下，我們假定N是它父親的左兒子。如果它是右兒子，則在這些情形下的"左"和"右"應當對調。voiddelete_case2(struct node *n)struct node *s = sibling (n);if(s-&gt;color == RED){n-&gt;parent-&gt;color = RED;s-&gt;color = BLACK;if(n == n-&gt;parent-&gt;left)rotate_left(n-&gt;parent);elserotate_right(n-&gt;parent);delete_case3 (n);voiddelete_case3(struct node *n)struct node *s = sibling (n);if((n-&gt;parent-&gt;color == BLACK)&amp;&amp;(s-&gt;color == BLACK)&amp;&amp;(s-&gt;left-&gt;color == BLACK)&amp;&amp;(s-&gt;right-&gt;color == BLACK)) {s-&gt;color = RED;delete_case1(n-&gt;parent);} elsedelete_case4 (n);voiddelete_case4(struct node *n)struct node *s = sibling (n);if（(n-&gt;parent-&gt;color == RED)&amp;&amp;(s-&gt;color == BLACK)&amp;&amp;(s-&gt;left-&gt;color == BLACK)&amp;&amp;(s-&gt;right-&gt;color == BLACK)) {s-&gt;color = RED;n-&gt;parent-&gt;color = BLACK;} elsedelete_case5 (n);voiddelete_case5(struct node *n)struct node *s = sibling (n);if（s-&gt;color == BLACK){ /* this if statement is trivial,due to Case 2(even though Case two changed the sibling to a sibling's child,the sibling's child can't be red, since no red parent can have a red child). */// the following statements just force the red to be on the left of the left of the parent,// or right of the right, so case six will rotate correctly.if((n == n-&gt;parent-&gt;left)&amp;&amp;(s-&gt;right-&gt;color == BLACK)&amp;&amp;(s-&gt;left-&gt;color == RED)) { // this last test is trivial too due to cases 2-4.s-&gt;color = RED;s-&gt;left-&gt;color = BLACK;rotate_right (s);} else if((n == n-&gt;parent-&gt;right)&amp;&amp;(s-&gt;left-&gt;color == BLACK)&amp;&amp;(s-&gt;right-&gt;color == RED)) {// this last test is trivial too due to cases 2-4.s-&gt;color = RED;s-&gt;right-&gt;color = BLACK;rotate_left (s);delete_case6 (n);voiddelete_case6(struct node *n)struct node *s = sibling (n);s-&gt;color = n-&gt;parent-&gt;color;n-&gt;parent-&gt;color = BLACK;if(n == n-&gt;parent-&gt;left){s-&gt;right-&gt;color = BLACK;rotate_left(n-&gt;parent);} else {s-&gt;left-&gt;color = BLACK;rotate_right(n-&gt;parent);同樣的，函式呼叫都使用了尾部遞迴，所以演算法是原地演算法。此外，在旋轉之後不再做遞迴呼叫，所以進行了恆定數目的旋轉。C++示例程式碼.using namespace std;class bst {private:struct Node {int value;bool color;Node *leftTree, *rightTree, *parent;Node() : value(0), color(RED), leftTree(NULL), rightTree(NULL), parent(NULL) { }Node* grandparent() {if(parent == NULL){return NULL;return parent-&gt;parent;Node* uncle() {if(grandparent() == NULL) {return NULL;if(parent == grandparent()-&gt;rightTree)return grandparent()-&gt;leftTree;elsereturn grandparent()-&gt;rightTree;Node* sibling() {if(parent-&gt;leftTree == this)return parent-&gt;rightTree;elsereturn parent-&gt;leftTree;};void rotate_right(Node *p){Node *gp = p-&gt;grandparent();Node *fa = p-&gt;parent;Node *y = p-&gt;rightTree;fa-&gt;leftTree = y;if(y != NIL)y-&gt;parent = fa;p-&gt;rightTree = fa;fa-&gt;parent = p;if(root == fa)root = p;p-&gt;parent = gp;if(gp != NULL){if(gp-&gt;leftTree == fa)gp-&gt;leftTree = p;elsegp-&gt;rightTree = p;void rotate_left(Node *p){if(p-&gt;parent == NULL){root = p;return;Node *gp = p-&gt;grandparent();Node *fa = p-&gt;parent;Node *y = p-&gt;leftTree;fa-&gt;rightTree = y;if(y != NIL)y-&gt;parent = fa;p-&gt;leftTree = fa;fa-&gt;parent = p;if(root == fa)root = p;p-&gt;parent = gp;if(gp != NULL){if(gp-&gt;leftTree == fa)gp-&gt;leftTree = p;elsegp-&gt;rightTree = p;void inorder(Node *p){if(p == NIL)return;if(p-&gt;leftTree)inorder(p-&gt;leftTree);cout « p-&gt;value « " ";if(p-&gt;rightTree)inorder(p-&gt;rightTree);string outputColor (bool color) {return color ? "BLACK" : "RED";Node* getSmallestChild(Node *p){if(p-&gt;leftTree == NIL)return p;return getSmallestChild(p-&gt;leftTree);bool delete_child(Node *p, int data){if(p-&gt;value &gt; data){if(p-&gt;leftTree == NIL){return false;return delete_child(p-&gt;leftTree, data);} else if(p-&gt;value  0所以它是個內部節點。同樣的它有黑色高度要麼是bh(formula_22)要麼是bh(formula_22)-1的兩個兒子。透過歸納假設每個兒子都有至少formula_30個內部接點，所以formula_22有：formula_32個內部節點。使用這個引理我們現在可以展示出樹的高度是對數性的。因為在從根到葉子的任何路徑上至少有一半的節點是黑色，根的黑色高度至少是formula_33。透過引理我們得到：formula_34因此根的高度是formula_1。