日常中我們見到的二叉樹應(yīng)用有趟畏，Java集合中的TreeSet和TreeMap蕉扮，C++ STL中的set、map角溃，以及Linux虛擬內(nèi)存的管理拷获，以及B-Tree，B+-Tree在文件系統(tǒng)减细，都是通過(guò)紅黑樹去實(shí)現(xiàn)的匆瓜。雖然之前寫過(guò)《再談堆排序：堆排序算法流程步驟透解—最大堆構(gòu)建原理》但是二叉樹的基本性質(zhì)，對(duì)我來(lái)說(shuō)未蝌，從入門到放棄是搞了好幾回陕壹。

樹的基本概念

樹（Tree）：樹是一種數(shù)據(jù)結(jié)構(gòu)，可以表示層次關(guān)系树埠，它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合糠馆。形狀像一棵倒掛的樹。

樹：不包含回路的連通無(wú)向圖（樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)）

樹有著不包含回路這個(gè)特點(diǎn)怎憋，所以樹就被賦予了很多特性

一棵樹中任意兩個(gè)結(jié)點(diǎn)有且僅有唯一的一條路徑連通

一棵樹如果有n個(gè)結(jié)點(diǎn)又碌，那它一定恰好有n-1條邊

在一棵樹中加一條邊將會(huì)構(gòu)成一個(gè)回路

樹中有且僅有一個(gè)沒(méi)有前驅(qū)的結(jié)點(diǎn)稱為根結(jié)點(diǎn)

在對(duì)樹進(jìn)行討論的時(shí)候?qū)?b>樹中的每個(gè)點(diǎn)稱為結(jié)點(diǎn)，

根結(jié)點(diǎn)|樹根（root）：沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)绊袋，即樹最頂層的節(jié)點(diǎn)

葉結(jié)點(diǎn)|樹葉（Leaf）：沒(méi)有子結(jié)點(diǎn)的結(jié)點(diǎn)（沒(méi)有子點(diǎn)的都稱為葉子）

內(nèi)部結(jié)點(diǎn)|分支結(jié)點(diǎn)|樹枝（Subtree）：除了根節(jié)點(diǎn)以外且擁有葉子節(jié)點(diǎn)毕匀，即一個(gè)結(jié)點(diǎn)既不是根結(jié)點(diǎn)也不是葉結(jié)點(diǎn)

集合概念理解樹

樹（Tree）是n（n>=0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：

有且僅有一個(gè)特定的稱為根（Root）的結(jié)點(diǎn)癌别；

當(dāng)n>1時(shí)皂岔，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,T3,...Tm，其中每一個(gè)集合本身又是一棵樹展姐，并且稱為根的子樹（Subtree）躁垛。

樹的基本特性

結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子（Child）。相應(yīng)的圾笨，該結(jié)點(diǎn)稱為孩子的雙親（Parent）教馆。同一個(gè)雙親的孩子之間互稱兄弟（Sibling）。其雙親在同一層的結(jié)點(diǎn)互為堂兄弟擂达。

樹的度

深度|高度（Depth）：是指從根結(jié)點(diǎn)到這個(gè)結(jié)點(diǎn)的層數(shù)土铺，根結(jié)點(diǎn)為第一層。每個(gè)結(jié)點(diǎn)都有深度，比如上圖左邊的樹的4號(hào)結(jié)點(diǎn)深度是3悲敷。

結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹的數(shù)目稱為結(jié)點(diǎn)的度（Degree）究恤。

樹的度：樹中結(jié)點(diǎn)的最大的度，即：是樹內(nèi)各結(jié)點(diǎn)的度的最大值后德。

葉子的度：度為0的結(jié)點(diǎn)（tips：在任意一個(gè)二叉樹中丁溅，度為0的葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)）

分支的度：度不為0的結(jié)點(diǎn)

結(jié)點(diǎn)的層次（Level）

層次：根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次等于該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的層次加1

樹的高度：樹中結(jié)點(diǎn)的最大層次

有序樹與無(wú)序樹

樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的（即不能交換）探遵，則稱該樹為有序樹窟赏，否則稱為無(wú)序樹。在有序樹中最左邊的子樹的根稱為第一個(gè)孩子箱季，最右邊的稱為最后一個(gè)孩子涯穷。

森林（Forest）

森林（Forest）是m（m>=0）棵互不相交的樹的集合。對(duì)樹中每個(gè)結(jié)點(diǎn)而言藏雏，其子樹的集合即為森林拷况。

二叉樹

二叉樹(Binary Tree)是一種樹形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支節(jié)點(diǎn)掘殴，一棵二叉樹通常由根節(jié)點(diǎn)赚瘦，分支節(jié)點(diǎn)，葉子節(jié)點(diǎn)組成奏寨。而每個(gè)分支節(jié)點(diǎn)也常常被稱作為一棵子樹起意。

二叉樹是遞歸定義的，其結(jié)點(diǎn)有左右子樹之分病瞳。

二叉樹的基本概念：

二叉樹是一種非線性結(jié)構(gòu)揽咕，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)結(jié)點(diǎn)由數(shù)據(jù)域和指針域（指針域：左指針域和右指針域）組成套菜，二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表亲善，對(duì)滿二叉樹和完全二叉樹可按層次進(jìn)行順序存儲(chǔ)

樹和二叉樹的三個(gè)主要差別

樹的節(jié)點(diǎn)個(gè)數(shù)至少為1，而二叉樹的節(jié)點(diǎn)個(gè)數(shù)可以為0

樹中節(jié)點(diǎn)的最大度數(shù)(節(jié)點(diǎn)數(shù)量)沒(méi)有限制,而二叉樹的節(jié)點(diǎn)的最大度數(shù)為2

樹的節(jié)點(diǎn)沒(méi)有左右之分逗柴，而二叉樹的節(jié)點(diǎn)有左右之分

二叉樹特點(diǎn)：

每個(gè)結(jié)點(diǎn)最多有兩顆子樹

左子樹和右子樹是有順序的蛹头，次序不能顛倒

即使某結(jié)點(diǎn)只有一個(gè)子樹，也要區(qū)分左右子樹

二叉樹可為空戏溺，空的二叉樹沒(méi)有結(jié)點(diǎn)渣蜗，非空二叉樹有且僅有一個(gè)根節(jié)點(diǎn)

二叉樹基本性質(zhì)：

在二叉樹的第k層上，至多有2^(k-1)個(gè)結(jié)點(diǎn)于购，k=1時(shí)袍睡，只有一個(gè)根節(jié)點(diǎn)知染，2^(k-1) = 2^0 = 1

深度為k的二叉樹至多有2^k-1個(gè)節(jié)點(diǎn)肋僧，k=2時(shí)，2^k-1 = 2^2 - 1 = 3個(gè)節(jié)點(diǎn)

如果總結(jié)點(diǎn)數(shù)為n0，度為2(子樹數(shù)目為2)的節(jié)點(diǎn)數(shù)為n2嫌吠，則n0=n2+1

度為0的結(jié)點(diǎn)n0（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)止潘，即n0=n2+1

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度至少為[log2n]+1，其中[log2n]表示log2n的整數(shù)部分

有N個(gè)結(jié)點(diǎn)的完全二叉樹各結(jié)點(diǎn)如果用順序方式存儲(chǔ)辫诅，如數(shù)組存儲(chǔ)

left = index * 2 + 1凭戴，

right = index * 2 + 2

序數(shù) >= floor(N/2)都是葉子節(jié)點(diǎn)

給定N個(gè)節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹炕矮，其中h(N)為卡特蘭數(shù)的第N項(xiàng)么夫，h(n)=C(2*n, n)/(n+1)。

設(shè)有i個(gè)枝點(diǎn)肤视，I為所有枝點(diǎn)的道路長(zhǎng)度總和档痪，J為葉的道路長(zhǎng)度總和J=I+2i。

二叉樹中有兩種特殊的二叉樹：滿二叉樹邢滑、完全二叉樹

完全二叉樹：

第一種解釋：完全二叉樹是指最后一層左邊是滿的腐螟，右邊可能滿也可能不滿，然后其余層都是滿的（這句話不太好理解）困后，看下面第二種解釋

第二種解釋：除第h層外乐纸，其他各層（1到h-1）的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層從右向左連續(xù)缺若干結(jié)點(diǎn)摇予，則這個(gè)二叉樹就是完全二叉樹

也就是說(shuō)如果一個(gè)結(jié)點(diǎn)有右子結(jié)點(diǎn)汽绢，那么它一定也有左子結(jié)點(diǎn)

第三種解釋：除最后一層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值侧戴，在最后一層上只缺少右邊的若干結(jié)點(diǎn)

深度為k的庶喜，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)救鲤，稱之為完全二叉樹久窟。

完全二叉樹的兩個(gè)特性：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為Math.floor(㏒? n) + 1;

如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為Math.floor(log_2 n) + 1）的結(jié)點(diǎn)按層序編號(hào)（從第1層到第Math.floor(log_2 n) + 1，每層從左到右）本缠，則對(duì)任一結(jié)點(diǎn)（1<=i<=n）有：

如果i=1斥扛，則結(jié)點(diǎn)i是二叉樹的根，無(wú)雙親丹锹；如果i>1稀颁，則其雙親parent(i)是結(jié)點(diǎn)Math.floor(i/2)。

如果2i > n楣黍，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）匾灶；否則其左孩子LChild(i)是結(jié)點(diǎn)2i.

如果2i + 1 > n，則結(jié)點(diǎn)i無(wú)右孩子租漂；否則其右孩子RChild(i)是結(jié)點(diǎn)2i + 1;

滿二叉樹：

滿二叉樹：一顆深度為k且有2^k - 1個(gè)節(jié)點(diǎn)的二叉樹稱為滿二叉樹阶女。

二叉樹中每個(gè)內(nèi)部結(jié)點(diǎn)都有存在左子樹和右子樹（或者說(shuō)滿二叉樹所有的葉結(jié)點(diǎn)都有同樣的深度）

滿二叉樹也是一種完全二叉樹颊糜，但完全二叉樹不一定是滿二叉樹。

二叉堆

二叉堆由一棵完全二叉樹來(lái)表示其結(jié)構(gòu)秃踩，可用數(shù)組來(lái)表示衬鱼。二叉堆需要滿足：

二叉堆的父節(jié)點(diǎn)的鍵值總是大于或等于(小于或等于)任何一個(gè)子節(jié)點(diǎn)的鍵值

當(dāng)父節(jié)點(diǎn)的鍵值大于或等于(小于或等于)它的每一個(gè)子節(jié)點(diǎn)的鍵值時(shí)，稱為最大堆（最小堆）

注：最大堆：父結(jié)點(diǎn)>=子結(jié)點(diǎn)憔杨，最小堆：父結(jié)點(diǎn)=<子結(jié)點(diǎn)鸟赫，

堆的實(shí)現(xiàn)通過(guò)構(gòu)造二叉堆（binary heap），實(shí)為二叉樹的一種消别；由于其應(yīng)用的普遍性抛蚤，當(dāng)不加限定時(shí)，均指該數(shù)據(jù)結(jié)構(gòu)的這種實(shí)現(xiàn)寻狂。

二叉搜索樹（二叉查找樹霉颠、二叉排序樹）

二叉查找樹(Binary Search Tree，BST)荆虱，又稱為有序二叉樹蒿偎，排序二叉樹。每個(gè)結(jié)點(diǎn)都符合：?父結(jié)點(diǎn)>右子結(jié)點(diǎn)>左子結(jié)點(diǎn)怀读。

二叉查找樹中對(duì)于目標(biāo)節(jié)點(diǎn)的查找過(guò)程類似與有序數(shù)組的二分查找诉位，并且查找次數(shù)不會(huì)超過(guò)樹的深度。

二叉搜索樹的特性：

若任意節(jié)點(diǎn)的左子樹不空菜枷，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值苍糠；

若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值啤誊；

任意節(jié)點(diǎn)的左岳瞭、右子樹也需要滿足左邊小于右邊的性質(zhì)

沒(méi)有鍵值相等的節(jié)點(diǎn)。

二叉搜索樹主要的幾個(gè)操作：

查找（search）

插入（insert）

遍歷（transverse）

二叉查找樹的性質(zhì)：對(duì)二叉查找樹進(jìn)行中序遍歷，即可得到有序的數(shù)列±桑　二叉查找樹的高度決定了二叉查找樹的查找效率。

二叉排序樹與堆的區(qū)別

在二叉排序樹中姚炕，某結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的值一定大于該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的值；在堆中卻不一定丢烘，堆只是限定了某結(jié)點(diǎn)的值大于（或小于）其左右孩子結(jié)點(diǎn)的值柱宦，但沒(méi)有限定左右孩子結(jié)點(diǎn)之間的大小關(guā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)，其左指針為空赢乓；最大值結(jié)點(diǎn)是最右下結(jié)點(diǎn)忧侧，其右指針為空石窑。在大根堆中，最小值結(jié)點(diǎn)位于某個(gè)葉子結(jié)點(diǎn)苍柏，而最大值結(jié)點(diǎn)是大根堆的堆頂（即根結(jié)點(diǎn)）尼斧。

堆是為了實(shí)現(xiàn)排序而設(shè)計(jì)的一種數(shù)據(jù)結(jié)構(gòu)姜贡，它不是面向查找操作的试吁，因而在堆中查找一個(gè)結(jié)點(diǎn)需要進(jìn)行遍歷，其平均時(shí)間復(fù)雜度是O(n)楼咳。

二叉排序樹是為了實(shí)現(xiàn)動(dòng)態(tài)查找而設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)熄捍，它是面向查找操作的。對(duì)于目標(biāo)節(jié)點(diǎn)的查找過(guò)程類似與有序數(shù)組的二分查找母怜，在二叉排序樹中查找一個(gè)結(jié)點(diǎn)的平均時(shí)間復(fù)雜度是O(log n)余耽；

設(shè)節(jié)點(diǎn)數(shù)目為n，樹的深度為h苹熏，假設(shè)樹的每層都被塞滿(第L層有2^L個(gè)節(jié)點(diǎn)碟贾，層數(shù)從1開始)，則根據(jù)等比數(shù)列公式可得h=log（n+1）轨域。即最好的情況下袱耽，二叉查找樹的查找效率為O(log n)。當(dāng)二叉查找樹退化為單鏈表時(shí)干发，比如朱巨，只有右子樹的情況,如下圖所示，此時(shí)查找效率為O(n)枉长。

總之冀续，二叉查找樹越是“矮胖”，也就是每層盡可能地被“塞滿”（每個(gè)父節(jié)點(diǎn)均有兩個(gè)子節(jié)點(diǎn)）時(shí)必峰，查找效率越高洪唐。

每層都被塞滿時(shí)，查找效率最高吼蚁，最高為O(log n)桐罕。

當(dāng)二叉查找樹退化為單鏈表時(shí)，查找效率最低桂敛，最低為O(n)功炮。

為了解決二叉查找樹退化為單鏈表時(shí)查找效率低下的問(wèn)題，引入了平衡二叉樹(AVL)术唬。

平衡二叉樹（Balanced binary tree）

平衡二叉樹定義：平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有別于AVL算法）薪伏，且具有以下性質(zhì)：它是一 棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹都是一棵平衡二叉樹粗仓。平衡二叉樹的常用算法有紅黑樹嫁怀、AVL樹等设捐。在平衡二叉搜索樹中，我們可以看到塘淑，其高度一般都良好地維持在O(log2n)萝招，大大降低了操作的時(shí)間復(fù)雜度。

最小二叉平衡樹的節(jié)點(diǎn)的公式如下：F(n)=F(n-1)+F(n-2)+1

這個(gè)類似于一個(gè)遞歸的數(shù)列存捺，可以參考Fibonacci數(shù)列槐沼，1是根節(jié)點(diǎn)，F(xiàn)(n-1)是左子樹的節(jié)點(diǎn)數(shù)量捌治，F(xiàn)(n-2)是右子樹的節(jié)點(diǎn)數(shù)量岗钩。

從平衡二叉樹的性質(zhì)可知，平衡二叉樹就是避免了二叉查找樹退化為單鏈表的極端情況肖油。二叉查找樹的查找兼吓、插入、刪除較好時(shí)間復(fù)雜度是O(log n)森枪，最差是O(n)视搏。二叉平衡樹保證查找、插入县袱、刪除的時(shí)間復(fù)雜度穩(wěn)定在O(log n)下浑娜。

總結(jié)：

完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，堆是一種完全二叉樹或者近似完全二叉樹显拳，所以效率極高棚愤，像十分常用的排序算法、Dijkstra算法杂数、Prim算法等都要用堆才能優(yōu)化宛畦，二叉排序樹的效率也要借助平衡性來(lái)提高，而平衡性基于完全二叉樹揍移。這里推薦閱讀《講透學(xué)爛二叉樹一：樹和圖的概念以及二叉樹的基本性質(zhì)》

平衡查找樹之AVL樹

AVL樹定義：AVL樹是最先發(fā)明的自平衡二叉查找樹次和。AVL樹得名于它的發(fā)明者 G.M. Adelson-Velsky 和 E.M. Landis，他們?cè)?1962 年的論文 "An algorithm for the organization of information" 中發(fā)表了它那伐。在AVL中任何節(jié)點(diǎn)的兩個(gè)兒子子樹的高度最大差別為1踏施，所以它也被稱為高度平衡樹，n個(gè)結(jié)點(diǎn)的AVL樹最大深度約1.44log2n罕邀。查找畅形、插入和刪除在平均和最壞情況下都是O(logn)。增加和刪除可能需要通過(guò)一次或多次樹旋轉(zhuǎn)來(lái)重新平衡這個(gè)樹诉探。這個(gè)方案很好的解決了二叉查找樹退化成鏈表的問(wèn)題日熬，把插入，查找肾胯，刪除的時(shí)間復(fù)雜度最好情況和最壞情況都維持在O(logN)竖席。但是頻繁旋轉(zhuǎn)會(huì)使插入和刪除犧牲掉O(logN)左右的時(shí)間耘纱，不過(guò)相對(duì)二叉查找樹來(lái)說(shuō)，時(shí)間上穩(wěn)定了很多毕荐。

AVL樹的自平衡操作——旋轉(zhuǎn)

AVL樹最關(guān)鍵的也是最難的一步操作就是旋轉(zhuǎn)束析。旋轉(zhuǎn)主要是為了實(shí)現(xiàn)AVL樹在實(shí)施了插入和刪除操作以后，樹重新回到平衡的方法憎亚。

平衡二叉樹-AVL樹(LL员寇、RR、LR虽填、RL旋轉(zhuǎn))

讓AVL樹重新平衡的操作叫做旋轉(zhuǎn)（Rotate）丁恭，旋轉(zhuǎn)操作是樹的基本操作也是其中一個(gè)難點(diǎn)曹动，對(duì)于旋轉(zhuǎn)斋日，使用結(jié)點(diǎn)上下移動(dòng)反而會(huì)好理解一點(diǎn)，失衡結(jié)點(diǎn)的BF為2或-2墓陈，注意這個(gè)失衡結(jié)點(diǎn)一般取的是最小失衡結(jié)點(diǎn)恶守，

AVL樹在實(shí)現(xiàn)上需要在每個(gè)結(jié)點(diǎn)中保留高度信息，或者使用平衡因子（Balanced Factor）贡必，簡(jiǎn)稱BF兔港，每個(gè)結(jié)點(diǎn)的平衡因子等于左子樹的高度減去右子樹的高度，因此平衡值只有三種-1仔拟，+1和0衫樊。AVL樹主要是在增加或刪除結(jié)點(diǎn)后需要重新計(jì)算平衡因子，調(diào)整樹的結(jié)構(gòu)使其重新平衡利花。

二叉樹不平衡的四種情況

首先要確定中心結(jié)點(diǎn)科侈，即最小失衡結(jié)點(diǎn)A，其平衡因子的絕對(duì)值為2炒事，主要有四種不平衡的情況：

（1）在A的左兒子B的左子樹插入臀栈，又稱為L(zhǎng)L；

（2）在A的左兒子C的右子樹插入P挠乳，又稱為L(zhǎng)R权薯；

（3）在A的右兒子C的左子樹插入P，又稱為RL睡扬；

（4）在A的右兒子B的右子樹插入盟蚣，又稱為RR。

要記住兩個(gè)重要節(jié)點(diǎn)卖怜，一個(gè)是失衡結(jié)點(diǎn)屎开，另一個(gè)是失衡結(jié)點(diǎn)的兒子，該兒子在失衡路徑上韧涨，旋轉(zhuǎn)操作則是依據(jù)失衡結(jié)點(diǎn)的兒子為中心牍戚，對(duì)失衡結(jié)點(diǎn)進(jìn)行下移動(dòng)侮繁。在這四種失衡情況中（1）和（4）是一樣的，（2）和（3）是一樣的如孝，前者使用單旋轉(zhuǎn)宪哩，后者使用雙旋轉(zhuǎn)。

AVL樹單旋轉(zhuǎn)和雙旋轉(zhuǎn)

在進(jìn)行旋轉(zhuǎn)操作時(shí)第晰，首先要找到最小失衡結(jié)點(diǎn)锁孟，判斷失衡的類型，然后選擇旋轉(zhuǎn)的類型茁瘦，如何判斷呢品抽？根據(jù)上面的圖片中的結(jié)點(diǎn)A，BF為2確定為左兒子左邊L甜熔，根據(jù)左兒子的BF為-1圆恤，則確定為R，此時(shí)屬于不平衡情況（2）腔稀，使用雙旋轉(zhuǎn)盆昙，下面詳細(xì)介紹單旋轉(zhuǎn)和雙旋轉(zhuǎn)的四種旋轉(zhuǎn)方式。

1焊虏、LL右旋轉(zhuǎn)

P下移淡喜，占據(jù)C的右兒子空穴，C的右兒子稱為P的左兒子

2诵闭、RR左旋轉(zhuǎn)

P下移炼团，占據(jù)C的左兒子空穴，C的左兒子作為P的右兒子疏尿。

3瘟芝、LR左右旋轉(zhuǎn)

雙旋轉(zhuǎn)分為兩步：左旋轉(zhuǎn)，以P的兒子C作為失衡結(jié)點(diǎn)润歉，Q的右兒子q模狭，Q下移，占據(jù)q的左兒子踩衩，q的左兒子左兒子作為Q的右兒子嚼鹉，q作為P的左兒子。

右旋轉(zhuǎn)驱富，P下移锚赤，作為p的右兒子，q的右兒子作為P的左兒子褐鸥。

4线脚、RL右左旋轉(zhuǎn)

右旋轉(zhuǎn)，P的右兒子C作為新的失衡結(jié)點(diǎn)Q，Q的左兒子q浑侥，Q下移姊舵，作為q的右兒子，q的右兒子作為Q的左兒子寓落，q作為P的右兒子括丁。

左旋轉(zhuǎn)，P下移伶选，占據(jù)q的左兒子史飞，q的左兒子作為P的右兒子。

平衡的二叉搜索樹的分類：

平衡的二叉搜索樹一般分為兩類：

嚴(yán)格維護(hù)平衡的仰税，樹的高度控制在log2n构资，使得每次操作都能使得時(shí)間復(fù)雜度控制在O(logn)，例如AVL樹陨簇，紅黑樹吐绵；

非嚴(yán)格維護(hù)平衡的，不能保證每次操作都控制在O(logn)塞帐，但是每次操作均攤時(shí)間復(fù)雜度為O(logn)拦赠，例如伸展樹巍沙。

伸展樹（Splay Tree）

伸展樹（Splay Tree）葵姥，是一種二叉搜索樹（Binary Search Tree，又稱二叉排序樹Binary Sort Tree）句携，由丹尼爾·斯立特（Daniel Sleator）和 羅伯特·恩卓·塔揚(yáng)（Robert Endre Tarjan）在1985年發(fā)明榔幸。

伸展樹的基本概念

AVL樹在每次刪除或添加結(jié)點(diǎn)時(shí)都需要使用旋轉(zhuǎn)操作平衡二叉樹，以獲得最好的查找效率矮嫉，伸展樹是另一種二叉樹削咆，它不需要高度或平衡因子這些平衡信息。伸展樹使用另一種方式實(shí)現(xiàn)高效率的查找蠢笋，不平衡但要求每次操作的那個(gè)結(jié)點(diǎn)旋轉(zhuǎn)到根結(jié)點(diǎn)上來(lái)拨齐，這樣下次查找它就能達(dá)到最快效率了，這是根據(jù)計(jì)算機(jī)的局部原理昨寞，當(dāng)一塊數(shù)據(jù)被訪問(wèn)后瞻惋，此后段時(shí)間內(nèi)也會(huì)該數(shù)據(jù)或附近的數(shù)據(jù)也會(huì)被再次用到。這也就是說(shuō)援岩，進(jìn)行增加歼狼、刪除、查找等操作都需要將本次操作的結(jié)點(diǎn)或附近結(jié)點(diǎn)旋轉(zhuǎn)到根結(jié)點(diǎn)上享怀，可對(duì)所有操作都調(diào)整羽峰，或只針對(duì)查找進(jìn)行調(diào)整。

伸展樹進(jìn)行M次操作，其時(shí)間復(fù)雜度為O(M logN)梅屉，而普通二叉樹最壞情況為O(N)值纱，連續(xù)M次操作為O(M*N)。如果一個(gè)算法M次操作的時(shí)間為O(MF(N))坯汤，則O(F(N))稱為該算法的攤還時(shí)間或攤還代價(jià)计雌，伸展樹的攤還代價(jià)為O(logN)。

伸展樹的實(shí)現(xiàn)原理

綜上玫霎，伸展樹不需要AVL樹的平衡信息凿滤，高度或BF，它是一個(gè)普通二叉查找樹庶近，它的出發(fā)點(diǎn)是：頻繁查找一個(gè)深結(jié)點(diǎn)X翁脆，會(huì)造成花費(fèi)的時(shí)間過(guò)多，采取的辦法是：將樹在X處展開鼻种，將該結(jié)點(diǎn)旋轉(zhuǎn)到根結(jié)點(diǎn)反番，自下向上單旋轉(zhuǎn)，對(duì)訪問(wèn)路徑上的每個(gè)結(jié)點(diǎn)和父結(jié)點(diǎn)進(jìn)行單旋轉(zhuǎn)叉钥，這樣頻繁訪問(wèn)結(jié)點(diǎn)即可大大減少時(shí)間罢缸，但是執(zhí)行M次操作仍然至少需要M*N的時(shí)間（最壞情況單鏈表為N）。

伸展樹在實(shí)現(xiàn)上可使用上面說(shuō)的單旋轉(zhuǎn)投队，根據(jù)目標(biāo)結(jié)點(diǎn)枫疆，全部使用單旋轉(zhuǎn)，但是效率并不好敷鸦，例如單鏈表的情況息楔，依次插入1、2扒披、3值依、4、5碟案，其效率并不好愿险，結(jié)點(diǎn)4深度依然比較深，如下圖：

為了解決這個(gè)問(wèn)題价说，我們采取一種特別的實(shí)現(xiàn)辆亏，根據(jù)三種情況進(jìn)行旋轉(zhuǎn)：

（1）當(dāng)前結(jié)點(diǎn)只有父親結(jié)點(diǎn)，使用單旋轉(zhuǎn)熔任，很明顯這種情況的父親結(jié)點(diǎn)為根結(jié)點(diǎn)褒链；

（2）當(dāng)前結(jié)點(diǎn)有父親結(jié)點(diǎn)和祖父結(jié)點(diǎn)，呈之字形疑苔，例如當(dāng)前結(jié)點(diǎn)是父親結(jié)點(diǎn)的右兒子甫匹，父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左兒子。之字形的情況進(jìn)行一次AVL雙旋轉(zhuǎn)，如下圖：

當(dāng)前結(jié)點(diǎn)有父親結(jié)點(diǎn)和祖父結(jié)點(diǎn)兵迅，呈一字形抢韭，也就是類似LL和RR的情況，但是并不是使用單旋轉(zhuǎn)恍箭，而是進(jìn)行一字形對(duì)稱旋轉(zhuǎn)刻恭。假設(shè)祖父結(jié)點(diǎn)是根結(jié)點(diǎn)，那么讓當(dāng)前結(jié)點(diǎn)X成為根結(jié)點(diǎn)扯夭，父親結(jié)點(diǎn)稱為X的右兒子鳍贾，祖父結(jié)點(diǎn)成為父親結(jié)點(diǎn)的右兒子，X的原右兒子成為父親的左兒子交洗，父親結(jié)點(diǎn)的右兒子成為祖父結(jié)點(diǎn)的左兒子骑科，下圖是一個(gè)例子：

相對(duì)于僅僅使用單旋轉(zhuǎn)，新實(shí)現(xiàn)方法的效率更高构拳，使用新的旋轉(zhuǎn)方式咆爽，對(duì)1、2置森、3斗埂、4、5的單鏈表情況在5處展開的過(guò)程如下圖：

平衡二叉樹之紅黑樹

紅黑樹的定義：

紅黑樹是一種自平衡二叉查找樹凫海，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)呛凶，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。它是在1972年由魯?shù)婪颉へ悹柊l(fā)明的盐碱，稱之為"對(duì)稱二叉B樹"把兔，它現(xiàn)代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年寫的一篇論文中獲得的。它是復(fù)雜的瓮顽，但它的操作有著良好的最壞情況運(yùn)行時(shí)間，并且在實(shí)踐中是高效的: 它可以在O(logn)時(shí)間內(nèi)做查找围橡，插入和刪除暖混，這里的n是樹中元素的數(shù)目。

紅黑樹和AVL樹一樣都對(duì)插入時(shí)間翁授、刪除時(shí)間和查找時(shí)間提供了最好可能的最壞情況擔(dān)保拣播。這不只是使它們?cè)跁r(shí)間敏感的應(yīng)用如實(shí)時(shí)應(yīng)用（real time application）中有價(jià)值，而且使它們有在提供最壞情況擔(dān)保的其他數(shù)據(jù)結(jié)構(gòu)中作為建造板塊的價(jià)值收擦；例如贮配，在計(jì)算幾何中使用的很多數(shù)據(jù)結(jié)構(gòu)都可以基于紅黑樹。此外塞赂，紅黑樹還是2-3-4樹的一種等同泪勒，它們的思想是一樣的，只不過(guò)紅黑樹是2-3-4樹用二叉樹的形式表示的。

紅黑樹的性質(zhì)：

紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹圆存，顏色為紅色或黑色叼旋。在二叉查找樹強(qiáng)制的一般要求以外，對(duì)于任何有效的紅黑樹我們?cè)黾恿巳缦碌念~外要求:

性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色沦辙。

性質(zhì)2. 根是黑色夫植。

性質(zhì)3. 所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。

性質(zhì)4. 每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)油讯。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)详民。)

性質(zhì)5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

設(shè)平衡二叉樹的深度為N陌兑，則N%2=0結(jié)點(diǎn)為黑色阐斜，N%2=1結(jié)點(diǎn)為紅色。

下面是一個(gè)具體的紅黑樹的圖例：

這些約束確保了紅黑樹的關(guān)鍵特性: 從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)诀紊。結(jié)果是這個(gè)樹大致上是平衡的谒出。因?yàn)椴僮鞅热绮迦搿h除和查找某個(gè)值的最壞情況時(shí)間都要求與樹的高度成比例邻奠，這個(gè)在高度上的理論上限允許紅黑樹在最壞情況下都是高效的笤喳，而不同于普通的二叉查找樹。

要知道為什么這些性質(zhì)確保了這個(gè)結(jié)果碌宴，注意到性質(zhì)4導(dǎo)致了路徑不能有兩個(gè)毗連的紅色節(jié)點(diǎn)就足夠了杀狡。最短的可能路徑都是黑色節(jié)點(diǎn)，最長(zhǎng)的可能路徑有交替的紅色和黑色節(jié)點(diǎn)贰镣。因?yàn)楦鶕?jù)性質(zhì)5所有最長(zhǎng)的路徑都有相同數(shù)目的黑色節(jié)點(diǎn)呜象，這就表明了沒(méi)有路徑能多于任何其他路徑的兩倍長(zhǎng)。

紅黑樹這段內(nèi)容來(lái)自maybe2030?整理自wiki百科之紅黑樹的內(nèi)容

B-樹（B-Tree）

B-樹和下面的B+樹是相當(dāng)有用和比較重要的樹數(shù)據(jù)結(jié)構(gòu)（B-樹和B樹的叫法是一樣的）碑隆，B樹恭陡，概括來(lái)說(shuō)是一個(gè)一般化的二叉查找樹，可以擁有多于2個(gè)子節(jié)點(diǎn)上煤。與自平衡二叉查找樹不同休玩，B-樹為系統(tǒng)最優(yōu)化大塊數(shù)據(jù)的讀和寫操作。B-tree算法減少定位記錄時(shí)所經(jīng)歷的中間過(guò)程劫狠，從而加快存取速度拴疤。這種數(shù)據(jù)結(jié)構(gòu)常被應(yīng)用在數(shù)據(jù)庫(kù)和文件系統(tǒng)的實(shí)作上。

B-樹的基本概念

B-樹也是一種平衡樹独泞，稱為M路平衡查找樹（并不是二叉的呐矾，M=2就是平衡二叉查找樹），M稱為階數(shù)或度數(shù)或叉數(shù)或最多子樹數(shù)懦砂，指的是一個(gè)結(jié)點(diǎn)擁有最多的兒子數(shù)蜒犯。上面一直提到關(guān)鍵字域组橄，關(guān)鍵字用于確定結(jié)點(diǎn)的分布規(guī)則，又稱為鍵值愧薛，和數(shù)據(jù)庫(kù)表的主鍵和唯一鍵是一樣的晨炕。1個(gè)關(guān)鍵字最多有2個(gè)兒子，如二叉樹毫炉，M階平衡樹的關(guān)鍵字?jǐn)?shù)為M-1瓮栗，在B-樹的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上，主要是使用關(guān)鍵字?jǐn)?shù)M-1瞄勾，可使用數(shù)組存儲(chǔ)费奸，或設(shè)計(jì)其它的容器如鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，其中3階B樹又叫2-3樹进陡，4階B樹又叫2-3-4樹愿阐，如下圖是一個(gè)3階B叉樹：

B-tree樹即B樹，B即Balanced趾疚，平衡的意思缨历。因?yàn)锽樹的原英文名稱為B-tree，而國(guó)內(nèi)很多人喜歡把B-tree譯作B-樹糙麦，其實(shí)辛孵，這是個(gè)非常不好的直譯，很容易讓人產(chǎn)生誤解赡磅。如人們可能會(huì)以為B-樹是一種樹魄缚，而B樹又是另一種樹。而事實(shí)上是焚廊，B-tree就是指的B樹冶匹。

B樹的搜索，從根結(jié)點(diǎn)開始咆瘟，如果查詢的關(guān)鍵字與結(jié)點(diǎn)的關(guān)鍵字相等嚼隘，那么就命中；否則搞疗，如果查詢關(guān)鍵字比結(jié)點(diǎn)關(guān)鍵字小嗓蘑，就進(jìn)入左兒子；如果比結(jié)點(diǎn)關(guān)鍵字大匿乃，就進(jìn)入當(dāng)前兄弟節(jié)點(diǎn)的右邊節(jié)點(diǎn)(二叉樹就是右節(jié)點(diǎn))

B-樹的主要特性如下：

每個(gè)結(jié)點(diǎn)的兒子數(shù)為2~M，為什么不是至少1個(gè)豌汇？因?yàn)锽樹的生長(zhǎng)方向是自底向上幢炸，在分裂的時(shí)候不會(huì)造成只有1個(gè)兒子，為什么最大為M拒贱？因?yàn)殡A數(shù)為M為最大兒子數(shù)宛徊，其關(guān)鍵字?jǐn)?shù)最大為M-1佛嬉；

非根非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2]~M，[]為向上取整闸天，或使用ceil()函數(shù)暖呕，這個(gè)不用太注意，實(shí)際上只要你正確操作B樹不會(huì)發(fā)生異常的情況苞氮；

所有樹葉的深度都相同湾揽，這就是說(shuō)B樹總是平衡的。

首先要指出笼吟，以上B-樹只是一個(gè)參考的規(guī)范并不是絕對(duì)標(biāo)準(zhǔn)库物，你可以根據(jù)自己的需求自己設(shè)計(jì)，這里的M一直指的都是每個(gè)結(jié)點(diǎn)的最大兒子數(shù)贷帮，而在我們的代碼中更直接的是使用關(guān)鍵字?jǐn)?shù)戚揭，關(guān)鍵字?jǐn)?shù)等于M-1，要注意是否混淆了撵枢。

B樹的主要數(shù)據(jù)存儲(chǔ)在所有結(jié)點(diǎn)上民晒，和一般的二叉樹是一樣的，在二叉樹上一個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)數(shù)據(jù)對(duì)象锄禽，B樹中H個(gè)關(guān)鍵字對(duì)應(yīng)有H個(gè)數(shù)據(jù)對(duì)象潜必，也就是說(shuō)關(guān)鍵字和數(shù)據(jù)對(duì)象的數(shù)量是相同的。如果使用的是數(shù)據(jù)對(duì)象中的成員作為數(shù)據(jù)關(guān)鍵字沟绪，則在節(jié)點(diǎn)中可以直接聲明一個(gè)數(shù)據(jù)對(duì)象的數(shù)組存儲(chǔ)（或者其它類型的容器）刮便，否則自定義創(chuàng)建一個(gè)關(guān)鍵字?jǐn)?shù)組，另外再創(chuàng)建數(shù)據(jù)對(duì)象數(shù)組绽慈，這樣會(huì)相當(dāng)麻煩（實(shí)際可以在數(shù)據(jù)對(duì)象中創(chuàng)建虛擬關(guān)鍵字恨旱，在結(jié)點(diǎn)聲明）。

?B-樹的搜索坝疼，從根結(jié)點(diǎn)開始搜贤，對(duì)結(jié)點(diǎn)內(nèi)的關(guān)鍵字（有序）序列進(jìn)行二分查找，如果命中則結(jié)束钝凶，否則進(jìn)入查詢關(guān)鍵字所屬范圍的兒子結(jié)點(diǎn)仪芒；重復(fù)，直到所對(duì)應(yīng)的兒子指針為空耕陷，或已經(jīng)是葉子結(jié)點(diǎn)掂名；

B樹的特性

定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子；且M>2哟沫；

根結(jié)點(diǎn)的兒子數(shù)為[2,M]饺蔑；

除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2,M]；

每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個(gè)關(guān)鍵字嗜诀；（至少2個(gè)關(guān)鍵字）

非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=指向兒子的指針個(gè)數(shù)-1猾警；

非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1],K[2],…,K[M-1]孔祸；且K[i]<K[i+1]；

非葉子結(jié)點(diǎn)的指針：P[1],P[2],…,P[M]发皿；其中P[1]指向關(guān)鍵字小于K[1]的子樹崔慧，P[M]指向關(guān)鍵字大于K[M-1]的子樹，其它P[i]指向關(guān)鍵字屬于(K[i-1],K[i])的子樹穴墅；

所有葉子結(jié)點(diǎn)位于同一層惶室；

B+樹（B+Tree）

B樹和B+樹的主要應(yīng)用在于數(shù)據(jù)庫(kù)開發(fā)，例如MySQL的索引引擎就是使用B+樹實(shí)現(xiàn)的封救，如此看來(lái)拇涤，使用數(shù)據(jù)庫(kù)的目的除了數(shù)據(jù)持久化就是索引了，如果數(shù)據(jù)庫(kù)失去了索引功能誉结，那么和一般的文件訪問(wèn)也就區(qū)別不大了鹅士。說(shuō)到數(shù)據(jù)庫(kù)，這里稍微討論一下相關(guān)的內(nèi)容惩坑，數(shù)據(jù)庫(kù)文件是存儲(chǔ)在硬盤上的掉盅，程序訪問(wèn)數(shù)據(jù)需要調(diào)用外設(shè)硬件去讀取硬盤上的數(shù)據(jù)，一次讀取操作稱為一次IO操作以舒，IO操作是比較耗時(shí)的趾痘，因此提高數(shù)據(jù)訪問(wèn)的速度也就是要降低IO操作的次數(shù)。

相對(duì)于物理磁盤而言蔓钟，數(shù)據(jù)的最小單位為扇區(qū)永票，一般512字節(jié)，相對(duì)文件系統(tǒng)而言滥沫，一次IO操作讀取的數(shù)據(jù)大小目前可達(dá)到4K侣集，也就是8個(gè)扇區(qū)。假如一個(gè)結(jié)點(diǎn)為4K兰绣，N個(gè)結(jié)點(diǎn)世分，最多深度為O(log N)，底數(shù)為M/2缀辩，加入一個(gè)結(jié)點(diǎn)存儲(chǔ)200個(gè)關(guān)鍵字臭埋，一百萬(wàn)個(gè)結(jié)點(diǎn)只需讀取幾次即可，而關(guān)鍵字的查詢速度也是對(duì)數(shù)時(shí)間O(log M)臀玄，如此你可以發(fā)現(xiàn)使用B樹或B+樹的功能強(qiáng)大瓢阴。

B+樹基本概念

B+樹和B樹的定義是等價(jià)的，其中有的定義是兒子數(shù)比關(guān)鍵字?jǐn)?shù)小1健无，這個(gè)不是很重要炫掐，完全可以自定義。

B+的搜索與B-樹也基本相同睬涧，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹可以在非葉子結(jié)點(diǎn)命中）募胃，其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找；

B+的性質(zhì)：

　　1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引）畦浓，且鏈表中的關(guān)鍵字恰好是有序的痹束；

　　2.不可能在非葉子結(jié)點(diǎn)命中；

　　3.非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引）讶请，葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層祷嘶；

　　4.更適合文件索引系統(tǒng)。

B+和B樹不同之處

B+樹主要分為索引結(jié)點(diǎn)和葉子結(jié)點(diǎn)夺溢，索引結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)论巍，主要用于存儲(chǔ)關(guān)鍵字，不再存儲(chǔ)數(shù)據(jù)风响，這樣一個(gè)索引結(jié)點(diǎn)的空間就小多了（一次IO操作可以讀取更多的關(guān)鍵字）嘉汰，葉子節(jié)點(diǎn)是數(shù)據(jù)記錄存儲(chǔ)的地方。索引結(jié)點(diǎn)中的關(guān)鍵字按升序排列状勤。

B+樹每個(gè)葉子結(jié)點(diǎn)保存相鄰葉子結(jié)點(diǎn)的指針（雙向鏈表）鞋怀，這樣因?yàn)槿~子結(jié)點(diǎn)中的關(guān)鍵字也是按升序排列的，那么B+樹不僅可以提供隨機(jī)訪問(wèn)持搜，還可以進(jìn)行范圍訪問(wèn)密似，因此使用B+樹實(shí)現(xiàn)索引引擎會(huì)比B樹更有優(yōu)勢(shì)。

非葉子結(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同葫盼；

非葉子結(jié)點(diǎn)的子樹指針P[i]厉熟，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區(qū)間）；

為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針怯屉；

所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)倚搬；

注意，只有葉子結(jié)點(diǎn)才存儲(chǔ)實(shí)際數(shù)據(jù)脱盲，MySQL的InnoDB引擎直接在葉子結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)本身邑滨，而MyISAM引擎則是在葉子結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)的邏輯地址，前者的方式稱為聚簇索引钱反，后者稱為非聚簇索引掖看，下面是這兩種索引結(jié)構(gòu)的粗略圖：

　B+樹的搜索與B樹也基本相同，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B樹可以在非葉子結(jié)點(diǎn)命中）面哥，其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找哎壳；

B*樹

B*樹是B+樹的變體，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針尚卫，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3。

B*樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M吱涉，即塊的最低使用率為2/3（代替B+樹的1/2）刹泄；

B+樹的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)外里，分配一個(gè)新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)特石，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針盅蝗；B+樹的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)，而不會(huì)影響兄弟結(jié)點(diǎn)姆蘸，所以它不需要指向兄弟的指針墩莫；

所以，B*樹分配新結(jié)點(diǎn)的概率比B+樹要低逞敷，空間使用率更高狂秦。

前綴樹(Tire樹)

Tire樹稱為字典樹，又稱單詞查找樹推捐，Trie樹裂问，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種玖姑。典型應(yīng)用是用于統(tǒng)計(jì)愕秫，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)焰络。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來(lái)減少查詢時(shí)間戴甩，最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希樹高闪彼。

Tire樹的三個(gè)基本性質(zhì)：

根節(jié)點(diǎn)不包含字符甜孤，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符；

從根節(jié)點(diǎn)到某一節(jié)點(diǎn)畏腕，路徑上經(jīng)過(guò)的字符連接起來(lái)缴川，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串；

每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同描馅。

Tire樹的應(yīng)用：

前綴樹里面可以存一堆字符串把夸，也可以說(shuō)是一堆單詞，存完之后我們可以輕松判斷一個(gè)指定的字符串是否出現(xiàn)過(guò)铭污×等眨”比如說(shuō)對(duì)于某一個(gè)單詞，我們要詢問(wèn)它的前綴是否出現(xiàn)過(guò)嘹狞。這樣hash就不好搞了岂膳，而用trie還是很簡(jiǎn)單“。例如：給你100000個(gè)長(zhǎng)度不超過(guò)10的單詞磅网。對(duì)于每一個(gè)單詞谈截，我們要判斷他出沒(méi)出現(xiàn)過(guò)，如果出現(xiàn)了，求第一次出現(xiàn)在第幾個(gè)位置簸喂。

串的快速檢索

給出N個(gè)單詞組成的熟詞表毙死，以及一篇全用小寫英文書寫的文章，請(qǐng)你按最早出現(xiàn)的順序?qū)懗鏊胁辉谑煸~表中的生詞娘赴。

在這道題中规哲，我們可以用數(shù)組枚舉，用哈希诽表，用字典樹，先把熟詞建一棵樹隅肥，然后讀入文章進(jìn)行比較竿奏，這種方法效率是比較高的。

“串”排序

給定N個(gè)互不相同的僅由一個(gè)單詞構(gòu)成的英文名腥放，讓你將他們按字典序從小到大輸出泛啸。用字典樹進(jìn)行排序，采用數(shù)組的方式創(chuàng)建字典樹秃症，這棵樹的每個(gè)結(jié)點(diǎn)的所有兒子很顯然地按照其字母大小排序候址。對(duì)這棵樹進(jìn)行先序遍歷即可。

最長(zhǎng)公共前綴

對(duì)所有串建立字典樹种柑，對(duì)于兩個(gè)串的最長(zhǎng)公共前綴的長(zhǎng)度即他們所在的結(jié)點(diǎn)的公共祖先個(gè)數(shù)岗仑，于是，問(wèn)題就轉(zhuǎn)化為求公共祖先的問(wèn)題聚请。

關(guān)于算法相關(guān)的詳細(xì)代碼荠雕，查看https://github.com/zhoulujun/algorithm

參考文章：

[Data Structure] 數(shù)據(jù)結(jié)構(gòu)中各種樹 https://www.cnblogs.com/maybe2030/p/4732377.html#_label3

你真的懂樹嗎？二叉樹驶赏、AVL平衡二叉樹炸卑、伸展樹、B-樹和B+樹原理和實(shí)現(xiàn)代碼詳解?www.srcmini.com/1315.html

伸展樹（Splay Tree）進(jìn)階 - 從原理到實(shí)現(xiàn)?https://www.cnblogs.com/dilthey/p/9379652.html#splay-2.1

二叉樹的遍歷（前序煤傍、中序盖文、后序、已知前中序求后序蚯姆、已知中后序求前序）?https://www.cnblogs.com/lanhaicode/p/10390147.html

js數(shù)據(jù)結(jié)構(gòu)-二叉樹（二叉堆）https://segmentfault.com/a/1190000017761929

圖的基本概念五续，圖的遍歷、拯救007?https://www.cnblogs.com/hi3254014978/p/9535276.html

小白學(xué)數(shù)據(jù)結(jié)構(gòu)——二蒋失、樹與堆（基本概念及二叉樹返帕、二叉堆的python實(shí)現(xiàn)）https://blog.csdn.net/qq_33414271/article/details/78506632

如果子結(jié)果編號(hào)為i，求其父節(jié)點(diǎn)編號(hào)?https://blog.csdn.net/qingmengwuhen1/article/details/51926409?utm_source=blogxgwz5

常見數(shù)據(jù)結(jié)構(gòu)(二)-樹(二叉樹篙挽，紅黑樹荆萤，B樹)?https://segmentfault.com/a/1190000007173881

js 中二叉樹的深度遍歷與廣度遍歷(遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn))?http://www.reibang.com/p/5e9ea25a1aae

平衡二叉樹-AVL樹(LL、RR、LR链韭、RL旋轉(zhuǎn))?https://www.cnblogs.com/ybf-yyj/p/9513706.html

數(shù)據(jù)結(jié)構(gòu)----樹及二叉樹的遍歷JS?https://blog.csdn.net/qq_43043859/article/details/101347877

https://www.cnblogs.com/guxuanqing/p/10540551.html

轉(zhuǎn)載本站文章《講透學(xué)爛二叉樹(二)：圖中樹的定義&各類型樹的特征分析》,

請(qǐng)注明出處：https://www.zhoulujun.cn/html/theory/algorithm/TreeGraph/8282.html