• 定義指針變量聪姿，如果不賦給它地址碴萧，系統(tǒng)會(huì)隨機(jī)給它分配一個(gè)地址。

C++標(biāo)準(zhǔn)庫(kù)

C++ Standard Library咳燕，是類庫(kù)和函數(shù)的集合勿决，其使用核心語(yǔ)言寫成乒躺，由c++標(biāo)準(zhǔn)委員會(huì)制定招盲，并不斷維護(hù)更新。C++強(qiáng)大的功能來源于其豐富的類庫(kù)及庫(kù)函數(shù)資源嘉冒。 C++標(biāo)準(zhǔn)庫(kù)（C++ Standard Library, 亦可稱作曹货，C++標(biāo)準(zhǔn)程序庫(kù)）的內(nèi)容總共在50個(gè)標(biāo)準(zhǔn)頭文件中定義。 在C++開發(fā)中讳推，要盡可能地利用標(biāo)準(zhǔn)庫(kù)完成顶籽。這樣做的直接好處包括：
（1）成本：
已經(jīng)作為標(biāo)準(zhǔn)提供，不必再花費(fèi)時(shí)間银觅、人力重新開發(fā)礼饱。
（2）質(zhì)量：
標(biāo)準(zhǔn)庫(kù)的都是經(jīng)過嚴(yán)格測(cè)試的，正確性有保證。
（3）效率：
關(guān)于人的效率已經(jīng)體現(xiàn)在成本中了镊绪，關(guān)于代碼的執(zhí)行效率要相信實(shí)現(xiàn)標(biāo)準(zhǔn)庫(kù)的前輩的水平匀伏。
（4）良好的編程風(fēng)格：

C++模板

模板可以實(shí)現(xiàn)類型的參數(shù)化(把類型定義為參數(shù))，從而實(shí)現(xiàn)了真正的代碼可重用性蝴韭。C++中的模板可分為函數(shù)模板和類模板够颠，而把函數(shù)模板的具體化稱為模板函數(shù)，把類模板的具體化成為模板類榄鉴。

哈希表

散列表(Hash table履磨，也叫哈希表)，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)庆尘。也就是說剃诅，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度减余。這個(gè)映射函數(shù)叫做散列函數(shù)综苔，存放記錄的[數(shù)組]叫做散列表。
給定表M位岔，存在函數(shù)f(key)如筛，對(duì)任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址抒抬，則稱表M為哈希(Hash)表杨刨，函數(shù)f(key)為哈希(Hash) 函數(shù)。

散列函數(shù)能使對(duì)一個(gè)數(shù)據(jù)序列的訪問過程更加迅速有效擦剑，通過散列函數(shù)妖胀，[數(shù)據(jù)元素]將被更快地定位。

遞歸

使用遞歸解決問題惠勒，思路清晰赚抡，代碼少。但是在主流高級(jí)語(yǔ)言中（如C語(yǔ)言纠屋、Pascal語(yǔ)言等）使用遞歸算法要耗用更多的椡砍迹空間，所以在堆棧尺寸受限制時(shí)（如嵌入式系統(tǒng)或者內(nèi)核態(tài)編程）售担，應(yīng)避免采用赁遗。所有的遞歸算法都可以改寫成與之等價(jià)的非遞歸[算法]

雙向鏈表

雙向鏈表也叫雙鏈表嫡霞，是鏈表的一種每辟，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)[指針]，分別指向直接后繼和直接前驅(qū)屏镊。所以哥攘，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始剖煌，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)材鹦。一般我們都構(gòu)造雙向[循環(huán)鏈表]

霍夫曼編碼

[哈夫曼]編碼(Huffman Coding)，又稱霍夫曼編碼耕姊，是一種編碼方式侠姑，哈夫曼編碼是可變[字長(zhǎng)]編碼(VLC)的一種。Huffman于1952年提出一種編碼方法箩做，該方法完全依據(jù)[字符]出現(xiàn)概率來構(gòu)造異字頭的平均長(zhǎng)度最短的碼字莽红，有時(shí)稱之為最佳編碼，一般就叫做Huffman編碼(有時(shí)也稱為霍夫曼編碼)邦邦。

在計(jì)算機(jī)數(shù)據(jù)處理中安吁，霍夫曼編碼使用變長(zhǎng)編碼表對(duì)源符號(hào)（如文件中的一個(gè)字母）進(jìn)行編碼，其中變長(zhǎng)編碼表是通過一種評(píng)估來源符號(hào)出現(xiàn)機(jī)率的方法得到的燃辖，出現(xiàn)機(jī)率高的字母使用較短的編碼鬼店，反之出現(xiàn)機(jī)率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均長(zhǎng)度黔龟、期望值降低妇智，從而達(dá)到無損壓縮數(shù)據(jù)的目的。

例如氏身，在英文中巍棱，e的出現(xiàn)機(jī)率最高，而z的出現(xiàn)概率則最低蛋欣。當(dāng)利用霍夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)航徙，e極有可能用一個(gè)比特來表示，而z則可能花去25個(gè)比特（不是26）陷虎。用普通的表示方法時(shí)到踏，每個(gè)英文字母均占用一個(gè)字節(jié)（byte），即8個(gè)比特尚猿。二者相比窝稿，e使用了一般編碼的1/8的長(zhǎng)度，z則使用了3倍多凿掂。倘若我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出現(xiàn)概率的較準(zhǔn)確的估算伴榔，就可以大幅度提高無損壓縮的比例。

霍夫曼樹又稱最優(yōu)二叉樹缠劝，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹潮梯。所謂樹的帶權(quán)路徑長(zhǎng)度骗灶，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為0層惨恭，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)）。樹的路徑長(zhǎng)度是從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和耙旦，記為WPL=（W1L1+W2L2+W3L3+...+WnLn）脱羡，N個(gè)權(quán)值Wi（i=1,2,...n）構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹萝究，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i（i=1,2,...n）★惫蓿可以證明霍夫曼樹的WPL是最小的帆竹。

二叉樹

順序存儲(chǔ)結(jié)構(gòu)用一組連續(xù)的存儲(chǔ)單元存放二叉樹中的結(jié)點(diǎn)。一般是按照二叉樹結(jié)點(diǎn)從上至下脓规、從左到右的順序存儲(chǔ)栽连。依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲(chǔ)比較合適侨舆，樹中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系秒紧，這樣既能夠最大可能地節(jié)省存儲(chǔ)空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹中的位置挨下，以及結(jié)點(diǎn)之間的關(guān)系熔恢。

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用鏈表來表示一棵二叉樹，即用鏈來指示著元素的邏輯關(guān)系臭笆。通常有下面兩種形式叙淌。

三叉鏈表存儲(chǔ)：其中，data愁铺、lchild以及rchild三個(gè)域的意義同二叉鏈表結(jié)構(gòu)鹰霍；parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。

線索二叉樹的定義
按照某種遍歷方式對(duì)二叉樹進(jìn)行遍歷茵乱，可以把二叉樹中所有結(jié)點(diǎn)排列為一個(gè)線性序列衅谷。在該序列中，除第一個(gè)結(jié)點(diǎn)外似将，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)获黔；除最后一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接后繼結(jié)點(diǎn)在验。但是玷氏，二叉樹中每個(gè)結(jié)點(diǎn)在這個(gè)序列中的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)是什么，二叉樹的存儲(chǔ)結(jié)構(gòu)中并沒有反映出來腋舌，只能在對(duì)二叉樹遍歷的動(dòng)態(tài)過程中得到這些信息盏触。為了保留結(jié)點(diǎn)在某種遍歷序列中直接前驅(qū)和直接后繼的位置信息，可以利用二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)中的那些空指針域來指示块饺。這些指向直接前驅(qū)結(jié)點(diǎn)和指向直接后繼結(jié)點(diǎn)的指針被稱為線索(thread)赞辩，加了線索的二叉樹稱為線索二叉樹。

Haffma Tree
?The optimal binary tree最優(yōu)二叉樹授艰，也稱哈夫曼(Haffman)樹辨嗽，是指對(duì)于一組帶有確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹淮腾。
?那么什么是二叉樹的帶權(quán)路徑長(zhǎng)度呢糟需？
?在前面我們介紹過路徑和結(jié)點(diǎn)的路徑長(zhǎng)度的概念屉佳，而二叉樹的路徑長(zhǎng)度則是指由根結(jié)點(diǎn)到所有葉結(jié)點(diǎn)的路徑長(zhǎng)度之和。如果二叉樹中的葉結(jié)點(diǎn)都具有一定的權(quán)值洲押，則可將這一概念加以推廣武花。

具有相同葉結(jié)點(diǎn)和不同帶權(quán)路徑長(zhǎng)度的二叉樹
由相同權(quán)值的一組葉結(jié)點(diǎn)所構(gòu)成的二叉樹有不同的形態(tài)和不同的帶權(quán)路徑長(zhǎng)度，那么如何找到帶權(quán)路徑長(zhǎng)度最小的二叉樹呢杈帐？根據(jù)哈夫曼樹的定義体箕，一棵二叉樹要使其WPL值最小，必須使權(quán)值越大的葉結(jié)點(diǎn)越靠近根結(jié)點(diǎn)挑童，而權(quán)值越小的葉結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)干旁。
?哈夫曼(Haffman)依據(jù)這一特點(diǎn)提出了一種方法。

哈夫曼樹的基本思想
⑴由給定的n個(gè)權(quán)值{W1,W2,…,Wn}構(gòu)造n棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹炮沐，從而得到一個(gè)二叉樹的集合F＝{T1,T2,…,Tn}争群；
⑵在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹大年，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左换薄、右子樹根結(jié)點(diǎn)權(quán)值之和；
⑶在集合F中刪除作為左翔试、右子樹的兩棵二叉樹轻要，并將新建立的二叉樹加入到集合F中；
⑷重復(fù)(2)垦缅、(3)兩步冲泥，當(dāng)F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹壁涎。

哈夫曼樹可用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案凡恍。具體做法如下：設(shè)需要編碼的字符集合為{d1,d2,…,dn}，它們?cè)陔娢闹谐霈F(xiàn)的次數(shù)或頻率集合為{w1,w2,…,wn}怔球，以d1,d2,…,dn作為葉結(jié)點(diǎn)嚼酝，w1,w2,…,wn作為它們的權(quán)值，構(gòu)造一棵哈夫曼樹竟坛，規(guī)定哈夫曼樹中的左分支代表0闽巩，右分支代表1，則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過的路徑分支組成的0和1的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼担汤，我們稱之為哈夫曼編碼涎跨。

在哈夫曼編碼樹中，樹的帶權(quán)路徑長(zhǎng)度的含義是各個(gè)字符的碼長(zhǎng)與其出現(xiàn)次數(shù)的乘積之和崭歧，也就是電文的代碼總長(zhǎng)隅很，所以采用哈夫曼樹構(gòu)造的編碼是一種能使電文代碼總長(zhǎng)最短的不等長(zhǎng)編碼。

實(shí)現(xiàn)哈夫曼編碼的算法可分為兩大部分：
(1)構(gòu)造哈夫曼樹驾荣；
(2)在哈夫曼樹上求葉結(jié)點(diǎn)的編碼外构。
?求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹中播掷，從葉結(jié)點(diǎn)開始审编，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，每回退一步歧匈，就走過了哈夫曼樹的一個(gè)分支垒酬，從而得到一位哈夫曼碼值，由于一個(gè)字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的0件炉，1序列勘究，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼斟冕。

哈希表

哈希法又稱散列法口糕、雜湊法以及關(guān)鍵字地址計(jì)算法等，相應(yīng)的表稱為哈希表磕蛇。這種方法的基本思想是：首先在元素的關(guān)鍵字k和元素的存儲(chǔ)位置p之間建立一個(gè)對(duì)應(yīng)關(guān)系f景描，使得p=f(k)，f稱為哈希函數(shù)秀撇。創(chuàng)建哈希表時(shí)超棺，把關(guān)鍵字為k的元素直接存入地址為f(k)的單元；以后當(dāng)查找關(guān)鍵字為k的元素時(shí)呵燕，再利用哈希函數(shù)計(jì)算出該元素的存儲(chǔ)位置p=f(k)棠绘，從而達(dá)到按關(guān)鍵字直接存取元素的目的。
當(dāng)關(guān)鍵字集合很大時(shí)再扭，關(guān)鍵字值不同的元素可能會(huì)映象到哈希表的同一地址上氧苍，即 k1≠k2 ，但 H（k1）=H（k2）泛范，這種現(xiàn)象稱為沖突候引，此時(shí)稱k1和k2為同義詞。實(shí)際中敦跌，沖突是不可避免的澄干，只能通過改進(jìn)哈希函數(shù)的性能來減少?zèng)_突。
綜上所述柠傍，哈希法主要包括以下兩方面的內(nèi)容：
1）如何構(gòu)造哈希函數(shù)
2）如何處理沖突麸俘。
8.4.1 哈希函數(shù)的構(gòu)造方法
構(gòu)造哈希函數(shù)的原則是：
①函數(shù)本身便于計(jì)算；
②計(jì)算出來的地址分布均勻惧笛，即對(duì)任一關(guān)鍵字k从媚，f(k) 對(duì)應(yīng)不同地址的概率相等，目的是盡可能減少?zèng)_突患整。
下面介紹構(gòu)造哈希函數(shù)常用的五種方法拜效。
1． 數(shù)字分析法
如果事先知道關(guān)鍵字集合喷众，并且每個(gè)關(guān)鍵字的位數(shù)比哈希表的地址碼位數(shù)多時(shí)，可以從關(guān)鍵字中選出分布較均勻的若干位紧憾，構(gòu)成哈希地址到千。例如，有80個(gè)記錄赴穗，關(guān)鍵字為8位十進(jìn)制整數(shù)d1d2d3…d7d8憔四，如哈希表長(zhǎng)取100，則哈希表的地址空間為：00~99般眉。假設(shè)經(jīng)過分析了赵，各關(guān)鍵字中 d4和d7的取值分布較均勻，則哈希函數(shù)為：h(key)=h(d1d2d3…d7d8)=d4d7甸赃。例如柿汛，h(81346532)=43，h(81301367)=06埠对。相反苛茂，假設(shè)經(jīng)過分析，各關(guān)鍵字中 d1和d8的取值分布極不均勻鸠窗， d1 都等于5妓羊，d8 都等于2，此時(shí)稍计，如果哈希函數(shù)為：h(key)=h(d1d2d3…d7d8)=d1d8躁绸，則所有關(guān)鍵字的地址碼都是52，顯然不可取臣嚣。
2． 平方取中法 當(dāng)無法確定關(guān)鍵字中哪幾位分布較均勻時(shí)净刮，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址硅则。這是因?yàn)椋浩椒胶笾虚g幾位和關(guān)鍵字中每一位都相關(guān)淹父，故不同關(guān)鍵字會(huì)以較高的概率產(chǎn)生不同的哈希地址。
例：我們把英文字母在字母表中的位置序號(hào)作為該英文字母的內(nèi)部編碼怎虫。例如K的內(nèi)部編碼為11暑认，E的內(nèi)部編碼為05，Y的內(nèi)部編碼為25大审，A的內(nèi)部編碼為01, B的內(nèi)部編碼為02蘸际。由此組成關(guān)鍵字“KEYA”的內(nèi)部代碼為11052501，同理我們可以得到關(guān)鍵字“KYAB”徒扶、“AKEY”粮彤、“BKEY”的內(nèi)部編碼。之后對(duì)關(guān)鍵字進(jìn)行平方運(yùn)算后，取出第7到第9位作為該關(guān)鍵字哈希地址导坟，如圖8.23所示屿良。

8.4.2 處理沖突的方法
通過構(gòu)造性能良好的哈希函數(shù)，可以減少?zèng)_突惫周，但一般不可能完全避免沖突尘惧，因此解決沖突是哈希法的另一個(gè)關(guān)鍵問題。創(chuàng)建哈希表和查找哈希表都會(huì)遇到?jīng)_突闯两，兩種情況下解決沖突的方法應(yīng)該一致褥伴。
下面以創(chuàng)建哈希表為例谅将，說明解決沖突的方法漾狼。常用的解決沖突方法有以下四種：
1.開放定址法
這種方法也稱再散列法，其基本思想是：當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時(shí)饥臂，以p為基礎(chǔ)逊躁，產(chǎn)生另一個(gè)哈希地址p1，如果p1仍然沖突隅熙，再以p為基礎(chǔ)稽煤，產(chǎn)生另一個(gè)哈希地址p2，…囚戚，直到找出一個(gè)不沖突的哈希地址pi 酵熙，將相應(yīng)元素存入其中。
這種方法有一個(gè)通用的再散列函數(shù)形式：
Hi=（H（key）+di）% m i=1驰坊，2匾二，…，n
其中H（key）為哈希函數(shù)拳芙，m 為表長(zhǎng)察藐，di稱為增量序列。增量序列的取值方式不同舟扎，相應(yīng)的再散列方式也不同分飞。
主要有以下三種：

• 線性探測(cè)再散列 dii=1，2睹限，3譬猫，…，m-1 這種方法的特點(diǎn)是：沖突發(fā)生時(shí)羡疗，順序查看表中下一單元删窒，直到找出一個(gè)空單元或查遍全表。
• 二次探測(cè)再散列 di=12顺囊，-12肌索，22，-22，…诚亚，k2晕换，-k2 ( k<=m/2 ) 這種方法的特點(diǎn)是：沖突發(fā)生時(shí)，在表的左右進(jìn)行跳躍式探測(cè)站宗，比較靈活闸准。
• 偽隨機(jī)探測(cè)再散列 di=偽隨機(jī)數(shù)序列。 具體實(shí)現(xiàn)時(shí)梢灭，應(yīng)建立一個(gè)偽隨機(jī)數(shù)發(fā)生器夷家，（如i=(i+p) % m），并給定一個(gè)隨機(jī)數(shù)做起點(diǎn)敏释。
  例如库快，已知哈希表長(zhǎng)度m=11，哈希函數(shù)為：H（key）= key % 11钥顽，則H（47）=3义屏，H（26）=4，H（60）=5蜂大，假設(shè)下一個(gè)關(guān)鍵字為69闽铐，則H（69）=3，與47沖突奶浦。如果用線性探測(cè)再散列處理沖突兄墅，下一個(gè)哈希地址為H1=（3 + 1）% 11 = 4，仍然沖突澳叉，再找下一個(gè)哈希地址為H2=（3 + 2）% 11 = 5隙咸，還是沖突，繼續(xù)找下一個(gè)哈希地址為H3=（3 + 3）% 11 = 6耳高，此時(shí)不再?zèng)_突扎瓶，將69填入5號(hào)單元，參圖8.26 (a)泌枪。如果用二次探測(cè)再散列處理沖突概荷，下一個(gè)哈希地址為H1=（3 + 12）% 11 = 4，仍然沖突碌燕，再找下一個(gè)哈希地址為H2=（3 - 12）% 11 = 2误证，此時(shí)不再?zèng)_突，將69填入2號(hào)單元修壕，參圖8.26 (b)愈捅。如果用偽隨機(jī)探測(cè)再散列處理沖突，且偽隨機(jī)數(shù)序列為：2慈鸠，5蓝谨，9，……..，則下一個(gè)哈希地址為H1=（3 + 2）% 11 = 5譬巫，仍然沖突咖楣，再找下一個(gè)哈希地址為H2=（3 + 5）% 11 = 8，此時(shí)不再?zèng)_突芦昔，將69填入8號(hào)單元诱贿，參圖8.26 (c)。

2.再哈希法
這種方法是同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù)：
Hi=RH1（key） i=1咕缎，2珠十，…，k 當(dāng)哈希地址Hi=RH1（key）發(fā)生沖突時(shí)凭豪，再計(jì)算Hi=RH2（key）……焙蹭，直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集墅诡，但增加了計(jì)算時(shí)間壳嚎。

3.鏈地址法
這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個(gè)稱為同義詞鏈的單鏈表桐智，并將單鏈表的頭指針存在哈希表的第i個(gè)單元中末早，因而查找、插入和刪除主要在同義詞鏈中進(jìn)行说庭。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況然磷。 例如，已知一組關(guān)鍵字（32刊驴，40姿搜，36，53捆憎，16舅柜，46，71躲惰，27致份，42，24础拨，49氮块，64），哈希表長(zhǎng)度為13诡宗，哈希函數(shù)為：H（key）= key % 13滔蝉，則用鏈地址法處理沖突的結(jié)果如圖8.27所示：

4、建立公共溢出區(qū) 這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分塔沃，凡是和基本表發(fā)生沖突的元素蝠引，一律填入溢出表。

B樹

1.前言：
動(dòng)態(tài)查找樹主要有：二叉查找樹（Binary Search Tree），平衡二叉查找樹（Balanced Binary Search Tree）螃概，紅黑樹边坤。前三者是典型的二叉查找樹結(jié)構(gòu)，其查找的時(shí)間復(fù)雜度O(log2N)與樹的深度相關(guān)谅年，那么降低樹的深度自然會(huì)提高查找效率茧痒。
但是咱們有面對(duì)這樣一個(gè)實(shí)際問題：就是大規(guī)模數(shù)據(jù)存儲(chǔ)中，實(shí)現(xiàn)索引查詢這樣一個(gè)實(shí)際背景下融蹂，樹節(jié)點(diǎn)存儲(chǔ)的元素?cái)?shù)量是有限的（如果元素?cái)?shù)量非常多的話旺订，查找就退化成節(jié)點(diǎn)內(nèi)部的線性查找了），這樣導(dǎo)致二叉查找樹結(jié)構(gòu)由于樹的深度過大而造成磁盤I/O讀寫過于頻繁超燃，進(jìn)而導(dǎo)致查詢效率低下（為什么會(huì)出現(xiàn)這種情況区拳，待會(huì)在外部存儲(chǔ)器-磁盤中有所解釋），那么如何減少樹的深度（當(dāng)然是不能減少查詢的數(shù)據(jù)量）意乓，一個(gè)基本的想法就是：采用多叉樹結(jié)構(gòu)（由于樹節(jié)點(diǎn)元素?cái)?shù)量是有限的樱调，自然該節(jié)點(diǎn)的子樹數(shù)量也就是有限的）。
也就是說届良，因?yàn)榇疟P的操作費(fèi)時(shí)費(fèi)資源笆凌，如果過于頻繁的多次查找勢(shì)必效率低下。那么如何提高效率士葫，即如何避免磁盤過于頻繁的多次查找呢乞而？根據(jù)磁盤查找存取的次數(shù)往往由樹的高度所決定，所以慢显，只要我們通過某種較好的樹結(jié)構(gòu)減少樹的結(jié)構(gòu)盡量減少樹的高度爪模，那么是不是便能有效減少磁盤查找存取的次數(shù)呢？那這種有效的樹結(jié)構(gòu)是一種怎樣的樹呢荚藻？
這樣我們就提出了一個(gè)新的查找樹結(jié)構(gòu)——多路查找樹屋灌。根據(jù)平衡二叉樹的啟發(fā)，自然就想到平衡多路查找樹結(jié)構(gòu)应狱，也就是這篇文章所要闡述的第一個(gè)主題B~tree共郭，即B樹結(jié)構(gòu)(后面，我們將看到侦香，B樹的各種操作能使B樹保持較低的高度落塑，從而達(dá)到有效避免磁盤過于頻繁的查找存取操作，從而有效提高查找效率)罐韩。
B-tree（B-tree樹即B樹憾赁，B即Balanced，平衡的意思）這棵神奇的樹是在Rudolf Bayer寫的一篇論文《Organization and Maintenance of Large Ordered Indices》中首次提出的散吵，闡述了B-tree名字來源以及相關(guān)的開源地址）龙考。
3.B- 樹
3.1什么是B-樹
具體講解之前蟆肆，有一點(diǎn)，再次強(qiáng)調(diào)下：B-樹晦款，即為B樹炎功。因?yàn)锽樹的原英文名稱為B-tree，而國(guó)內(nèi)很多人喜歡把B-tree譯作B-樹缓溅，其實(shí)蛇损，這是個(gè)非常不好的直譯，很容易讓人產(chǎn)生誤解坛怪。如人們可能會(huì)以為B-樹是一種樹淤齐，而B樹又是一種一種樹。而事實(shí)上是袜匿，B-tree就是指的B樹更啄。特此說明。
我們知道居灯，B 樹是為了磁盤或其它存儲(chǔ)設(shè)備而設(shè)計(jì)的一種多叉（下面你會(huì)看到祭务，相對(duì)于二叉，B樹每個(gè)內(nèi)結(jié)點(diǎn)有多個(gè)分支怪嫌，即多叉）平衡查找樹义锥。與本blog之前介紹的紅黑樹很相似，但在降低磁盤I/0操作方面要更好一些喇勋。許多[數(shù)據(jù)庫(kù)]系統(tǒng)都一般使用B樹或者B樹的各種變形結(jié)構(gòu)缨该，如下文即將要介紹的B+樹偎行，B樹來存儲(chǔ)信息川背。
B樹與紅黑樹最大的不同在于，B樹的結(jié)點(diǎn)可以有許多子女蛤袒，從幾個(gè)到幾千個(gè)熄云。那為什么又說B樹與紅黑樹很相似呢?因?yàn)榕c紅黑樹一樣，一棵含n個(gè)結(jié)點(diǎn)的B樹的高度也為O（lgn）妙真，但可能比一棵紅黑樹的高度小許多缴允，應(yīng)為它的分支因子比較大。所以珍德，B樹可以在O（logn）時(shí)間內(nèi)练般，實(shí)現(xiàn)各種如插入（insert），刪除（delete）等動(dòng)態(tài)集合操作锈候。
如下圖所示薄料，即是一棵B樹，一棵關(guān)鍵字為英語(yǔ)中輔音字母的B樹泵琳，現(xiàn)在要從樹種查找字母R（包含n[x]個(gè)關(guān)鍵字的內(nèi)結(jié)點(diǎn)x摄职，x有n[x]+1]個(gè)子女（也就是說誊役，一個(gè)內(nèi)結(jié)點(diǎn)x若含有n[x]個(gè)關(guān)鍵字，那么x將含有n[x]+1個(gè)子女）谷市。所有的葉結(jié)點(diǎn)都處于相同的深度蛔垢，帶陰影的結(jié)點(diǎn)為查找字母R時(shí)要檢查的結(jié)點(diǎn)）：
用階定義的B樹
B 樹又叫平衡多路查找樹。一棵m階的B 樹 (注：切勿簡(jiǎn)單的認(rèn)為一棵m階的B樹是m叉樹迫悠，雖然存在[四叉樹]鹏漆，[八叉樹]，[KD][樹]创泄，及vp/R樹/R樹/R+樹/X樹/M樹/線段樹/希爾伯特R樹/優(yōu)先R樹等空間劃分樹甫男，但與B樹完全不等同)的特性如下*：
樹中每個(gè)結(jié)點(diǎn)最多含有m個(gè)孩子（m>=2）；

除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外验烧，其它每個(gè)結(jié)點(diǎn)至少有[ceil(m / 2)]個(gè)孩子（其中ceil(x)是一個(gè)取上限的函數(shù)）板驳；

若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有2個(gè)孩子（特殊情況：沒有孩子的根結(jié)點(diǎn)碍拆，即根結(jié)點(diǎn)為葉子結(jié)點(diǎn)若治，整棵樹只有一個(gè)根節(jié)點(diǎn)）；

所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層感混，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部接點(diǎn)或查詢失敗的接點(diǎn)端幼，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針都為null)弧满；（讀者反饋@冷岳：這里有錯(cuò)婆跑，葉子節(jié)點(diǎn)只是沒有孩子和指向孩子的指針，這些節(jié)點(diǎn)也存在庭呜，也有元素滑进。@研究者July：其實(shí)，關(guān)鍵是把什么當(dāng)做葉子結(jié)點(diǎn)募谎，因?yàn)槿缂t黑樹中扶关，每一個(gè)NULL指針即當(dāng)做葉子結(jié)點(diǎn)，只是沒畫出來而已）数冬。

每個(gè)非終端結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息： (n节槐，P0，K1拐纱，P1铜异，K2，P2秸架，......揍庄，Kn，Pn)咕宿。其中： a) Ki (i=1...n)為關(guān)鍵字币绩，且關(guān)鍵字按順序升序排序K(i-1)< Ki蜡秽。 b) Pi為指向子樹根的接點(diǎn)，且指針P(i-1)指向子樹種所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki缆镣，但都大于K(i-1)芽突。 c) 關(guān)鍵字的個(gè)數(shù)n必須滿足： [ceil(m / 2)-1]<= n <= m-1。如下圖所示：

平衡二叉樹

平衡二叉樹(Balanced Binary Tree)又被稱為AVL樹(有別于AVL算法)董瞻，且具有以下性質(zhì):它是一 棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1寞蚌，并且左右兩個(gè)子樹都是一棵平衡二叉樹。構(gòu)造與調(diào)整方法 平衡二叉樹的常用[算法]有紅黑樹钠糊、AVL挟秤、Treap等。 最小二叉平衡樹的節(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ù)量攀甚。
我們知道，對(duì)于一般的二叉搜索樹(Binary Search Tree)岗喉，其期望高度(即為一棵平衡樹時(shí))為log2n秋度，其各操作的時(shí)間復(fù)雜度(O(log2n))同時(shí)也由此而決定。但是钱床，在某些極端的情況下(如在插入的序列是有序的時(shí))荚斯，二叉搜索樹將退化成近似鏈或鏈，此時(shí)查牌，其操作的時(shí)間復(fù)雜度將退化成線性的事期，即O(n)。我們可以通過[隨機(jī)化]建立二叉搜索樹來盡量的避免這種情況僧免，但是在進(jìn)行了多次的操作之后刑赶，由于在刪除時(shí)，我們總是選擇將待刪除節(jié)點(diǎn)的后繼代替它本身懂衩，這樣就會(huì)造成總是右邊的節(jié)點(diǎn)數(shù)目減少，以至于樹向左偏沉金踪。這同時(shí)也會(huì)造成樹的平衡性受到破壞浊洞，提高它的操作的[時(shí)間復(fù)雜度]
[平衡二叉搜索樹](Balanced Binary Tree)具有以下性質(zhì):它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹胡岔。常用算法有紅黑樹法希、AVL、Treap靶瘸、伸展樹等苫亦。在平衡二叉搜索樹中毛肋，我們可以看到，其高度一般都良好地維持在O(log2n)屋剑，大大降低了操作的時(shí)間復(fù)雜度润匙。

度

子樹就是二叉樹的分支。度就是分支的數(shù)目唉匾。沒有分叉的二叉樹節(jié)點(diǎn)的度就是0度孕讳。如果一個(gè)節(jié)點(diǎn)只有一個(gè)分叉就是1度。兩個(gè)分叉就是2度的子樹巍膘。