2019年7月26日
前言：樹是一種數(shù)據(jù)結構的組織方式谍咆，不同的數(shù)據(jù)組織方式在數(shù)據(jù)的增刪改查方面性能上有差異堕伪。例如ArrayList增刪慢挤渔，其時間復雜度O(n），修改查詢快先慷，時間復雜度為O(1)饮笛；LinkedList正好與ArrayList相反；而紅黑樹在增刪改查的時間復雜度均為O(log(n))论熙。接下來福青，是我對樹的簡單總結和理解。
全文缺少配圖脓诡，有時間補上

概念理解

樹：從直接前繼和直接后繼個數(shù)角度无午，可以這樣定義， 0到1個直接前繼祝谚，0到n個直接后繼宪迟，其中n>=2。
節(jié)點：樹就是由有限節(jié)點組成的一個具有層次關系的集合交惯，數(shù)據(jù)就存在這些節(jié)點中次泽。
根節(jié)點：最頂上的一個節(jié)點穿仪，沒有父節(jié)點。
子節(jié)點：兩個相連節(jié)點的關系意荤。
葉子節(jié)點：某個節(jié)點下方?jīng)]有任何分叉啊片。
節(jié)點的高度：從某個節(jié)點出發(fā)，到葉子節(jié)點為止玖像，最長簡單路徑上邊的條數(shù)紫谷，稱為該節(jié)點高度。
節(jié)點的深度：從根節(jié)點出發(fā)捐寥，到某節(jié)點邊的條數(shù)笤昨，稱為該節(jié)點的深度。

二叉樹：至多有兩個子節(jié)點的樹握恳，平衡二叉樹咬腋、二叉查找樹、紅黑樹都是一種特殊的二叉樹睡互。

平衡二叉樹性質(zhì)：

（1）樹的左右高度查不能超過1；
（2）任何往下遞歸的左子樹和右子樹陵像，必須符合第一條性質(zhì)就珠；
（3）沒有任何節(jié)點的空樹或只有根節(jié)點的樹也是平衡二叉樹。

二叉查找樹性質(zhì)：

（1）對于任意節(jié)點來說醒颖，它的左子樹上所有節(jié)點的值都小于他妻怎，而他的右子樹上所有節(jié)點都大于他。
遍歷所有節(jié)點的常用方式有三種：前序遍歷泞歉、中序遍歷逼侦、后序遍歷。
（1）在任何遞歸子樹中腰耙，左節(jié)點一定在右節(jié)點之前遍歷榛丢。
（2）前序、中序挺庞、后序晰赞，僅指根節(jié)點在遍歷時的為止順序。
前序遍歷順序：根節(jié)點选侨、左節(jié)點掖鱼、右節(jié)點；
中序遍歷順序：左節(jié)點援制、根節(jié)點戏挡、右節(jié)點；
后序遍歷順序：做節(jié)點晨仑、右節(jié)點褐墅、根節(jié)點拆檬；
二叉查找樹由于數(shù)據(jù)不斷增加或刪除容易失衡，因此為了保持二叉樹重要的平衡性掌栅，有很多算法實現(xiàn)秩仆，比如AVL樹、紅黑樹等

AVL樹：

AVL樹是一種平衡二叉查找樹猾封，在增加或刪除節(jié)點后通過樹形旋轉(zhuǎn)重新達到平衡澄耍。
右旋，以某個節(jié)點為中心晌缘，將它沉入當前右子節(jié)點的位置齐莲，而讓當前的左子節(jié)點作為新樹的根節(jié)點，也稱為順時針旋轉(zhuǎn)磷箕。
左旋选酗，以某個節(jié)點為中心，將它沉入當前左子節(jié)點的位置岳枷，而讓當前右子節(jié)點作為新樹的跟節(jié)點芒填，也稱為逆時針旋轉(zhuǎn)。

紅黑樹：一種特殊的二叉查找樹

與AVL樹相比空繁，紅黑樹并不追求所有遞歸子樹的高度差不超過1殿衰，而是保證從根節(jié)點到葉子節(jié)點的最長路徑不超過最短路徑的2倍。
相比二叉查找樹盛泡，有5個約束條件：
（1）節(jié)點只能是紅色或黑色闷祥。
（2）根節(jié)點必須是黑色。
（3）所有NIL節(jié)點都是黑色的傲诵。NIL凯砍，即葉子節(jié)點下掛的兩個虛節(jié)點。
（4）一條路徑上不能出現(xiàn)相鄰的兩個紅色節(jié)點拴竹。
（5）在任何遞歸子樹內(nèi)悟衩，根節(jié)點到葉子節(jié)點所有路徑上包含相同數(shù)目的黑色節(jié)點。

總結即是“有紅必有黑栓拜，紅紅不相連”局待，上述5個約束條件保證了：
（1）紅黑樹的新增、刪除菱属、查找的最壞時間復雜度均為O(logn);
（2）如果一個樹的左子節(jié)點或者右子節(jié)點不存在钳榨，則均認定為黑色；
（3）紅黑樹的任何旋轉(zhuǎn)在3次之內(nèi)均可完成纽门。（這個是怎么計算出來的薛耻？？赏陵？）

紅黑樹與AVL樹的比較

這里還需更加詳細分析兩者的區(qū)別
面對頻繁的插入和刪除饼齿，紅黑樹更為合適饲漾；
面對低頻修改、大量查詢缕溉，AVL樹更合適考传。