一、樹(shù)

一些基本概念有：

節(jié)點(diǎn)、父節(jié)點(diǎn)、子節(jié)點(diǎn)、兄弟節(jié)點(diǎn)、根節(jié)點(diǎn)、葉子節(jié)點(diǎn)；

高度(從葉子節(jié)點(diǎn)往上)、深度(從根節(jié)點(diǎn)往下0 ^ (n-1) )、層(從根節(jié)點(diǎn)往下1~n)；n為層數(shù)；

二、二叉樹(shù)

一些基本的概念：

• 左子節(jié)點(diǎn)、右子節(jié)點(diǎn)；二叉樹(shù)要求每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)，但并不要求必須有兩個(gè)子節(jié)點(diǎn)，單獨(dú)有左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)都是可以的；
• 滿二叉樹(shù)，是指所有葉子節(jié)點(diǎn)都在最底層，除了葉子節(jié)點(diǎn)以外，每個(gè)節(jié)點(diǎn)都有左右兩個(gè)子節(jié)點(diǎn)；
• 完全二叉樹(shù)，是指所有葉子節(jié)點(diǎn)都在最底下兩層，最后一層的葉子節(jié)點(diǎn)是從左到右依次排列的，中間不能有空缺，其它層節(jié)點(diǎn)個(gè)數(shù)都要達(dá)到最大，不能有空缺；
• 存儲(chǔ)方法有鏈?zhǔn)酱鎯?chǔ)法、順序存儲(chǔ)法；

大部分二叉樹(shù)都可以使用如下鏈?zhǔn)酱鎯?chǔ)法來(lái)進(jìn)行表示，必然要左右節(jié)點(diǎn)空間來(lái)指向各自的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)；

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)

順序存儲(chǔ)法則是利用一個(gè)數(shù)組，將當(dāng)前節(jié)點(diǎn)存放在下標(biāo)為i的地址中，那么左子節(jié)點(diǎn)就存放在2i的地址中，右子節(jié)點(diǎn)存放在2i+1的地址中；反過(guò)來(lái)，已知某個(gè)節(jié)點(diǎn)位置為k，那么它的父節(jié)點(diǎn)位置就是k/2；但是當(dāng)二叉樹(shù)不是一顆完全二叉樹(shù)的時(shí)候，就會(huì)比較浪費(fèi)數(shù)組存儲(chǔ)空間；因此，當(dāng)二叉樹(shù)為完全二叉樹(shù)的時(shí)候，采用順序存儲(chǔ)是最優(yōu)的；

完全二叉樹(shù)的順序存儲(chǔ)

非完全二叉樹(shù)的順序存儲(chǔ)

• 遍歷分為前序遍歷、中序遍歷和后序遍歷；

前序遍歷，先自己，再左邊，最后右邊；

中序遍歷，先左邊，再自己，最后右邊；

后續(xù)遍歷，先左邊，再右邊，最后自己；

三、二叉查找樹(shù)

在二叉樹(shù)的基礎(chǔ)上，滿足如下條件：對(duì)于任意一個(gè)節(jié)點(diǎn)，其左子樹(shù)上的每個(gè)節(jié)點(diǎn)值都要小于當(dāng)前節(jié)點(diǎn)的值，其右子樹(shù)上的每個(gè)節(jié)點(diǎn)值都要大于當(dāng)前節(jié)點(diǎn)的值；

查找，目標(biāo)元素target和當(dāng)前節(jié)點(diǎn)比較，如果比當(dāng)前節(jié)點(diǎn)小那么就在左子樹(shù)中繼續(xù)查找，反之則在右子樹(shù)中查找；

插入，目標(biāo)元素target和當(dāng)前節(jié)點(diǎn)比較，如果比當(dāng)前節(jié)點(diǎn)小并且當(dāng)前節(jié)點(diǎn)沒(méi)有左子樹(shù)，那么作為左子節(jié)點(diǎn)插入，如果有左子樹(shù)，那么繼續(xù)往左遍歷；如果比當(dāng)前節(jié)點(diǎn)大并且當(dāng)前節(jié)點(diǎn)沒(méi)有右子樹(shù)，那么作為右子節(jié)點(diǎn)插入，如果有右子樹(shù)，那么繼續(xù)往右遍歷；

刪除，先找到目標(biāo)元素，如果目標(biāo)沒(méi)有子節(jié)點(diǎn)，直接將其刪除即可；如果目標(biāo)有子節(jié)點(diǎn)（左右子節(jié)點(diǎn)都可），那么將目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)的子節(jié)點(diǎn)即可；如果目標(biāo)節(jié)點(diǎn)同時(shí)擁有左右子樹(shù)，那么就需要在右子樹(shù)中找到最小值替換當(dāng)前節(jié)點(diǎn)；（如果想要提高刪除的性能，我們還是可以采用標(biāo)記刪除法，以空間換時(shí)間）

二叉查找樹(shù)的刪除操作

• 查找最大值和最小值；
• 尋找給定元素的前驅(qū)和后繼節(jié)點(diǎn)；
• 中序遍歷輸出完全有序的數(shù)列，時(shí)間復(fù)雜度O(n)，相較于原先講過(guò)的八大排序算法來(lái)說(shuō)，算是最好的排序算法了；
• 重復(fù)數(shù)據(jù)的存儲(chǔ)；

相同值存放在同一個(gè)節(jié)點(diǎn)；

相同值存放在右子樹(shù)；但是要求在查找和刪除的時(shí)候，一定要遍歷到葉子節(jié)點(diǎn)才能找到所有相同的元素；

• 時(shí)間復(fù)雜度分析，在最壞的情況下，二叉查找樹(shù)退化為鏈表，那么所有操作的時(shí)間復(fù)雜度都是O(n)，但是在完全二叉樹(shù)時(shí)，時(shí)間復(fù)雜度取決于樹(shù)的高度，就是O(logn)；

四、平衡二叉查找樹(shù)

如何讓二叉查找樹(shù)盡量保持平衡，讓時(shí)間復(fù)雜度維持在O(logn)，這是平衡二叉查找樹(shù)需要做的事情。那什么樣子的二叉查找樹(shù)可以被稱為平衡的二叉查找樹(shù)呢？

嚴(yán)格的定義就是：任意一個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度相差不能大于1；比如AVL樹(shù)，這就是一種高度平衡的，完全符合平衡二叉樹(shù)定義的。

但是，比較嚴(yán)格的平衡二叉樹(shù)實(shí)現(xiàn)起來(lái)有些復(fù)雜，需要耗費(fèi)過(guò)多的資源在平衡高度差不超過(guò)1這個(gè)條件上面，反而矯枉過(guò)正了。因此，我們只要能設(shè)計(jì)出一種二叉查找樹(shù)，使得所有節(jié)點(diǎn)的左右子樹(shù)看起來(lái)相對(duì)均衡，那么也可以將它稱為符合要求的平衡二叉查找樹(shù)，比如下面的紅黑樹(shù)。

五、紅黑樹(shù)

紅黑樹(shù)是一種不嚴(yán)格的平衡二叉查找樹(shù)，它具有以下要求：

• 根節(jié)點(diǎn)是黑色的；
• 每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)，不存儲(chǔ)數(shù)據(jù)；
• 任何上下相鄰的節(jié)點(diǎn)都不能同時(shí)為紅色，紅色節(jié)點(diǎn)是被黑色節(jié)點(diǎn)隔開(kāi)的；
• 每個(gè)節(jié)點(diǎn)到到其所有葉子節(jié)點(diǎn)的路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)；
• 插入的節(jié)點(diǎn)必須是紅色的，新插入的節(jié)點(diǎn)都是放在葉子節(jié)點(diǎn)上的；

紅黑樹(shù)在插入節(jié)點(diǎn)時(shí)，如果父節(jié)點(diǎn)是黑色的，那么直接插入就行；如果插入的節(jié)點(diǎn)是根節(jié)點(diǎn)，那么將它改為黑色即可；除此之外的任何情況，都會(huì)破壞如上紅黑樹(shù)的要求，此時(shí)就需要通過(guò)左旋、右旋或者改變顏色才能重新符合紅黑樹(shù)的要求。紅黑樹(shù)的實(shí)現(xiàn)過(guò)程和平衡過(guò)程都比較復(fù)雜，一般了解即可。

紅黑樹(shù)具有穩(wěn)定的性能，在插入、刪除和查找時(shí)都能穩(wěn)定在O(logn)，同時(shí)不會(huì)浪費(fèi)太多資源進(jìn)行平衡的操作，所以在工業(yè)運(yùn)用上，比嚴(yán)格的平衡二叉查找樹(shù)要更加地受歡迎。

六、遞歸樹(shù)

遞歸樹(shù)主要可以用來(lái)分析復(fù)雜算法的時(shí)間復(fù)雜度；比如原先說(shuō)過(guò)的歸并排序，時(shí)間復(fù)雜度是O(logn)，這個(gè)使用遞歸樹(shù)怎么分析呢？

歸并排序的遞歸樹(shù)

歸并排序的過(guò)程就是每次分解都是1/2，直至每個(gè)節(jié)點(diǎn)只有一個(gè)元素為止，然后從下往上進(jìn)行相鄰節(jié)點(diǎn)的歸并排序，直至歸并為一個(gè)數(shù)列。

分解的過(guò)程時(shí)間耗費(fèi)比較小，因?yàn)榭梢岳脭?shù)組隨機(jī)訪問(wèn)的特性一分為二，所以時(shí)間可以記為常數(shù)C；

歸并的時(shí)候每層都需要比較n個(gè)元素，所以時(shí)間復(fù)雜度為O(n)，假設(shè)樹(shù)的高度為h，那么時(shí)間復(fù)雜度就是O(hn)，其中高度怎么計(jì)算呢？在滿二叉樹(shù)的時(shí)候，樹(shù)的高度可以表示為logn，所以歸并過(guò)程的時(shí)間復(fù)雜度就近似為O(nlogn)，那么整個(gè)分解和歸并的時(shí)間復(fù)雜度就是O(C+nlogn)，去掉低階，最終得到歸并排序的時(shí)間復(fù)雜度就是O(logn)。

七、總結(jié)

二叉樹(shù)比散列表的優(yōu)勢(shì)在哪里？

散列表中的數(shù)據(jù)是無(wú)序存儲(chǔ)的，如果我們需要有序的數(shù)列，就必須先排序，時(shí)間復(fù)雜度取決于你用的排序算法以及無(wú)序數(shù)據(jù)的排列情況，但是肯定不會(huì)好于O(n)，但是二叉查找樹(shù)，又稱二叉排序樹(shù)天然就是有序的，只要按照中序遍歷輸出即可，時(shí)間復(fù)雜度穩(wěn)定為O(n)；

散列表有擴(kuò)容操作，哈希計(jì)算操作，還會(huì)有沖突再散列的問(wèn)題，其時(shí)間效率并不穩(wěn)定；而平衡二叉樹(shù)能讓查找、插入和刪除的時(shí)間復(fù)雜度能穩(wěn)定在O(logn)；當(dāng)數(shù)據(jù)量大的時(shí)候，平衡二叉樹(shù)的優(yōu)勢(shì)和性能將會(huì)遠(yuǎn)超散列表；

散列表實(shí)現(xiàn)起來(lái)比較復(fù)雜，需要考慮散列函數(shù)的設(shè)計(jì)、裝載因子的設(shè)計(jì)、擴(kuò)容和縮容方案、沖突再散列如何解決等；而平衡二叉樹(shù)只需要考慮平衡的問(wèn)題，比較簡(jiǎn)單，方案也比較成熟。