樹(shù)
樹(shù)晒夹，這種結(jié)構(gòu)在計(jì)算機(jī)領(lǐng)域應(yīng)用非常廣泛，便于管理和查找僚稿。
樹(shù)的關(guān)鍵在與“分治”思想凡桥。我理解的分治思想就是將事務(wù)進(jìn)行分類(lèi)歸納，使得具有規(guī)律或者特征的來(lái)把數(shù)據(jù)或者事務(wù)聯(lián)系起來(lái)蚀同，這樣在查找或者使用的時(shí)候就可以有目的的忽略不需要浪費(fèi)精力的部分缅刽，從而提高效率。
例如：文件系統(tǒng)（B+樹(shù)）蠢络，DB索引（B+樹(shù)衰猛、哈希樹(shù)），treemap(紅黑樹(shù))刹孔，堆（完全二叉樹(shù)）
二叉樹(shù)
每個(gè)節(jié)點(diǎn)只有兩個(gè)子節(jié)點(diǎn)啡省。
二叉查找樹(shù)，關(guān)鍵點(diǎn)是樹(shù)的深度髓霞。
堆結(jié)構(gòu)就是一個(gè)完全二叉樹(shù)卦睹，（gc）。
二叉樹(shù)有很多種：紅黑樹(shù)酸茴，AVL樹(shù)分预，堆
AVL樹(shù)
1.本身首先是一棵二叉搜索樹(shù)。
2.帶有平衡條件：每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度之差的絕對(duì)值（平衡因子）最多為1薪捍。
堆
1笼痹、二叉樹(shù)的深度為h，除第 h 層外酪穿，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)
2凳干、第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊
紅黑樹(shù)
樹(shù)的旋轉(zhuǎn)
1、左旋
圖片引用http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html
2被济、右旋
圖片引用http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html
紅黑樹(shù)性質(zhì)
1救赐、任何一個(gè)節(jié)點(diǎn)都有顏色，黑色或者紅色
2、根節(jié)點(diǎn)是黑色的
3经磅、紅節(jié)點(diǎn)的子節(jié)點(diǎn)必須為黑節(jié)點(diǎn)
4泌绣、任何一個(gè)節(jié)點(diǎn)向下遍歷到其子孫的葉子節(jié)點(diǎn)，所經(jīng)過(guò)的黑節(jié)點(diǎn)個(gè)數(shù)必須相等
5预厌、空節(jié)點(diǎn)被認(rèn)為是黑色的
6阿迈、新插入節(jié)點(diǎn)所帶顏色為紅色，需要根據(jù)以上性質(zhì)進(jìn)行調(diào)整
二叉查找樹(shù)的遍歷轧叽、查找苗沧，還有基于兩者的排序、contain等方法的實(shí)現(xiàn)炭晒，對(duì)于所有的類(lèi)型的二叉查找樹(shù)都是相同的待逞。
插入
對(duì)于二叉查找樹(shù)的插入操作基本操作都是一樣的，都是先通過(guò)二分查找法找到所需要插入數(shù)據(jù)對(duì)應(yīng)的位置网严，插入節(jié)點(diǎn)识樱。關(guān)鍵的不同是：不同的查找樹(shù)在插入節(jié)點(diǎn)后，為了保持相應(yīng)的性質(zhì)所需進(jìn)行的在平衡操作屿笼。
1牺荠、對(duì)于新節(jié)點(diǎn)的插入有如下三個(gè)關(guān)鍵地方：
(1)插入新節(jié)點(diǎn)總是紅色節(jié)點(diǎn) 。
(2)如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色, 能維持性質(zhì) 驴一。
(3)如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色, 破壞了性質(zhì). 故插入算法就是通過(guò)重新著色或旋轉(zhuǎn), 來(lái)維持性質(zhì) 休雌。
由此得出：只有新插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色節(jié)點(diǎn)的時(shí)候需要來(lái)進(jìn)行調(diào)整。
2肝断、紅黑樹(shù)插入
(1)(2)(3)
3杈曲、紅黑樹(shù)插入的再平衡操作
父節(jié)點(diǎn)為紅色節(jié)點(diǎn)的場(chǎng)景分析
(1)(2)(3)
刪除
刪除的過(guò)程也同插入操作，首先通過(guò)二分查找找到對(duì)應(yīng)的節(jié)點(diǎn)胸懈，刪除后再平衡
1担扑、將紅黑樹(shù)當(dāng)作一顆二叉查找樹(shù)，將節(jié)點(diǎn)刪除趣钱。
(1) 被刪除節(jié)點(diǎn)沒(méi)有兒子(葉節(jié)點(diǎn))涌献，直接將該節(jié)點(diǎn)刪除就OK了。
(2) 被刪除節(jié)點(diǎn)只有一個(gè)兒子首有，直接刪除該節(jié)點(diǎn)燕垃，并用該節(jié)點(diǎn)的唯一子節(jié)點(diǎn)頂替它的位置與被刪節(jié)點(diǎn)的父節(jié)點(diǎn)相連。
(3) 被刪除節(jié)點(diǎn)有兩個(gè)兒子井联，先找出它的后繼節(jié)點(diǎn)卜壕；然后把“它的后繼節(jié)點(diǎn)的內(nèi)容”復(fù)制給“該節(jié)點(diǎn)的內(nèi)容”；之后烙常，刪除“它的后繼節(jié)點(diǎn)”轴捎。在這里，后繼節(jié)點(diǎn)相當(dāng)于替身，在將后繼節(jié)點(diǎn)的內(nèi)容復(fù)制給"被刪除節(jié)點(diǎn)"之后侦副，再將后繼節(jié)點(diǎn)刪除侦锯。這樣就巧妙的將問(wèn)題轉(zhuǎn)換為"刪除后繼節(jié)點(diǎn)"的情況了，下面就考慮后繼節(jié)點(diǎn)秦驯。 在"被刪除節(jié)點(diǎn)"有兩個(gè)非空子節(jié)點(diǎn)的情況下率触，它的后繼節(jié)點(diǎn)只可能是沒(méi)有兒子的葉節(jié)點(diǎn)或者只有一個(gè)右兒子。若沒(méi)有兒子汇竭，則按"情況① "進(jìn)行處理；若只有一個(gè)兒子穴张，則按"情況② "進(jìn)行處理细燎。
(1)(2)(3)(4)
