上學(xué)的時(shí)候是學(xué)過數(shù)據(jù)結(jié)構(gòu)的羔沙。躺涝。可是對(duì)于二叉樹扼雏，提起來總是一臉懵逼坚嗜。總是看著黑板上一堆圈圈杠杠诗充。苍蔬。什么前序，中序蝴蜓，后續(xù)遍歷碟绑，很是莫名俺猿。。我在想這到底在干什么格仲？押袍？？因此埋下坑凯肋，最近看java基礎(chǔ)谊惭，發(fā)現(xiàn)一些紅黑樹的應(yīng)用，對(duì)二叉樹若有所悟侮东。
首先二叉樹結(jié)構(gòu)的基本參數(shù)圈盔，自己（節(jié)點(diǎn)），父節(jié)點(diǎn)苗桂，左子節(jié)點(diǎn)和右子節(jié)點(diǎn)药磺；
然后來看二叉樹能干什么；來說說我是怎么發(fā)現(xiàn)的煤伟，因?yàn)橹皩?duì)這個(gè)概念一直很模糊癌佩。。
首先便锨，set和treeSet的區(qū)別围辙，treeSet是有序的，然后map和TreeMap的區(qū)別放案，TreeMap是有序的姚建，因此我認(rèn)為Tree就是個(gè)排序方法；
那怎么排序呢吱殉，要排序肯定對(duì)象實(shí)現(xiàn)了比較方法comparable掸冤，然后二叉樹結(jié)構(gòu)就是最簡(jiǎn)單的，N個(gè)對(duì)象比大小友雳，第一個(gè)就是父節(jié)點(diǎn)稿湿，然后第二個(gè)數(shù)如果比第一個(gè)小就是左子樹，比第一個(gè)大就是右子樹押赊，依次類推饺藤。。
說完二叉樹流礁，再說java為什么要用紅黑樹涕俗，所謂紅黑樹就是平衡二叉樹的特殊實(shí)現(xiàn)，二叉樹為什么要平衡呢神帅？
舉例再姑，如果N個(gè)數(shù)是從小到大的。找御。那個(gè)二叉樹結(jié)構(gòu)不就成了一條斜線嗎询刹。谜嫉。如果要找其中一個(gè)數(shù)，豈不是要把每個(gè)節(jié)點(diǎn)都過一遍凹联。。
所以平衡二叉樹要做的是讓根節(jié)點(diǎn)左右邊的節(jié)點(diǎn)數(shù)差不多哆档。
比如一條直線的二叉樹蔽挠，如果從中間折斷，它依然滿足左邊小瓜浸，右邊大的基本特性澳淑，但是如果查詢一個(gè)值，至少我們可以減少一半的查詢效率插佛；因?yàn)橹虚g這個(gè)數(shù)是中間值杠巡，如果x比中間值大，那么這個(gè)數(shù)肯定在右邊雇寇，反之亦然
當(dāng)然這種平衡二叉樹數(shù)據(jù)結(jié)構(gòu)的增刪改查的效率是比不上鏈表氢拥，但要保證數(shù)據(jù)的有序性，還要算上效率锨侯，那平衡二叉樹非常nice
既然平衡二叉樹已經(jīng)如此優(yōu)秀嫩海，那么紅黑樹又是為什么出現(xiàn)呢？
我們?cè)趯?shí)現(xiàn)平衡二叉樹時(shí)囚痴，隨著數(shù)據(jù)量的增大叁怪，有時(shí)一個(gè)子節(jié)點(diǎn)的增加可能會(huì)讓整個(gè)樹發(fā)現(xiàn)大范圍的翻轉(zhuǎn)，那么如果標(biāo)識(shí)紅的子節(jié)點(diǎn)是黑深滚，黑的子節(jié)點(diǎn)是紅奕谭，將二叉樹一層層分開，為了滿足紅黑樹的特性痴荐，平衡二叉樹必然不能發(fā)生大范圍翻轉(zhuǎn)血柳，缺點(diǎn)是紅黑樹的查詢速率沒有平衡樹高，但是修改蹬昌，刪除操作遠(yuǎn)優(yōu)于平衡二叉樹
再說說前種后序遍歷混驰，既然二叉樹是有序的，那我們就把一串?dāng)?shù)字按從小到大輸出皂贩，或者從大到小輸出栖榨。。但是直接一串?dāng)?shù)想不出來明刷，網(wǎng)上隨便找個(gè)圖
先序 abdefcghi
中序 dbefaghci
后序 defbhgica
如果滿足大小關(guān)系 婴栽，那么有 B<A,D<B,F>B,E<F,C>A,G<C.I>C,H>G
再說推斷關(guān)系，D和E誰更小辈末，如果E<D那么E應(yīng)該是D的左子節(jié)點(diǎn)愚争，然后不是映皆，說明D<E；
那么轰枝，正確的從小到大的順序是DBEFAGHC 即是二叉樹的中序遍歷
至于先序和后序捅彻，我倒是沒什么想法，百度后鞍陨，發(fā)現(xiàn)先序用來展示文件夾結(jié)構(gòu),如果用來展示文件夾步淹，a下面有bc，但是b下還有文件诚撵，所以先不展示c,b下面有df,f下有e所有先e后f,再之后是本該是c可c下還有g(shù)缭裆，g下還有h，所以為ghc寿烟，最后是g平級(jí)的i
后序是用來計(jì)算文件大小,這個(gè)暫時(shí)理解不了澈驼，可能展示了自底向上的一種統(tǒng)計(jì)方式吧。筛武。
至于紅黑樹具體怎么實(shí)現(xiàn)缝其，https://www.cnblogs.com/skywang12345/p/3624343.html這篇文章講的非常清楚
