BST
二叉查找樹（Binary Search Tree，簡(jiǎn)稱BST）是一棵二叉樹测僵，它的左子節(jié)點(diǎn)的值比父節(jié)點(diǎn)的值要小街佑，右節(jié)點(diǎn)的值要比父節(jié)點(diǎn)的值大。它的高度決定了它的查找效率捍靠。
在理想的情況下舆乔，二叉查找樹增刪查改的時(shí)間復(fù)雜度為O(logN)（其中N為節(jié)點(diǎn)數(shù)），最壞的情況下為O(N)剂公。當(dāng)它的高度為logN+1時(shí)希俩，我們就說二叉查找樹是平衡的。
BST存在的問題
BST存在的主要問題是纲辽，數(shù)在插入的時(shí)候會(huì)導(dǎo)致樹傾斜颜武，不同的插入順序會(huì)導(dǎo)致樹的高度不一樣，而樹的高度直接的影響了樹的查找效率拖吼。理想的高度是logN鳞上，最壞的情況是所有的節(jié)點(diǎn)都在一條斜線上，這樣的樹的高度為N吊档。
RBTree
基于BST存在的問題篙议，一種新的樹——平衡二叉查找樹(Balanced BST)產(chǎn)生了。平衡樹在插入和刪除的時(shí)候怠硼，會(huì)通過旋轉(zhuǎn)操作將高度保持在logN鬼贱。其中兩款具有代表性的平衡樹分別為AVL樹和紅黑樹。AVL樹由于實(shí)現(xiàn)比較復(fù)雜香璃，而且插入和刪除性能差这难，在實(shí)際環(huán)境下的應(yīng)用不如紅黑樹。
紅黑樹（Red-Black Tree葡秒，以下簡(jiǎn)稱RBTree）的實(shí)際應(yīng)用非常廣泛姻乓，比如Linux內(nèi)核中的完全公平調(diào)度器嵌溢、高精度計(jì)時(shí)器、ext3文件系統(tǒng)等等蹋岩，各種語言的函數(shù)庫(kù)如Java的TreeMap和TreeSet赖草，C++ STL的map、multimap剪个、multiset等秧骑。
RBTree也是函數(shù)式語言中最常用的持久數(shù)據(jù)結(jié)構(gòu)之一，在計(jì)算幾何中也有重要作用禁偎。值得一提的是腿堤，Java 8中HashMap的實(shí)現(xiàn)也因?yàn)橛肦BTree取代鏈表阀坏，性能有所提升如暖。
RBTree的定義
RBTree的定義如下:
1. 任何一個(gè)節(jié)點(diǎn)都有顏色，黑色或者紅色
2. 根節(jié)點(diǎn)是黑色的
3. 父子節(jié)點(diǎn)之間不能出現(xiàn)兩個(gè)連續(xù)的紅節(jié)點(diǎn)忌堂，但是可以出現(xiàn)連續(xù)的黑色節(jié)點(diǎn)
4. 任何一個(gè)節(jié)點(diǎn)向下遍歷到其子孫的葉子節(jié)點(diǎn)盒至，所經(jīng)過的黑節(jié)點(diǎn)個(gè)數(shù)必須相等
5. 空節(jié)點(diǎn)被認(rèn)為是黑色的
RBTree在理論上還是一棵BST樹，但是它在對(duì)BST的插入和刪除操作時(shí)會(huì)維持樹的平衡士修，即保證樹的高度在[logN,logN+1]（理論上枷遂，極端的情況下可以出現(xiàn)RBTree的高度達(dá)到2*logN，但實(shí)際上很難遇到）棋嘲。這樣RBTree的查找時(shí)間復(fù)雜度始終保持在O(logN)從而接近于理想的BST酒唉。RBTree的刪除和插入操作的時(shí)間復(fù)雜度也是O(logN)。RBTree的查找操作就是BST的查找操作沸移。
RBTree的旋轉(zhuǎn)操作
旋轉(zhuǎn)操作(Rotate)的目的是使節(jié)點(diǎn)顏色符合定義痪伦，讓RBTree的高度達(dá)到平衡。
Rotate分為left-rotate（左旋）和right-rotate（右旋）雹锣，區(qū)分左旋和右旋的方法是：待旋轉(zhuǎn)的節(jié)點(diǎn)從左邊上升到父節(jié)點(diǎn)就是右旋网沾，待旋轉(zhuǎn)的節(jié)點(diǎn)從右邊上升到父節(jié)點(diǎn)就是左旋。即蕊爵，左旋節(jié)點(diǎn)的父節(jié)點(diǎn)點(diǎn)從左邊下沉成為子節(jié)點(diǎn)為左旋辉哥，右旋節(jié)點(diǎn)的父節(jié)點(diǎn)從右邊下沉成為子節(jié)點(diǎn)為右旋
RBTree的查找操作
參考樹:二叉樹
RBTree的插入操作
RBTree的插入與BST的插入方式是一致的，只不過是在插入過后攒射，可能會(huì)導(dǎo)致樹的不平衡醋旦，這時(shí)就需要對(duì)樹進(jìn)行旋轉(zhuǎn)操作和顏色修復(fù)（在這里簡(jiǎn)稱插入修復(fù)），使得它符合RBTree的定義会放。
新插入的節(jié)點(diǎn)是紅色的浑度，插入修復(fù)操作如果遇到父節(jié)點(diǎn)的顏色為黑則修復(fù)操作結(jié)束。也就是說鸦概，只有在父節(jié)點(diǎn)為紅色節(jié)點(diǎn)的時(shí)候是需要插入修復(fù)操作的箩张。
插入修復(fù)操作分為以下的三種情況甩骏，而且新插入的節(jié)點(diǎn)的父節(jié)點(diǎn)都是紅色的：
叔叔節(jié)點(diǎn)也為紅色。
叔叔節(jié)點(diǎn)為空先慷，且祖父節(jié)點(diǎn)饮笛、父節(jié)點(diǎn)和新節(jié)點(diǎn)處于一條斜線上。
叔叔節(jié)點(diǎn)為空论熙，且祖父節(jié)點(diǎn)福青、父節(jié)點(diǎn)和新節(jié)點(diǎn)不處于一條斜線上。
插入操作-case 1
case 1的操作是將父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)與祖父節(jié)點(diǎn)的顏色互換脓诡，這樣就符合了RBTRee的定義无午。即維持了高度的平衡，修復(fù)后顏色也符合RBTree定義的第三條祝谚。下圖中宪迟，操作完成后A節(jié)點(diǎn)變成了新的節(jié)點(diǎn)。如果A節(jié)點(diǎn)的父節(jié)點(diǎn)不是黑色的話（所以需要向上遍歷所有節(jié)點(diǎn)顏色）交惯，則繼續(xù)做修復(fù)操作次泽。
插入操作-case 2
case 2的操作是將B節(jié)點(diǎn)進(jìn)行右旋操作，并且和父節(jié)點(diǎn)A互換顏色席爽。通過該修復(fù)操作RBTRee的高度和顏色都符合紅黑樹的定義意荤。如果B和C節(jié)點(diǎn)都是右節(jié)點(diǎn)的話，只要將操作變成左旋就可以了只锻。
插入操作-case 3
case 3的操作是將C節(jié)點(diǎn)進(jìn)行左旋玖像，這樣就從case 3轉(zhuǎn)換成case 2了，然后針對(duì)case 2進(jìn)行操作處理就行了齐饮。case 2操作做了一個(gè)右旋操作和顏色互換來達(dá)到目的捐寥。如果樹的結(jié)構(gòu)是下圖的鏡像結(jié)構(gòu)，則只需要將對(duì)應(yīng)的左旋變成右旋沈矿，右旋變成左旋即可上真。
插入操作的總結(jié)
插入后的修復(fù)操作是一個(gè)向root節(jié)點(diǎn)回溯的操作，一旦牽涉的節(jié)點(diǎn)都符合了紅黑樹的定義羹膳，修復(fù)操作結(jié)束睡互。之所以會(huì)向上回溯是由于case 1操作會(huì)將父節(jié)點(diǎn)，叔叔節(jié)點(diǎn)和祖父節(jié)點(diǎn)進(jìn)行換顏色陵像，有可能會(huì)導(dǎo)致祖父節(jié)點(diǎn)不平衡(紅黑樹定義3)就珠。這個(gè)時(shí)候需要對(duì)祖父節(jié)點(diǎn)為起點(diǎn)進(jìn)行調(diào)節(jié)（向上回溯）。
祖父節(jié)點(diǎn)調(diào)節(jié)后如果還是遇到它的祖父顏色問題醒颖，操作就會(huì)繼續(xù)向上回溯妻怎，直到root節(jié)點(diǎn)為止，根據(jù)定義root節(jié)點(diǎn)永遠(yuǎn)是黑色的泞歉。在向上的追溯的過程中逼侦，針對(duì)插入的3中情況進(jìn)行調(diào)節(jié)匿辩。直到符合紅黑樹的定義為止。直到牽涉的節(jié)點(diǎn)都符合了紅黑樹的定義榛丢，修復(fù)操作結(jié)束铲球。
如果上面的3中情況如果對(duì)應(yīng)的操作是在右子樹上，做對(duì)應(yīng)的鏡像操作就是了晰赞。
刪除節(jié)點(diǎn)
刪除操作首先需要做的也是BST的刪除操作稼病，刪除操作會(huì)刪除對(duì)應(yīng)的節(jié)點(diǎn)，如果是葉子節(jié)點(diǎn)就直接刪除掖鱼，如果是非葉子節(jié)點(diǎn)然走，會(huì)用對(duì)應(yīng)的中序遍歷的后繼節(jié)點(diǎn)來頂替要?jiǎng)h除節(jié)點(diǎn)的位置。刪除后就需要做刪除修復(fù)操作戏挡，使的樹符合紅黑樹的定義芍瑞，符合定義的紅黑樹高度是平衡的。
刪除修復(fù)操作在遇到被刪除的節(jié)點(diǎn)是紅色節(jié)點(diǎn)或者到達(dá)root節(jié)點(diǎn)時(shí)增拥，修復(fù)操作完畢啄巧。
刪除修復(fù)操作是針對(duì)刪除黑色節(jié)點(diǎn)（葉子節(jié)點(diǎn)為紅色節(jié)點(diǎn)）才有的寻歧，當(dāng)黑色節(jié)點(diǎn)被刪除后會(huì)讓整個(gè)樹不符合RBTree的定義的第四條掌栅。需要做的處理是從兄弟節(jié)點(diǎn)上借調(diào)黑色的節(jié)點(diǎn)過來，如果兄弟節(jié)點(diǎn)沒有黑節(jié)點(diǎn)可以借調(diào)的話码泛，就只能往上追溯猾封，將每一級(jí)的黑節(jié)點(diǎn)數(shù)減去一個(gè)，使得整棵樹符合紅黑樹的定義噪珊。
刪除操作的總體思想是從兄弟節(jié)點(diǎn)借調(diào)黑色節(jié)點(diǎn)使樹保持局部的平衡晌缘，如果局部的平衡達(dá)到了，就看整體的樹是否是平衡的痢站，如果不平衡就接著向上追溯調(diào)整磷箕。
代碼引申
CompareTo 和 equals 和 == 區(qū)別
CompareTo
CompareTo 比較兩個(gè)類對(duì)象。就不能直接通過>,<進(jìn)行比較阵难，引用對(duì)象不是基本數(shù)據(jù)類型岳枷。兩個(gè)對(duì)象進(jìn)行比較返回 “0”是 相等，正數(shù)是 大于呜叫，負(fù)數(shù)是小于
==
當(dāng)復(fù)合數(shù)據(jù)類型用（==）進(jìn)行比較空繁，比較的是他們?cè)趦?nèi)存中的存放地址。
equals
當(dāng)復(fù)合數(shù)據(jù)類型之間進(jìn)行equals比較時(shí)朱庆，這個(gè)方法的初始行為是比較對(duì)象在堆內(nèi)存中的地址盛泡，但在一些諸如String,Integer,Date類中把Object中的這個(gè)方法覆蓋了，作用被覆蓋為比較內(nèi)容是否相同娱颊。
Java 中 比較兩個(gè)類對(duì)象傲诵。就不能直接通過>,<進(jìn)行比較凯砍，引用對(duì)象不是基本數(shù)據(jù)類型
Java中很多類也都有CompareTo方法，甚至于排序算法的底層組成也是依賴于比較的拴竹，而這個(gè)比較就是依賴于各種數(shù)據(jù)類型的CompareTo或者Compare方法果覆。Java中所有的compareTo方法都源于一個(gè)共同的接口，那就是Comparable殖熟。這個(gè)接口只有一個(gè)方法局待，那就是CompareTo。所有想要具有比較功能的類菱属，都建議實(shí)現(xiàn)這個(gè)接口钳榨，而非是自己定義這個(gè)功能，這是面向?qū)ο蟮母拍睿▽⒕哂邢嗤δ艿氖挛锍橄蟮揭粋€(gè)共同的類或接口）纽门，并且為了多態(tài)也建議通過實(shí)現(xiàn)接口來進(jìn)行向上轉(zhuǎn)型薛耻，通過接口來操作具體實(shí)現(xiàn)，這也是面向接口編程要求我們做的赏陵。
