2019年7月26日
前言：樹是一種數(shù)據(jù)結(jié)構(gòu)的組織方式，不同的數(shù)據(jù)組織方式在數(shù)據(jù)的增刪改查方面性能上有差異。例如ArrayList增刪慢，其時間復(fù)雜度O(n），修改查詢快，時間復(fù)雜度為O(1)；LinkedList正好與ArrayList相反；而紅黑樹在增刪改查的時間復(fù)雜度均為O(log(n))。接下來，是我對樹的簡單總結(jié)和理解。
全文缺少配圖，有時間補(bǔ)上
概念理解
樹：從直接前繼和直接后繼個數(shù)角度，可以這樣定義， 0到1個直接前繼，0到n個直接后繼，其中n>=2。
節(jié)點(diǎn)：樹就是由有限節(jié)點(diǎn)組成的一個具有層次關(guān)系的集合，數(shù)據(jù)就存在這些節(jié)點(diǎn)中。
根節(jié)點(diǎn)：最頂上的一個節(jié)點(diǎn)，沒有父節(jié)點(diǎn)。
子節(jié)點(diǎn)：兩個相連節(jié)點(diǎn)的關(guān)系。
葉子節(jié)點(diǎn)：某個節(jié)點(diǎn)下方?jīng)]有任何分叉。
節(jié)點(diǎn)的高度：從某個節(jié)點(diǎn)出發(fā)，到葉子節(jié)點(diǎn)為止，最長簡單路徑上邊的條數(shù)，稱為該節(jié)點(diǎn)高度。
節(jié)點(diǎn)的深度：從根節(jié)點(diǎn)出發(fā)，到某節(jié)點(diǎn)邊的條數(shù)，稱為該節(jié)點(diǎn)的深度。
二叉樹：至多有兩個子節(jié)點(diǎn)的樹，平衡二叉樹、二叉查找樹、紅黑樹都是一種特殊的二叉樹。
平衡二叉樹性質(zhì)：
（1）樹的左右高度查不能超過1；
（2）任何往下遞歸的左子樹和右子樹，必須符合第一條性質(zhì)；
（3）沒有任何節(jié)點(diǎn)的空樹或只有根節(jié)點(diǎn)的樹也是平衡二叉樹。
二叉查找樹性質(zhì)：
（1）對于任意節(jié)點(diǎn)來說，它的左子樹上所有節(jié)點(diǎn)的值都小于他，而他的右子樹上所有節(jié)點(diǎn)都大于他。
遍歷所有節(jié)點(diǎn)的常用方式有三種：前序遍歷、中序遍歷、后序遍歷。
（1）在任何遞歸子樹中，左節(jié)點(diǎn)一定在右節(jié)點(diǎn)之前遍歷。
（2）前序、中序、后序，僅指根節(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)；
二叉查找樹由于數(shù)據(jù)不斷增加或刪除容易失衡，因此為了保持二叉樹重要的平衡性，有很多算法實現(xiàn)，比如AVL樹、紅黑樹等
AVL樹：
AVL樹是一種平衡二叉查找樹，在增加或刪除節(jié)點(diǎn)后通過樹形旋轉(zhuǎn)重新達(dá)到平衡。
右旋，以某個節(jié)點(diǎn)為中心，將它沉入當(dāng)前右子節(jié)點(diǎn)的位置，而讓當(dāng)前的左子節(jié)點(diǎn)作為新樹的根節(jié)點(diǎn)，也稱為順時針旋轉(zhuǎn)。
左旋，以某個節(jié)點(diǎn)為中心，將它沉入當(dāng)前左子節(jié)點(diǎn)的位置，而讓當(dāng)前右子節(jié)點(diǎn)作為新樹的跟節(jié)點(diǎn)，也稱為逆時針旋轉(zhuǎn)。
紅黑樹：一種特殊的二叉查找樹
與AVL樹相比，紅黑樹并不追求所有遞歸子樹的高度差不超過1，而是保證從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長路徑不超過最短路徑的2倍。
相比二叉查找樹，有5個約束條件：
（1）節(jié)點(diǎn)只能是紅色或黑色。
（2）根節(jié)點(diǎn)必須是黑色。
（3）所有NIL節(jié)點(diǎn)都是黑色的。NIL，即葉子節(jié)點(diǎn)下掛的兩個虛節(jié)點(diǎn)。
（4）一條路徑上不能出現(xiàn)相鄰的兩個紅色節(jié)點(diǎn)。
（5）在任何遞歸子樹內(nèi)，根節(jié)點(diǎn)到葉子節(jié)點(diǎn)所有路徑上包含相同數(shù)目的黑色節(jié)點(diǎn)。
總結(jié)即是“有紅必有黑，紅紅不相連”，上述5個約束條件保證了：
（1）紅黑樹的新增、刪除、查找的最壞時間復(fù)雜度均為O(logn);
（2）如果一個樹的左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)不存在，則均認(rèn)定為黑色；
（3）紅黑樹的任何旋轉(zhuǎn)在3次之內(nèi)均可完成。（這個是怎么計算出來的？？？）
紅黑樹與AVL樹的比較
這里還需更加詳細(xì)分析兩者的區(qū)別
面對頻繁的插入和刪除，紅黑樹更為合適；
面對低頻修改、大量查詢，AVL樹更合適。
