本節書摘來自華章計算機《程式設計解題政策》一書中的第1章，第1.4節,作者：吳永輝 王建德 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
我們知道，二叉查找樹(binary search tree)能夠支援多種動态集合操作，是以在程式設計競賽中，二叉查找樹起着非常重要的作用，它可以用來表示有序集合、建立索引或優先隊列等。作用于二叉查找樹上的基本操作時間是與樹的高度成正比的：對于一棵含n個節點的二叉查找樹，如果呈完全二叉樹結構，則這些操作的最壞情況運作時間為o(log2n)；但如果呈線性鍊結構，則這些操作的最壞情況運作時間退化為o(n)。針對二叉查找樹這種不平衡、不穩定的弊病，人們做了大量改進優化的嘗試，使其基本操作在最壞情況下的性能盡量保持良好。本節将介紹兩種改進型的二叉查找樹：
1) 伸展樹(splay tree)。
2) 紅黑樹(redblack tree)。
與普通的二叉查找樹一樣，這兩種“改進版”同樣具備有序性，即樹中每一個節點x都滿足：該節點左子樹中的每一個元素都不大于x，而其右子樹中的每一個元素都大于x。但不同的是，樹的高度保持近似平衡，使得每一步操作在最壞情況下亦有良好的運作時間，并且在運作過程中保持穩定和高效，可在o(log2n)時間内完成查找、插入和删除(n為樹中元素數)。
1.4.1 改進型1：伸展樹
這裡要介紹的伸展樹是一種改進型的二叉查找樹。雖然它并不能完全保證樹結構始終平衡，但對于伸展樹的一系列操作，我們可以證明其每一步操作的平攤複雜度都是o(log2n)。是以從某種意義上說，這種改進後的二叉查找樹能夠基本達到一種平衡狀态。至于伸展樹的空間要求與程式設計複雜度，在各種樹狀資料結構中都是很優秀的。
伸展樹的基本操作包括：
1) 伸展操作，即伸展樹作自我調整。
2) 判斷元素x是否在伸展樹中。
3) 将元素x插入伸展樹。
4) 将元素x從伸展樹中删除。
5) 将兩棵伸展樹s1與s2合并成為一棵伸展樹(其中s1的所有元素都小于s2的元素)。
6) 以x為界，将伸展樹s分離為兩棵伸展樹s1和s2，其中s1中所有元素都小于x，s2中的所有元素都大于x。
其中基本操作2)～6)都是在伸展操作的基礎上進行的。
（1） 伸展操作——splay(x，s)
伸展操作是在保持伸展樹有序性的前提下，通過一系列旋轉将伸展樹s中的元素x調整至樹的根部。在調整的過程中，要分以下三種情況分别處理。
情況1：節點x的父節點y是根節點。
這時，如果x是y的左孩子，我們進行一次zig(右旋)操作；如果x是y的右孩子，則進行一次zag(左旋)操作。經過旋轉，x成為二叉查找樹s的根節點，調整結束。我們稱這種旋轉為單旋轉，如圖1.4-1所示。
情況2：節點x的父節點y不是根節點，y的父節點為z且x與y同時是各自父節點的左孩子或者同時是各自父節點的右孩子。
這時，進行一次zig-zig操作或者zag-zag操作，即假設目前節點為x，x的父節點為y，u的父節點為z，如果y和x同為其父親的左孩子或右孩子，那麼先旋轉y，再旋轉x。我們稱這種旋轉為一字形旋轉，如圖1.4-2所示。
情況3：節點x的父節點y不是根節點，y的父節點為z，x與y中一個是其父節點的左孩子而另一個是其父節點的右孩子。
這時，進行一次zig-zag操作或者zag-zig操作，即連續旋轉兩次x。我們稱這種旋轉為之字形旋轉，如圖1.4-3所示。
如圖1.4-4所示，執行splay(1，s)，我們将元素1調整到了伸展樹s的根部，再執行splay(2，s)，如圖1.4-5所示。
https://yqfile.alicdn.com/5815de8c859ddbd3dda5fb734dea500fdd967ffd.png" >
我們從直覺上可以看出經調整後，伸展樹比原來“平衡”了許多。伸展操作的過程并不複雜，隻需要根據情況進行旋轉就可以了，而三種旋轉都是由基本的左旋和右旋組成，實作較為簡單。
利用splay操作，我們可以在伸展樹s上進行如下運算。
（2） 判斷元素x是否在伸展樹s表示的有序集中——find(x，s)
首先，與在二叉查找樹中的查找操作一樣，在伸展樹中查找元素x。如果x在樹中，則将x調整至伸展樹s的根部(執行splay(x，s))。
（3） 将元素x插入伸展樹s表示的有序集中——insert(x，s)
與處理普通的二叉查找樹一樣，将x插入到伸展樹s中的相應位置上，再将x調整至伸展樹s的根部(執行splay(x，s))。
（4） 将元素x從伸展樹s所表示的有序集中删除——delete(x，s)
首先，用在二叉查找樹中查找元素的方法找到x的位置。如果x沒有孩子或隻有一個孩子，那麼直接将x删去，并通過splay操作，将x節點的父節點調整到伸展樹的根節點處。否則，向下查找x的後繼y，用y替代x的位置，最後執行splay(y，s)，将y調整為伸展樹的根。
（5） 将兩棵伸展樹s1與s2合并成為一棵伸展樹——join(s1，s2)(其中s1的所有元素值都小于s2的所有元素值)
首先，找到伸展樹s1中最大的一個元素x，再通過splay(x，s1)将x調整到伸展樹s1的根。然後再将s2作為x節點的右子樹。這樣，就得到了新的伸展樹s，如圖1.4-6所示。
（6） 以x為界，将伸展樹s分離為兩棵伸展樹s1和s2——split(x，s)(其中s1中所有元素都小于x，s2中的所有元素都大于x)
首先執行find(x，s)，将元素x調整為伸展樹的根節點，則x的左子樹就是s1，而右子樹為s2。然後去除x通往左右兒子的邊，如圖1.4-7所示。
在伸展操作的基礎上，除了上面介紹的五種基本操作，伸展樹還支援求最大值、最小值、前驅、後繼等多種操作，這些基本操作也都是建立在伸展操作的基礎上的。
由上述操作的實作過程可以看出，伸展樹基本操作的時間效率完全取決于splay操作的時間複雜度。下面，我們用會計方法來分析splay操作的平攤複雜度。
首先，我們定義一些符号：s(x)表示以節點x為根的子樹。s表示伸展樹s的節點個數。令μ(s)=log2s」，μ(x)=μ(s(x))，如圖1.4-8所示。
https://yqfile.alicdn.com/28b97bc8181a5acc24ad86423b72d0db14371069.png" >
我們用1元錢表示機關代價(這裡我們将對于某個點通路和旋轉看作一個機關時間的代價)。定義伸展樹不變量：在任意時刻，伸展樹中的任意節點x都至少有μ(x)元的存款。
在splay調整過程中，費用将會用在以下兩個方面：
1) 為使用的時間付費。也就是每一次機關時間的操作，我們要支付1元錢。
2) 當伸展樹的形狀調整時，我們需要加入一些錢或者重新配置設定原來樹中每個節點的存款，以保持不變量繼續成立。
下面給出關于splay操作花費的定理：
【定理1.4-1】 在每一次splay(x，s)操作中，調整樹的結構與保持伸展樹不變量的總花費不超過3μ(s)+1。
證明：用μ(x)和μ′(x)分别表示在進行一次zig、zig-zig或zig-zag操作前後節點x處的存款。下面，我們分三種情況分析旋轉操作的花費。
情況1：zig或zag(如圖1.4-9)。
我們進行zig或者zag操作時，為了保持伸展樹不變量繼續成立，我們需要花費：
此外我們花費另外1元錢用來支付通路、旋轉的基本操作。是以，一次zig或zag操作的花費至多為3(μ(s)-μ(x))。
情況2：zig-zig或zag-zag(如圖1.4-10)。
我們進行zig-zig操作時，為了保持伸展樹不變量，我們需要花費：
與第一種情況一樣，我們也需要花費另外的1元錢來支付機關時間的操作。
當μ′(x)<μ(x)時，顯然2(μ′(x)-μ(x))+1≤3(μ′(x)-μ(x))。也就是進行zig-zig操作的花費不超過3(μ′(x)-μ(x))。
當μ′(x)=μ(x)時，我們可以證明μ′(x)+μ′(y)+μ′(z)<μ(x)+μ(y)+μ(z)，也就是說我們不需要任何花費保持伸展樹不變量，并且可以得到退回來的錢，用其中的1元支付通路、旋轉等操作的費用。為了證明這一點，我們假設μ′(x)+μ′(y)+μ′(z)>μ(x)+μ(y)+μ(z)。
聯系第一種情況，我們有μ(x)=μ′(x)=μ(z)。那麼，顯然μ(x)=μ(y)=μ(z)。于是，可以得出μ(x)=μ′(z)=μ(z)。令a=1+a+b，b=1+c+d，那麼就有：
我們不妨設b≥a，則有：
①與②沖突，是以我們可以得到μ′(x)=μ(x)時，zig-zig操作不需要任何花費，顯然也不超過3(μ′(x)-μ(x))。
情況3：zig-zag或zag-zig(如圖1.4-11)。
與情況2類似，我們可以證明，每次zig-zag操作的花費也不超過3(μ′(x)-μ(x))。
以上三種情況說明，zig操作花費最多為3(μ(s)-μ(x))+1，zigzig或zigzag操作最多花費3(μ′(x)-μ(x))。那麼将旋轉操作的花費依次累加，則一次splay(x，s)操作的費用就不會超過3μ(s)+1，如圖1.4-12所示。
https://yqfile.alicdn.com/f0ae62e7c2544f26aa3ca4cf2f8d2f1fbc319e6d.png" >
也就是說，對于伸展樹的各種以splay操作為基礎的基本操作的平攤複雜度，都是o(log2n)。可見，伸展樹是一種時間效率非常優秀的資料結構。
1.4.2 改進型2：紅黑樹
紅黑樹也是一種自平衡的二叉查找樹。雖然同伸展樹、平衡二叉樹一樣，它可以在o(log2n)時間内完成查找、插入和删除等操作，但其統計性能要更好一些，是以紅黑樹在很多地方都有應用，例如c++stl中的很多部分(目前包括set、multiset、map、multimap)應用了紅黑樹的變體；java提供的集合類treemap本身就是一個紅黑樹的實作。紅黑樹的操作有着良好的最壞情況運作時間，任何不平衡都會在三次旋轉之内解決，為我們提供了一個比較“便宜”的解決方案。
紅黑樹，顧名思義，就是通過紅黑兩種顔色域保證樹的高度近似平衡。它的每個節點是一個五元組：color(顔色)，key(資料)，left(左孩子)，right(右孩子)和p(父節點)。紅黑樹具有如下性質。
【性質1.4-1】 節點是紅色或黑色。
【性質1.4-2】 根是黑色。
【性質1.4-3】 所有葉子都是黑色(葉子是nil節點)。
【性質1.4-4】 如果一個節點是紅的，則它的兩個兒子都是黑的。
【性質1.4-5】 從任一節點到其葉子的所有簡單路徑都包含相同數目的黑色節點(如圖1.4-13)。
https://yqfile.alicdn.com/59d6a6d8ceb5aa1de4f42c15c63611fd8b33db92.png" >
這五條性質凸顯了紅黑樹的一個關鍵特征:從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。為什麼呢？性質1.4-4暗示着任何一個簡單路徑上不能有兩個毗連的紅色節點，這樣，最短的可能路徑全是黑色節點，最長的可能路徑有交替的紅色和黑色節點。同時根據性質1.4-5知道：所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。
由于紅黑樹也是二叉查找樹，是以紅黑樹上的查找操作與普通二叉查找樹上的查找操作相同。然而，紅黑樹上的插入操作和删除操作可能會導緻紅黑樹性質的喪失。恢複紅黑樹的性質需要少量節點的顔色變更(變更顔色的節點數不超過o(log2n)，非常快速)和不超過三次的樹旋轉(插入操作僅兩次)。雖然插入和删除操作較複雜，但實際時間仍可以保持為o(log2n)次。
1.插入操作
插入操作可以概括為以下3個步驟。
步驟1：查找要插入的位置，時間複雜度為o(log2n)。
步驟2：将插入節點的color賦為紅色。
步驟3：自下而上重新調整該樹為紅黑樹。
其中，步驟1的查找方法跟普通二叉查找樹一樣；步驟2之是以将插入節點的顔色賦為紅色，是因為若設為黑色，就會因多出一個黑色節點而破壞性質1.4-5，這個是很難調整的。但設為紅色節點後，可能會導緻出現兩個連續紅色節點的沖突，那麼可以通過簡單的顔色調換(color flips)和樹旋轉來調整。至于進行什麼操作取決于其臨近節點的顔色。同人類的家族樹一樣，我們将使用術語叔父節點來指一個節點的父節點的兄弟節點。注意：性質1.4-1和性質1.4-3總是保持着；性質1.4-4隻在增加紅色節點、重繪黑色節點為紅色或做旋轉時受到威脅；性質1.4-5隻在增加黑色節點、重繪紅色節點為黑色或做旋轉時受到威脅。
下面讨論步驟3的一些細節。
設要插入的紅色節點為n，其父節點為p，p的兄弟節點為u、父親節點為g(即p和u是g的兩個子節點，u是n的叔父節點)。父節點p有兩種可能顔色：
如果p是黑色的，則整棵樹保持紅黑樹性質，不必調整。
如果p是紅色的(可知，其父節點g一定是黑色的)，則插入n後，違背了性質1.4-4，需要進行調整。調整分以下3種情況：
情況1：n的叔叔u是紅色的。
如圖1.4-14所示，我們将p和u重繪為黑色并重繪節點g為紅色(用來保持性質1.4-4)。現在新節點n有了一個黑色的父節點p，因為通過父節點p或叔父節點u的任何路徑都必定通過祖父節點g，在這些路徑上的黑節點數沒有改變。但是，紅色的祖父節點g的父節點也有可能是紅色的，這就違反了性質1.4-4。為了解決這個問題，我們把g當成是新加入的節點進行各種情況的檢查。
情況2：n的叔叔u是黑色的，且n是右孩子。
如圖1.4-15所示，我們對p進行一次左旋轉調換新節點和其父節點的角色；接着，按情形3處理以前的父節點p，以解決仍然失效的性質1.4-4。
https://yqfile.alicdn.com/139e9871a3a421ac172ba6b2115182f3c46b52e8.png" >
情況3：n的叔叔u是黑色的，且n是左孩子。
如圖1.4-16所示，對祖父節點g的一次右旋轉；在旋轉産生的樹中，以前的父節點p現在是新節點n和以前的祖父節點g的父節點，然後交換以前的父節點p和祖父節點g的顔色，使其滿足性質1.4-4，同時性質1.4-5也依然滿足。
https://yqfile.alicdn.com/d4588ec6dd61810e011c49cc3b68b220620c4de5.png" >
2.删除操作
删除操作也可以概括為以下3個步驟。
步驟1：查找删除位置，時間複雜度為o(log2n)。
步驟2：用被删節點的後繼替換該節點(隻進行資料替換即可，不必調整指針，後繼節點是中序周遊中緊挨着該節點的節點，即右孩子的最左孩子節點)。
步驟3：如果删除節點的替換節點為黑色，則需重新調整該樹為紅黑樹。
其中步驟1的查找方法跟普通二叉查找樹一樣，步驟2之是以用後繼節點替換删除節點，是因為這樣可以保證該後繼節點之上仍是一個紅黑樹，而後繼節點可能是一個葉節點或者隻有右子樹的節點。若後繼節點隻有右子樹，則用右兒子替換後繼節點即可達到删除的目的。如果需要删除的節點有兩個兒子，那麼問題可以被轉化成删除另一個隻有一個兒子的節點的問題(因為對于二叉查找樹，我們要麼找其左子樹中的最大元素，要麼找其右子樹中的最小元素，并把它的值轉移到要删除的節點中。接着，删除被複制出值的那個節點，它必定有少于兩個非葉子的兒子。因為隻是複制了一個值而不違反任何性質，這樣就把問題簡化為如何删除最多有一個兒子的節點的問題)。在步驟3中，如果删除節點為紅色節點，則它的父親和孩子全為黑節點，這樣直接删除該節點即可，不必進行任何調整。如果删除節點是黑節點，則分四種情況讨論：
設要删除的節點為n，其父節點為p，其兄弟節點為s。由于n是黑色的，則p和s可能是黑色的，也可能是紅色的。
情況1：s是紅色的。
此時p肯定是紅色的。我們對n的父節點進行左旋轉，然後把紅色兄弟轉換成n的祖父，對調n的父親和祖父的顔色。完成這兩個操作後，盡管所有的路徑仍然有相同數目的黑色節點，現在n有了一個黑色兄弟一個紅色的父親(它的新兄弟是黑色的，因為它是紅色節點s的一個兒子)，是以可以繼續按情況2、情況3或情況4處理，使其新兄弟變為黑色，新父親變為紅色(如圖1.4-17)。
情況2：s和s的孩子全是黑色的。
在這種情況下，p可能是黑色或紅色的，我們簡單的重繪s為紅色。結果是通過s的所有路徑為以前不通過n的那些路徑，且都少了一個黑色節點。因為删除n的初始的父親，使通過n的所有路徑少了一個黑色節點，這使事情都平衡了起來。但是通過p的所有路徑現在比不通過p的路徑少了一個黑色節點。是以仍然違反性質1.4-4。要修正這個問題，我們就要将p調整為n，進行各種情況的檢查(圖1.4-18)。
情況3：s是黑色的，s的左孩子是紅色，右孩子是黑色。
這種情況下，我們在s上做右旋轉，這樣s的左兒子成為s的父親和n的新兄弟，接着交換s和它新父親的顔色。所有路徑仍有同樣數目的黑色節點，但n有了一個右兒子是紅色的黑色兄弟，是以進入了情況4。n和它的父親都不受這個變換的影響(如圖1.4-19)。
情況4：s是黑色的，s的右孩子是紅色。
在這種情況下，我們在n的父親上做左旋轉，使得s成為p和s的右兒子sr的父親。接着，交換p和s的顔色，并使sr為黑色(如圖1.4-20b))。子樹在它的根上仍是相同顔色，是以性質1.4-3沒有被違反。但是，n增加了一個黑色祖先:要麼n的父親p變成黑色，要麼它是黑色而s被增加一個黑色祖父。是以，通過n的路徑都增加了一個黑色節點。此時，如果一條路徑不通過n，則有兩種可能：
1) 它通過n的新兄弟(如圖1.4-20b)中的節點s)。那麼它以前和現在都必定通過s和p，而它們隻是交換了顔色。是以路徑保持了同樣數目的黑色節點。
2) 它通過n的新叔父、s的右兒子(如圖1.4-20b)中的節點sr)，那麼它以前通過s、p和sr，但現在僅通過s，它被假定為它以前父親的顔色，而sr由紅色變為黑色。合成效果是這條路徑通過了同樣數目的黑色節點。
https://yqfile.alicdn.com/617a9916ec532d5fb71c86d3c8cfc68313ed3b96.png" >
在任何情況下，在這些路徑上的黑色節點數目都沒有改變，是以恢複了性質1.4-4。在圖1.4-20中的白色節點可以是紅色或黑色，但是在變換前後的顔色相同。
紅黑樹之是以能夠在o(log2n)時間内做查找、插入和删除，是因為樹的高度能保持o(log2n)的漸進邊界。下面，我們就來給予證明這個結論:
【定理1.4-2】 包含n個内部節點的紅黑樹的高度是o(log2n)。
證明：
設以節點v為根的子樹的高度為h(v)；從v到子樹中任何葉子的黑色節點數(亦稱黑色高度。若v是黑色，則不計數)為bh(v)；
【引理1.4-1】 以節點v為根的子樹有至少2bh(v)-1個内部節點。
證明(歸納法)：
如果v的高度是零(h(v)=0)，則它必定是nil，是以bh(v)=0。是以2bh(v)-1=20-1=0。
歸納假設:h(v)=k的v有2bh(v)-1-1個内部節點暗示了h(v′)=k+1的v′有2bh(v′)-1個内部節點。
因為v′有h(v′)>0，是以它是個内部節點。同樣，它有黑色高度要麼是bh(v′)，要麼是bh(v′)-1(依據v′是紅色還是黑色)的兩個兒子。通過歸納假設每個兒子都有至少2bh(v′)-1-1個内部接點，是以v′有2bh(v′)-1-1+2bh(v′)-1-1+1=2bh(v′)-1個内部節點。
使用引理1.4-1就可以展示出樹的高度是對數性的。因為在從根到葉子的任何路徑上至少有一半的節點是黑色(根據紅黑樹性質1.4-4)，根的黑色高度至少是h(root)2，即
由此得證，紅黑樹根的高度是o(log2n)。
1.4.3 應用改進型的二叉查找樹解題
改進型的二叉查找樹作為一種時間效率很高、空間要求不大的資料結構，在解題中大有用武之地。下面就通過三個範例說明其應用價值。
【1.4.1 turnover】
【問題描述】
tiger最近被公司升任為營業部經理，他上任後接受公司交給的第一項任務便是統計并分析公司成立以來的營業情況。
tiger拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業額。分析營業情況是一項相當複雜的工作。由于節假日、大減價或者是其他情況的時候，營業額會出現一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業額突變得很高或是很低，這就證明公司此時的經營狀況出現了問題。經濟管理學上定義了一種最小波動值來衡量這種情況：
該天的最小波動值=min｛該天以前某一天的營業額-該天營業額｝
當最小波動值越大時，就說明營業情況越不穩定。
而分析整個公司從成立到現在營業情況是否穩定，隻需要把每一天的最小波動值加起來就可以了。你的任務就是編寫一個程式幫助tiger來計算這個值。
第一天的最小波動值為第一天的營業額。
輸入：
輸入由檔案“turnover.in”讀入。
第一行為正整數n(n≤32767)，表示該公司從成立一直到現在的天數，接下來的n行每行有一個正整數ai(ai≤1000000)，表示第i天公司的營業額。
輸出：
輸出到檔案“turnover.out”。
輸出檔案僅有一個正整數，即∑每一天的最小波動值。結果小于231。
輸入輸出樣例：
https://yqfile.alicdn.com/63bdd04fa5cd311670bae3531bd85ee6e709eed1.png" >
結果說明：5+1-5+2-1+5-5+4-5+6-5=5+4+1+0+1+1=12
試題來源：湖南省隊2002年選拔賽
試題解析
簡述題意：給出一個含n個元素的數列a，對于第i個元素ai定義
即每次讀入一個數ai，就要在前面輸入的數中找到一個與該數相差最小的一個，計算兩數間差的絕對值fi。要求統計∑ni=1fi。
我們很容易想到一個時間複雜度為o(n2)的樸素算法：每次讀入一個數，再将前面輸入的數依次查找一遍，求出與目前數的最小內插補點，記入總結果t。但由于本題中n很大，這樣的算法是不可能在時限内出解的。而如果使用線段樹記錄已經讀入的數，就需要記下一個2m的大數組，空間需求很大。而紅黑樹與平衡二叉樹雖然在時間效率、空間複雜度上都比較優秀，但過高的程式設計複雜度卻讓人望而卻步。于是我們想到了伸展樹算法。
進一步分析本題，解題涉及對于有序集的三種操作：插入、求前驅、求後繼。而對于這三種操作，伸展樹的時間複雜度都非常優秀，于是我們設計了如下算法。
開始時，樹s為空，總和t為零。每次讀入一個數p，執行insert(p，s)，将p插入伸展樹s。這時，p也被調整到伸展樹的根節點。這時，求出p點左子樹中的最右點和右子樹中的最左點，這兩個點分别是有序集中p的前驅和後繼。然後求得最小內插補點，加入最後結果t。
由于對于伸展樹的基本操作的平攤複雜度都是o(log2n)的，是以整個算法的時間複雜度是o(n*log2n)；而空間上，可以用數組模拟指針存儲樹狀結構，這樣所用記憶體不超過400k；程式設計複雜度方面，伸展樹算法非常簡單，程式并不複雜。
程式清單
【1.4.2 jewel magic】
我是一個魔術師。我有一串綠寶石和珍珠。我可以在串中插入新的珠寶，或删除舊的珠寶。我甚至可以翻轉串的一個連續的部分。在任何時候，如果您指點兩個珠寶并問我，從這兩個珠寶開始，珠寶串的最長公共字首(the longest common prefix，lcp)的長度是多少，我可以馬上回答您的問題。您能比我做得更好嗎？
在形式上，本題給出一個由0和1組成的字元串。您要進行四種操作(如下所述，l表示字元串的長度，珠寶的目前位置從左到右由1到l編号)，如表1.4-1所示。
輸入包含若幹測試用例。每個測試用例的第一行給出整數n和m(1≤n，m≤200000)，其中n是初始時珠寶的數目，m是操作的數目。接下來的一行給出長度為n的01字元串。然後的m行每行給出一個操作。輸入以eof結束。輸入檔案大小不超過5mb。
對于每個類型的操作，輸出答案。
說明：
1) 在操作1 0 1之後的字元串:1000100001100。
2) 在操作3 7 10之後的字元串:1000101000100。
3) 在操作2 9之後的字元串:100010100100。
試題來源：rujia lius present 3:a data structure contest celebrating the 100th anniversary of tsinghua university
線上測試位址：uva 11996
簡述題意：給出一個初始長度為n的01串，進行四種操作：
1) 在位置x插入y。
2) 删除位置x的内容。
3) 翻轉區間［l，r］的内容。
4) 輸出從x開始和從y開始的串的最長公共字首。
如果以珠寶位置為關鍵字的話，則一個珠寶串可用一棵伸展樹表述，樹中的節點序号為珠寶位置i(i=左子樹的節點數+1)，以其為根的子樹代表一個連續的珠寶子串［l，r］(l≤i≤r)，左子樹對應珠寶i左方的連續子串［l，i-1］，右子樹對應珠寶i右方的連續子串［i+1，r］，為了能夠準确地找出任意兩個珠寶位置開始的最長公共字首，用一個11進制整數si表征珠寶子串［l，r］的狀态。
若珠寶子串［l，r］反轉的話，相當于左右子樹交換，反轉後［l，r］的狀态值。
顯然，插入、删除和反轉都需要通過伸展操作(splay)維護伸展樹。關鍵是如何查找首指針分别為x和y的兩個子串的最長公共字首(即lcp長度)。設lcp的長度區間［l，r］，初始時為［0，min{串長-x+1，串長-y+1}］。
顯然，若x==y，則lcp長度為r-1；若伸展樹中節點x的位碼≠節點y的位碼，則lcp長度為0。
否則采用二分查找的方法計算lcp長度：
得出lcp長度為l。
對于查詢從x開始長度為mid的串的狀态值，隻要将x-1和x+mid分别調整到根和根的右子樹，則根的右子樹的左子樹就是串［x，x+mid-1］，由此得到其狀态值(如圖1.4-21)。
用類似方法可查詢［y，y+mid-1］的狀态值。
當然，伸展樹算法并不是［1.4.1 turnover］和［1.4.2 jewel magic］的唯一算法，但它與其他常用的資料結構相比，還是有許多優勢的。下面表1.4-2比較了四種算法(順序查找、線段樹、avl樹和伸展樹)的時空複雜度和程式設計複雜度，從中可以看出伸展樹的優越性。
https://yqfile.alicdn.com/4b3159a15347fd9fd0c2f6adb214127e64b82598.png" >
由上面的分析介紹，我們可以發現伸展樹有以下幾個優點。
1) 時間複雜度低。伸展樹的各種基本操作的平攤複雜度都是o(log2n)的。在樹狀的資料結構中，無疑是非常優秀的。
2) 空間要求不高。與紅黑樹需要記錄每個節點的顔色、avl樹需要記錄平衡因子不同，伸展樹不需要記錄任何資訊以保持樹的平衡。
3) 算法簡單。程式設計容易，調試友善。伸展樹的基本操作都是以splay操作為基礎的，而splay操作中隻需根據目前節點的位置進行旋轉操作即可。
雖然伸展樹算法與avl樹在時間複雜度上相差不多，甚至有時候會比avl樹稍慢一些，但伸展樹的程式設計複雜度大大低于avl樹。競賽中使用伸展樹，在程式設計和調試等方面都更有優勢。
【1.4.3 black box】
我們的黑匣子(black box)表示一個原始的資料庫。它可以儲存一個整數數組，并有一個特殊的i變量。初始時，黑匣子為空，i等于0。黑匣子處理一個指令序列(事務)。它有兩類事務：
add(x)：将元素x加入到黑匣子中。
get:i增加1，并在黑匣子中給出所有整數中第i小的整數。在黑匣子中元素按非降序排列後，第i小的整數排在第i個位置上。
下例給出一個11個事務的序列，如表1.4-3所示。
https://yqfile.alicdn.com/bd488945757aff9b0d7288e05354d1a3166d4929.png" >
請你完成一個處理一個給出的事務序列的有效算法。add和get事務的最大數目：每種類型30000。
本題用兩個整數數組描述事務的序列：
1) a(1)，a(2)，…，a(m)：表示在黑匣子中的元素序列。a的值是絕對值不超過2000000000的整數，m≤30000。上面的例子中，a=(3，1，-4，2，8，-1000，2)。
2) u(1)，u(2)，…，u(n)：在執行第一個，第二個，……，第n個get事務時，黑匣子中序列元素的個數。上面的例子中，u=(1，2，6，6)。
黑匣子假設自然數序列u(1)，u(2)，……，u(n)按非降序排列，n≤m，并且對每個p(1≤p≤n)不等式p≤u(p)≤m成立。對于u序列的第p個元素，執行get事務從a(1)，a(2)，…，a(u(p))序列中給出第p小的整數。
輸入(以給出的次序)包含：m，n，a(1)，a(2)，…，a(m)，u(1)，u(2)，…，u(n)。所有的數字以空格和回車符分隔。
對于給出的事務序列，輸出黑匣子的結果，每個數字一行。
試題來源：acm northeastern europe 1996
線上測試位址：poj 1442，zoj 1319，uva 501
簡述題意：給出兩種操作：add(x)，将x添加到有序清單中；get(up［p］)傳回有序清單的前up［p］個元素中第p小的元素值。其中疊代器p在get操作後會自動加1。
方法1：使用大根堆h≥和小根堆h≤。
我們使用兩個堆使執行add和get操作：如圖1.4-22所示。那樣根對根地放置。在大根堆h≥中，根節點值h≥［1］最大；在小根堆h≤中，根節點值h≤［1］最小。
https://yqfile.alicdn.com/82afac119cbe88002f0a07c9519994df7597ba4c.png" >
在執行黑匣子操作時，我們時刻維護以下條件：
條件（1）：h≥［1］≤h≤［1］。
條件（2）：大根堆h≥的規模=i。
執行add(x)指令時，比較x與h≥［1］：若x≥h≥［1］，則将x插入h≤，否則從h≥中取出h≥［1］插入h≤，再将x插入h≥。
執行get指令時，h≤［1］就是待擷取的對象。輸出h≤［1］，同時從h≤中取出h≤［1］插入h≤，以維護條件(2)。
上述算法的時間複雜度為o(mlg2m+nlg2n)，算法較簡潔。
方法2：使用紅黑樹。
由于u(1)，u(2)，…，u(n)是遞增排序的，我們将u［］分成n個子區間：
［1，u［1］］，［u［1］+1，u［2］］，…，［u［n-1］+1，u［n］］
依次處理u［i］(1≤i≤n):
将a序列中第i個子區間的元素a［u［i-1］+1］..a［u［i］］插入紅黑樹，然後計算和輸出紅黑樹中第i小的元素。
顯然，算法的時間複雜度為o(nlg2m)，效率提高了不少。
由上可見，紅黑樹與伸展樹、avl樹類似，都是在進行插入和删除操作時通過特定操作保持二叉樹查找樹的平衡，進而獲得較高的檢索性能。差別在于：伸展樹、avl樹所追求的是全局均衡，插入、删除操作需調整整棵樹，頗為費時；而紅黑樹使用顔色來辨別節點高度，所追求的是局部平衡而不是非常嚴格的平衡。插入、删除資料時最多旋轉3次，尤其是對随機無序資料，由于平衡要求沒那麼嚴格，旋轉次數較少，因而提升了增删操作的效率。
但不足的是，由于紅黑樹須存儲顔色類型，是以存儲空間要比伸展樹略大一些，且程式設計複雜度和思維複雜度要高出許多。是以對這幾種改進型二叉查找樹的選擇權衡，需要遵循“邊分析，邊選擇，兼顧四個标準(時間複雜度、空間複雜度、程式設計複雜度和思維複雜度)”的原則。