數(shù)據(jù)結(jié)構(gòu)平衡二叉樹

平衡二叉樹起因：提高查找速度，避免最壞情況出現(xiàn)。如右圖情況的出現(xiàn)。DABCFEGGEDBACF平衡二叉樹平衡因子（平衡度）： 結(jié)點(diǎn)的平衡度是結(jié)點(diǎn)的左子樹的高度－右子樹的高度。平衡二叉樹： 每個(gè)結(jié)點(diǎn)的平衡因子都為＋1、－1、0的二叉樹。 或者說每個(gè)結(jié)點(diǎn)的左右子樹的高度最多差一的二叉樹。141253928635360501718730+1+1-1-1-100000000是平衡樹不是平衡樹145392863536050171830+1+2-1-100000+1-1平衡二叉樹平衡樹的Adelson算法的本質(zhì)特點(diǎn)：以插入為例：在左圖所示的平衡樹中插入數(shù)據(jù)為2的結(jié)點(diǎn)。插入之后仍應(yīng)保持平衡分類二叉樹的性質(zhì)不變。平衡樹如何用最簡單、最有效的辦法保持平衡分類二叉樹的性質(zhì)不變？平衡二叉樹141253928635360501718730+1+1-1-1-100000000141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)解決方案：不涉及到危機(jī)結(jié)點(diǎn)的父親結(jié)點(diǎn)，即以危機(jī)結(jié)點(diǎn)為根的子樹的高度應(yīng)保持不變（左圖為3）。新結(jié)點(diǎn)插入后，找到第一個(gè)平衡度不為0的結(jié)點(diǎn)（如左圖結(jié)點(diǎn)9）即可。新插入的結(jié)點(diǎn)和第一個(gè)平衡度不為0的結(jié)點(diǎn)（也可能是危機(jī)結(jié)點(diǎn)）之間的結(jié)點(diǎn)，其平衡度皆為0在調(diào)整中，僅調(diào)整那些在平衡度變化的路徑上的結(jié)點(diǎn)（如：359），其它結(jié)點(diǎn)不予調(diào)整。仍應(yīng)保持分類二叉樹的性質(zhì)不變。平衡二叉樹141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)如何用最簡單、最有效的辦法保持平衡分類二叉樹的性質(zhì)不變？23597122359712平衡二叉樹141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)關(guān)鍵：將導(dǎo)致出現(xiàn)危機(jī)結(jié)點(diǎn)的情況全部分析，就可以使得平衡分類二叉樹的性質(zhì)保持不變14932528635360501718730+1+1-1-1-100000001200平衡二叉樹左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹上進(jìn)行的調(diào)整）的情況分析：1、LL情況：（LL：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子樹的左子樹上）AB+1h-10+2+1hh-1h-1LL改組BLBRARBA0h0h-1h-1BLBRAR危機(jī)結(jié)點(diǎn)改組前：高度為h+1中序序列：ABBLBRAR改組后：高度為h+1中序序列：ABBLBRAR注意：改組后平衡度為0AB平衡二叉樹左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹上進(jìn)行的調(diào)整）的情況分析：2、LR情況：（LR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子樹的右子樹上）情況A：AB+1h-10+2-1h-1LR改組BLAR危機(jī)結(jié)點(diǎn)改組前：高度為h+1中序序列：注意：改組后平衡度為0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改組后：高度為h+1中序序列：ABBLARCCLCRA左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹上進(jìn)行的調(diào)整）的情況分析：2、LR情況：（LR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子樹的右子樹上）情況B：AB+1h-10+2-1h-1LR改組BLAR危機(jī)結(jié)點(diǎn)改組前：高度為h+1中序序列：注意：改組后平衡度為+1,0,0CBCCRCLh-1h-2h-20-1CB0h-1h-1BLARACRh-1CLh-2+10ABBLARCCRCL改組后：高度為h+1中序序列：AABBLARCCRCL定理：具有N個(gè)結(jié)點(diǎn)的平衡樹，高度h滿足：log2(N+1)<=h<=1.44log2(N+1)-0.328;最大高度為log2(sqr(N+1))-2

如：高度2的平衡樹，豐滿樹結(jié)點(diǎn)個(gè)數(shù)最多為2h-1個(gè)。查找分析為什么采用B_樹和B+樹：大量數(shù)據(jù)存放在外存中，通常存放在硬盤中。由于是海量數(shù)據(jù)，不可能一次調(diào)入內(nèi)存。因此，要多次訪問外存。但硬盤的驅(qū)動(dòng)受機(jī)械運(yùn)動(dòng)的制約，速度慢。所以，主要矛盾變?yōu)闇p少訪外次數(shù)。在1970年由Rbayer和Emacreight提出用B_樹作為索引組織文件。提高訪問速度、減少時(shí)間。 B_樹和B+樹用二叉樹組織文件，當(dāng)文件的記錄個(gè)數(shù)為100，000時(shí)，要找到給定關(guān)鍵字的記錄，需訪問外存17次（log100,000）502510751535609020304055708095索引文件數(shù)據(jù)文件文件頭，可常駐內(nèi)存文件訪問示意圖：索引文件、數(shù)據(jù)文件存在盤上B_樹和B+樹B_樹是一種多分支數(shù)，首先介紹m階B_樹：定義：m階B_樹滿足或空，或： A、根結(jié)點(diǎn)要么是葉子，要么至少有兩個(gè)兒子 B、除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù) 為:m/2<=s<=mB_樹和B+樹C、有s個(gè)兒子的非葉結(jié)點(diǎn)具有n=s－1個(gè)關(guān)鍵字，即:s=n+1這些結(jié)點(diǎn)的數(shù)據(jù)信息為：（n,A0,K1,R1,A1,K2,R2,A2,…Kn,Rn,An）這里：

n：關(guān)鍵字的個(gè)數(shù)A0：<K1的結(jié)點(diǎn)的地址（指在該B_樹中）K1：關(guān)鍵字R1：關(guān)鍵字=K1的數(shù)據(jù)記錄在硬盤中的地址A2：>K1且<K2的結(jié)點(diǎn)的地址（指在該B_樹中）余類推…An：>Kn的結(jié)點(diǎn)的地址（指在該B_樹中） 注意：K1<=K2<=…...<=KnD、所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層上，不帶信息（可認(rèn)為外部結(jié)點(diǎn)或失敗結(jié)點(diǎn)）。B_樹和B+樹m=4階B_樹。除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù)至少為m/2=2個(gè)；結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)至少為1。該B_樹的深度為4。葉子結(jié)點(diǎn)都在第4層上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第1層第2層第3層(L層)第4層(L＋1層)B_樹和B+樹查找過程，類似于二叉樹的查找。如查找關(guān)鍵字為KEY的記錄。從根開始查找，如果Ki=KEY則查找成功，Ri為關(guān)鍵字為KEY的記錄的地址。 若Ki<KEY<Ki+1;查找Ai指向的結(jié)點(diǎn) 若KEY<K1;查找A0指向的結(jié)點(diǎn) 若KEY>Kn;查找An指向的結(jié)點(diǎn) 若找到葉子，則查找失敗。注意：每次查找將去掉（s-1）/s個(gè)分支，比二分查找快得多。B_樹的查找代價(jià)分析：設(shè)關(guān)鍵字的總數(shù)為N，求m階B_樹的最大層次L。故：L＝logm/2（（N+1）/2）+1設(shè)N＝1000，000且m＝256，則L<=3；最多3次訪問外存可找到所有的記錄。B_樹的查找代價(jià)分析：1、確定插入位置，將結(jié)點(diǎn)插入到第L層（注意：第L+1層為葉子結(jié)點(diǎn)）2、找到插入位置，將關(guān)鍵字和其它信息按序插入。3、若被插入結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)>m-1,則該結(jié)點(diǎn)滿。必須分裂成兩個(gè)結(jié)點(diǎn)。否則不滿，結(jié)束。如結(jié)點(diǎn)原為：（m-1,A0,(K1,A1),(K2,A2),………(Km-1,Am-1)）插入一個(gè)關(guān)鍵字之后變?yōu)椋海╩,A0,(K1,A1),(K2,A2),………(Km,Am)）該結(jié)點(diǎn)將進(jìn)行分裂： …………... (Km/2,p‘

)…………...（m/2-1,A0,(K1,A1),…(Km/2,Am/2)）（m-m/2,Am/2,…(Km,Am)）生成新結(jié)點(diǎn)p‘,將原結(jié)點(diǎn)的后半部分復(fù)制過去。若分裂一直進(jìn)行到根結(jié)點(diǎn)，樹可能長高一層。B_樹的插入操作例如：3階B_樹的插入操作。m=3,m/2-1=1;至少1個(gè)關(guān)鍵字，二個(gè)兒子結(jié)點(diǎn)。3，127243024，3045，7053902610039506185345，70539026100395061851230324457053902610039506185127303245390261003950618512745707插入B_樹和B+樹1、查找具有給定鍵值的關(guān)鍵字Ki2、如果在第L層，可直接刪除（注意：第L+1層為葉子結(jié)點(diǎn)），轉(zhuǎn)4。3、否則，則首先生成“替身”。用右子樹中的最左面的結(jié)點(diǎn)的關(guān)鍵字值，即處于第L層上的最小關(guān)鍵字值取代。然后，刪除第L層上的該關(guān)鍵字。B_樹的刪除操作4、從第L層開始進(jìn)行刪除。

A、不動(dòng)：若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)仍處于m/2-1和m-1之間。則結(jié)束。

B、借：若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)原為m/2-1。而它們的左或右鄰居結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)>m/2-1;則借一個(gè)關(guān)鍵字過來。處理結(jié)束。C、并：若該結(jié)點(diǎn)的左或右鄰居結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)為m/2-1;則執(zhí)行合并結(jié)點(diǎn)的操作。B_樹的刪除操作第L層：找到了被刪結(jié)點(diǎn)的替身。B_樹的刪除操作（………….(Ki,Ai),(Ki+1,Ai+1),………….）（A0’,(K1’,A1’)………）（A0’‘,(K1’‘,A1’‘)………）……K1L………例如：3階B_樹的刪除操作。m=3,m/2-1=1;至少1個(gè)關(guān)鍵字，二個(gè)兒子結(jié)點(diǎn)。324455390371005061，70被刪關(guān)鍵字324456190371005370借：向被刪結(jié)點(diǎn)方向旋轉(zhuǎn)假定再刪除該關(guān)鍵字32445903710061，70假定再刪除該關(guān)鍵字3，24459010061，703，24459010061，70并并并并：和父結(jié)點(diǎn)的一個(gè)關(guān)鍵字、及鄰居合并。有可能進(jìn)行到根，使B_樹的深度降低一層！哈希查找表前述的查找方法建立在“比較”的基礎(chǔ)上，查找的次數(shù)依賴于查找過程中進(jìn)行比較的次數(shù)。問題：能否不用比較就能直接計(jì)算出記錄的存儲(chǔ)地址，從而找到所要的結(jié)點(diǎn)？----采用散列（hash）方法。散列表和查找散列表---是根據(jù)設(shè)定的散列函數(shù)和相應(yīng)解決沖突的方法為一組結(jié)點(diǎn)建立的一張表，表中的結(jié)點(diǎn)的存儲(chǔ)位置依賴于設(shè)定的散列函數(shù)和處理沖突的方法。散列（又稱雜湊、哈希）的基本思想：以結(jié)點(diǎn)的鍵值k為自變量，通過一定的函數(shù)關(guān)系h計(jì)算出對(duì)應(yīng)的函數(shù)值h(k),把這個(gè)值解釋為結(jié)點(diǎn)的存儲(chǔ)地址（散列地址），將結(jié)點(diǎn)存入該地址中去。函數(shù)h---散列函數(shù)h(k)---散列地址基本區(qū)---分配給散列表的連續(xù)存儲(chǔ)空間。哈希查找表將31個(gè)常用的英文單詞，映射到M存區(qū)。設(shè)m=41,映射是等可能性的。哈希表014039A、AND、……YOU:總的可能分布為4131，不沖突的分布為A41；不沖突的可能性為1/10,000,000簡短的結(jié)論：選取好的hashing函數(shù)非常困難，不沖突的可能性非常小沖突；若ki!=kk;但f(ki)=f(kk)減少?zèng)_突的方法：好的hashing函數(shù)減少負(fù)載系數(shù)哈希表014039哈希查找表哈希表014039hashing函數(shù)直接地址法：H(key)=key或H(key)=a×key＋b如：k1,k2分別有值10、1000；選10、1000作為存放地址。簡單、不經(jīng)濟(jì)。除留余數(shù)法：H(key)=keyMODp或H(key)=keyMODp+c這里p<m最常用，余數(shù)總在0～p-1之間。哈希查找表hashing函數(shù)除留余數(shù)法：H(key)=keyMODp或H(key)=keyMODp+c這里p<m最常用，余數(shù)總在0～p-1之間。通常選<m的最大質(zhì)數(shù)。如：m=1024,則p=1019選取p為質(zhì)數(shù)的理由：設(shè)key值都為奇數(shù)，選p為偶數(shù)；則H(key)=keyMODp，結(jié)果為奇數(shù)，一半單元被浪費(fèi)掉。設(shè)key值都為5的倍數(shù)，選p為95；則H(key)=keyMODp，結(jié)果為：0、5、10、15、……90奇數(shù)。4/5的單元被浪費(fèi)掉。hashing函數(shù)折疊法及位移法：key=381，412，975選取768或570作為散列地址（在m＝1000情況下）。38141297517689752143811570＋＋hashing函數(shù)基數(shù)轉(zhuǎn)換法：key=236076基數(shù)為10，看成是13進(jìn)制的。則：（236075）13＝841547；選取4154作為散列地址（在m＝10000情況下）。平方取中法：（4731）2＝22382361；選取82（在m＝100情況下）。

H(17)=6H(60)=5H(29)=7H(38)=5012345678910Hashing表1760293838開放定址法：線性探測在散列法：假定采用的hashing函數(shù)為：H(key)=keyMOD11假定的關(guān)鍵字序列為：17、60、29、38……；它們的散列過程為：當(dāng)散列38時(shí)發(fā)生沖突，同60爭奪第5個(gè)單元解決辦法：探測下一個(gè)空單元步長：H(key)=(key+di)MOD11其中：di為1、2……10注意：可取其它步長，如3hashing函數(shù)沖突的解決辦法沖突：初級(jí)沖突：不同關(guān)鍵字值的結(jié)點(diǎn)得到同一個(gè)散列地址。若對(duì)于不同的鍵值k1和k2,且k1<>k2,但h(k1)=h(k2)，即具有相同的散列地址，稱為沖突。

二次聚集：同不同散列地址的結(jié)點(diǎn)爭奪同一個(gè)單元。結(jié)果：沖突加劇，最壞時(shí)可能達(dá)到O（n）級(jí)代價(jià)。同義詞---發(fā)生沖突的兩個(gè)或多個(gè)鍵值。解決辦法：改變步長：選和m互質(zhì)的數(shù)作為步長，如3、5、7……如選步長為5，用H(key)=(key+5)MOD11H(key)=(key+5×2)MOD11H(key)=(key+5×3)MOD11等進(jìn)行下一個(gè)空的單元，直到找到為止。隨機(jī)地改變步長，如取步長序列：2，7，4，3，6，1，5如用H(key)=(key+2)MOD11H(key)=(key+7)MOD11H(key)=(key+4)MOD11等進(jìn)行探測下一個(gè)空的單元，直到找到為止。沖突的解決辦法其它解決辦法：出現(xiàn)沖突時(shí)：H(key)=(key+di)MODp其中：di為+/-12、+/-22……+/-k2（k<=m/2）；稱之為二次探測再散列或者取為偽隨機(jī)數(shù)；稱之為隨機(jī)再探測散列。沖突的解決辦法再hashing法：出現(xiàn)沖突時(shí)，采用多個(gè)hashing函數(shù)計(jì)算散列地址，直到找到空單元為止。或者用另一個(gè)hashing函數(shù)作為步長進(jìn)行探測，找到下一個(gè)空單元。如：H1(key)=keyMOD11H2(key)=(key+MOD9〕＋1設(shè)key=42,則H1(42)=9，H2(42)=7。首先探測9號(hào)單元，如空則結(jié)束。否則，以7作為步長探測下一個(gè)空單元，直到找到下一個(gè)空單元為止。探測序列為：9、5、1、8、4、0、7、3、10、6、2。沖突的解決辦法鏈地址法：將具有同