Can you summarize the following document?
        
  紅黑樹和AVL樹一樣都對插入時間、刪除時間和查詢時間提供了最好可能的最壞情況擔保。這不只是使它們在時間敏感的應用,如實時應用(real time application)中有價值,而且使它們有在提供最壞情況擔保的其他資料結構中作為基礎模板的價值;例如,在計算幾何中使用的很多資料結構都可以基於紅黑樹實現。  紅黑樹在函數語言程式設計中也特別有用,在這裡它們是最常用的持久資料結構(persistent data structure)之一,它們用來構造關聯陣列和集合,每次插入、刪除之後它們能保持為以前的版本。除了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葉子"或"空(null)葉子",如上圖所示,它不包含資料而只充當樹在此結束的指示。這些節點在繪圖中經常被省略,導致了這些樹好像同上述原則相矛盾,而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點,儘管其中的一個或兩個可能是空葉子。

  因為每一個紅黑樹也是一個特化的二叉查詢樹,因此紅黑樹上的只讀操作與普通二叉查詢樹上的只讀操作相同。然而,在紅黑樹上進行插入操作和刪除操作會導致不再符合紅黑樹的性質。恢復紅黑樹的性質需要少量(formula_1)的顏色變更(實際是非常快速的)和不超過三次樹旋轉(對於插入操作是兩次)。雖然插入和刪除很複雜,但操作時間仍可以保持為formula_1次。

  我們首先以二叉查詢樹的方法增加節點並標記它為紅色。(如果設為黑色,就會導致根到葉子的路徑上有一條路上,多一個額外的黑節點,這個是很難調整的。但是設為紅色節點後,可能會導致出現兩個連續紅色節點的衝突,那麼可以通過顏色調換(color flips)和樹旋轉來調整。)下面要進行什麼操作取決於其他臨近節點的顏色。同人類的家族樹中一樣,我們將使用術語"叔父節點"來指一個節點的父節點的兄弟節點。注意:  在下面的示意圖中,將要插入的節點標為N,N的父節點標為P,N的祖父節點標為G,N的叔父節點標為U。在圖中展示的任何顏色要麼是由它所處情形這些所作的假定,要麼是假定所暗含(imply)的。  對於每一種情形,我們將使用C示例程式碼來展示。通過下列函式,可以找到一個節點的叔父和祖父節點:  情形1:新節點N位於樹的根上,沒有父節點。在這種情形下,我們把它重繪為黑色以滿足性質2。因為它在每個路徑上對黑節點數目增加一,性質5符合。  情形2:新節點的父節點P是黑色,所以性質4沒有失效(新節點是紅色的)。在這種情形下,樹仍是有效的。性質5也未受到威脅,儘管新節點N有兩個黑色葉子子節點;但由於新節點N是紅色,通過它的每個子節點的路徑就都有同通過它所取代的黑色的葉子的路徑同樣數目的黑色節點,所以依然滿足這個性質。  注意:在下列情形下我們假定新節點的父節點為紅色,所以它有祖父節點;因為如果父節點是根節點,那父節點就應當是黑色。所以新節點總有一個叔父節點,儘管在情形4和5下它可能是葉子節點。  注意:在餘下的情形下,我們假定父節點P是其祖父G的左子節點。如果它是右子節點,情形4和情形5中的"左"和"右"應當對調。  注意插入實際上是原地演算法,因為上述所有呼叫都使用了尾部遞迴。

  如果需要刪除的節點有兩個兒子,那麼問題可以被轉化成刪除另一個只有一個兒子的節點的問題(為了表述方便,這裡所指的兒子,為非葉子節點的兒子)。對於二叉查詢樹,在刪除帶有兩個非葉子兒子的節點的時候,我們要麼找到它左子樹中的最大元素、要麼找到它右子樹中的最小元素,並把它的值轉移到要刪除的節點中(如在這裡所展示的那樣)。我們接著刪除我們從中複製出值的那個節點,它必定有少於兩個非葉子的兒子。因為只是複製了一個值(沒有複製顏色),不違反任何性質,這就把問題簡化為如何刪除最多有一個兒子的節點的問題。它不關心這個節點是最初要刪除的節點還是我們從中複製出值的那個節點。  在本文餘下的部分中,我們只需要討論刪除只有一個兒子的節點(如果它兩個兒子都為空,即均為葉子,我們任意將其中一個看作它的兒子)。如果我們刪除一個紅色節點(此時該節點的兒子將都為葉子節點),它的父親和兒子一定是黑色的。所以我們可以簡單的用它的黑色兒子替換它,並不會破壞性質3和性質4。通過被刪除節點的所有路徑只是少了一個紅色節點,這樣可以繼續保證性質5。另一種簡單情況是在被刪除節點是黑色而它的兒子是紅色的時候。如果只是去除這個黑色節點,用它的紅色兒子頂替上來的話,會破壞性質5,但是如果我們重繪它的兒子為黑色,則曾經通過它的所有路徑將通過它的黑色兒子,這樣可以繼續保持性質5。  需要進一步討論的是在要刪除的節點和它的兒子二者都是黑色的時候,這是一種複雜的情況(這種情況下該結點的兩個兒子都是葉子結點,否則若其中一個兒子是黑色非葉子結點,另一個兒子是葉子結點,那麼從該結點通過非葉子結點兒子的路徑上的黑色結點數最小為2,而從該結點到另一個葉子結點兒子的路徑上的黑色結點數為1,違反了性質5)。我們首先把要刪除的節點替換為它的兒子。出於方便,稱呼這個兒子為N(在新的位置上),稱呼它的兄弟(它父親的另一個兒子)為S。在下面的示意圖中,我們還是使用P稱呼N的父親,S稱呼S的左兒子,S稱呼S的右兒子。我們將使用下述函式找到兄弟節點:  我們可以使用下列程式碼進行上述的概要步驟,這裡的函式codice_1替換codice_2到codice_3在樹中的位置。出於方便,在本章節中的程式碼將假定空葉子被用不是NULL的實際節點物件來表示(在"插入"章節中的程式碼可以同任何一種表示一起工作)。  如果N和它初始的父親是黑色,則刪除它的父親導致通過N的路徑都比不通過它的路徑少了一個黑色節點。因為這違反了性質5,樹需要被重新平衡。有幾種情形需要考慮:  情形1: N是新的根。在這種情形下,我們就做完了。我們從所有路徑去除了一個黑色節點,而新根是黑色的,所以性質都保持著。  注意:在情形2、5和6下,我們假定N是它父親的左兒子。如果它是右兒子,則在這些情形下的"左"和"右"應當對調。  同樣的,函式呼叫都使用了尾部遞迴,所以演算法是原地演算法。此外,在旋轉之後不再做遞迴呼叫,所以進行了恆定數目(最多3次)的旋轉。

  包含"n"個內部節點的紅黑樹的高度是formula_1。  定義:  引理:以節點formula_9為根的子樹有至少formula_14個內部節點。  引理的證明(通過歸納高度):  基礎:formula_15  如果formula_9的高度是零則它必定是NIL,因此formula_17。所以:  formula_18  歸納假設:formula_19的formula_9有formula_21個內部節點暗示了h(formula_22) = k+1的formula_22有formula_24個內部節點。  因為formula_22有h(formula_22)> 0所以它是個內部節點。同樣的它有黑色高度要麼是bh(formula_22)要麼是bh(formula_22)-1(依據formula_22是紅色還是黑色)的兩個兒子。通過歸納假設每個兒子都有至少formula_30個內部接點,所以formula_22有:  formula_32  個內部節點。  使用這個引理我們現在可以展示出樹的高度是對數性的。因為在從根到葉子的任何路徑上至少有一半的節點是黑色(根據紅黑樹性質4),根的黑色高度至少是formula_33。通過引理我們得到:  formula_34  因此根的高度是formula_1。
紅黑樹(英語:Red–black tree)是一種自平衡二叉查詢樹,是在電腦科學中用到的一種資料結構,典型的用途是實現關聯陣列。它在1972年由魯道夫·貝爾發明,被稱為"對稱二叉B樹",它現代的名字源於Leo J. Guibas和Robert Sedgewick於1978年寫的一篇論文。紅黑樹的結構複雜,但它的操作有著良好的最壞情況執行時間,並且在實踐中高效:它可以在formula_1時間內完成查詢、插入和刪除,這裡的formula_2是樹中元素的數目。