二叉樹的定義
二叉樹是樹形結(jié)構(gòu)的一個(gè)重要類型。 許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹的形式垄提，即使是一般的樹也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹顯得特別重要器虾。
二叉樹(BinaryTree)由一個(gè)結(jié)點(diǎn)及兩棵互不相交的躬窜、分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成浇垦。下圖中展現(xiàn)了五種不同基本形態(tài)的二叉樹。
(a)?為空樹
(b)?為僅有一個(gè)結(jié)點(diǎn)的二叉樹
(c)?是僅有左子樹而右子樹為空的二叉樹
(d)?是僅有右子樹而左子樹為空的二叉樹
(e)?是左荣挨、右子樹均非空的二叉樹男韧。
?
這里應(yīng)特別注意的是，二叉樹的左子樹和右子樹是嚴(yán)格區(qū)分并且不能隨意顛倒的默垄，圖?(c)?與圖?(d)?就是兩棵不同的二叉樹此虑。
排序二叉樹
排序二叉樹特性如下：
1. 左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值
2. 右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值
比如：我們要將數(shù)據(jù)【14,12,23,4,16,13, 8,,3】存儲(chǔ)到排序二叉樹中：
排序二叉樹本身實(shí)現(xiàn)了排序功能，可以快速檢索口锭。但如果插入的節(jié)點(diǎn)集本身就是有序的朦前，要么是由小到大排列，要么是由大到小排列鹃操，那么最后得到的排序二叉樹將變成普通的鏈表韭寸，其檢索效率就會(huì)很差。 比如上面的數(shù)據(jù)【14,12,23,4,16,13, 8,,3】荆隘，我們先進(jìn)行排序變成：【3,4,8,12,13,14,16,23】恩伺，然后存儲(chǔ)到排序二叉樹中，顯然就變成了鏈表椰拒。
平衡二叉樹（AVL）
為了避免出現(xiàn)一邊倒的存儲(chǔ)晶渠，科學(xué)家提出了“平衡二叉樹”。
在平衡二叉樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為1燃观，所以它也被稱為高度平衡樹褒脯。 增加和刪除節(jié)點(diǎn)可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個(gè)樹。
節(jié)點(diǎn)的平衡因子是它的左子樹的高度減去它的右子樹的高度（有時(shí)相反）仪壮。帶有平衡因子1憨颠、0或 -1的節(jié)點(diǎn)被認(rèn)為是平衡的。帶有平衡因子 -2或2的節(jié)點(diǎn)被認(rèn)為是不平衡的，并需要重新平衡這個(gè)樹爽彤。
比如养盗，我們存儲(chǔ)排好序的數(shù)據(jù)【3,4,8,12,13,14,16,23】，增加節(jié)點(diǎn)如果出現(xiàn)不平衡适篙，則通過節(jié)點(diǎn)的左旋或右旋往核，重新平衡樹結(jié)構(gòu)，最終平衡二叉樹如下：
平衡二叉樹追求絕對(duì)平衡嚷节，實(shí)現(xiàn)起來比較麻煩聂儒，每次插入新節(jié)點(diǎn)需要做的旋轉(zhuǎn)操作次數(shù)不能預(yù)知。
紅黑二叉樹
紅黑二叉樹(簡(jiǎn)稱：紅黑樹)硫痰，它首先是一顆二叉樹衩婚，同時(shí)也是一顆自平衡的排序二叉樹。
紅黑樹在原有的排序二叉樹增加了如下幾個(gè)要求：
性質(zhì)?1：每個(gè)節(jié)點(diǎn)要么是紅色效斑，要么是黑色非春。
性質(zhì)?2：根節(jié)點(diǎn)永遠(yuǎn)是黑色的。
性質(zhì)?3：所有的葉節(jié)點(diǎn)都是空節(jié)點(diǎn)（即?null）缓屠，并且是黑色的奇昙。
性質(zhì)?4：每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。（從每個(gè)葉子到根的路徑上不會(huì)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）
性質(zhì)?5：從任一節(jié)點(diǎn)到其子樹中每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)敌完。
這些約束強(qiáng)制了紅黑樹的關(guān)鍵性質(zhì)：從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)储耐。這樣就讓樹大致上是平衡的。
紅黑樹是一個(gè)更高效的檢索二叉樹滨溉，JDK?提供的集合類?TreeMap什湘、TreeSet?本身就是一個(gè)紅黑樹的實(shí)現(xiàn)。
【圖】一個(gè)典型的紅黑樹（考慮書本印刷問題业踏，淺色表示紅色禽炬，深色表示紅色）
紅黑樹的基本操作：插入、刪除勤家、左旋腹尖、右旋、著色伐脖。?每插入或者刪除一個(gè)節(jié)點(diǎn)热幔，可能會(huì)導(dǎo)致樹不在符合紅黑樹的特征，需要進(jìn)行修復(fù)讼庇，進(jìn)行?“左旋绎巨、右旋、著色”操作蠕啄，使樹繼續(xù)保持紅黑樹的特性场勤。
老鳥建議
本節(jié)關(guān)于二叉樹的介紹戈锻，僅限于了解。實(shí)際開發(fā)中和媳，直接用到的概率非常低格遭。普通企業(yè)面試中也較少。不過留瞳，極有可能出現(xiàn)在BAT等企業(yè)筆試中拒迅。建議，想進(jìn)BAT等名企的童鞋她倘，專門準(zhǔn)備一下數(shù)據(jù)結(jié)構(gòu)相關(guān)的知識(shí)璧微。
TreeMap的使用和底層實(shí)現(xiàn)
TreeMap是紅黑二叉樹的典型實(shí)現(xiàn)。我們打開TreeMap的源碼硬梁，發(fā)現(xiàn)里面有一行核心代碼：
private?transient?Entry<K,V>?root?=?null;
?root用來存儲(chǔ)整個(gè)樹的根節(jié)點(diǎn)前硫。我們繼續(xù)跟蹤Entry（是TreeMap的內(nèi)部類）的代碼：
static?final?class?? Entry<K,V>?implements?? Map.Entry<K,V> {
??? K?key;
??????? V?value;
??????? Entry<K,V>?left?=?null;
??????? Entry<K,V>?right?=?null;
??????? Entry<K,V>?parent;
????????boolean?color?= ? BLACK;
}
可以看到里面存儲(chǔ)了本身數(shù)據(jù)、左節(jié)點(diǎn)靶溜、右節(jié)點(diǎn)开瞭、父節(jié)點(diǎn)懒震、以及節(jié)點(diǎn)顏色罩息。?TreeMap的put()/remove()方法大量使用了紅黑樹的理論。本書限于篇幅个扰，不再展開瓷炮。需要了解更深入的，可以參考專門的數(shù)據(jù)結(jié)構(gòu)書籍递宅。
TreeMap和HashMap實(shí)現(xiàn)了同樣的接口Map娘香，因此，用法對(duì)于調(diào)用者來說沒有區(qū)別办龄。HashMap效率高于TreeMap烘绽；在需要排序的Map時(shí)才選用TreeMap。
「全棧Java筆記」是一部能幫大家從零到一成長(zhǎng)為全棧Java工程師系列筆記俐填。筆者江湖人稱 Mr. G安接，10年Java研發(fā)經(jīng)驗(yàn)，曾在神州數(shù)碼英融、航天院某所研發(fā)中心從事軟件設(shè)計(jì)及研發(fā)工作盏檐，從小白逐漸做到工程師、高級(jí)工程師驶悟、架構(gòu)師胡野。精通Java平臺(tái)軟件開發(fā)，精通JAVAEE痕鳍，熟悉各種流行開發(fā)框架硫豆。
? 筆記包含從淺入深的六大部分：
? A-Java入門階段
? B-數(shù)據(jù)庫(kù)從入門到精通
? C-手刃移動(dòng)前端和Web前端
? D-J2EE從了解到實(shí)戰(zhàn)
? E-Java高級(jí)框架精解
? F-Linux和Hadoop?
