系研一下學(xué)期-算法設(shè)計(jì)與分析課件ch3.datastructure

Chapter3BasicDataStructures(Zilei: Hash樹USTCUSTC棧棧實(shí)現(xiàn)的是一種后進(jìn)先出（LIFO）策略的動(dòng)態(tài)集用一個(gè)數(shù)組S[1:n]實(shí)現(xiàn)一個(gè)可容納n個(gè)元素的629STACK-EMPTYSTACK-EMPTY1.ifreturn3.elsereturnPUSH(S,S[S.top]=1.ifSTACK-error3.elseS.top=S.top-return隊(duì)列實(shí)現(xiàn)的是一種先進(jìn)先出（FIFO）策略的動(dòng)態(tài)集用一個(gè)數(shù)組Q[1:n]實(shí)現(xiàn)一個(gè)可容納n-1個(gè)元素的隊(duì)Q.head指向隊(duì)頭元素，Q.tail指向下一個(gè)元素要插入的位629629ENQUEUE(Q,

ifelse

ifQ.head=elsereturnUSTC雙向鏈表：每個(gè)元素一個(gè)key和兩個(gè)指針：next,哨兵L.nil位于表頭和表尾之L.L.nil.next指向表頭，L.nil.prev指向表9?USTC使用哨兵的好處是使代碼整潔，并提高效假定數(shù)據(jù)沒有排whilex≠L.nilandx.key≠x=return

LIST-INSERT(L,

LIST-DELETE(L, USTC二叉樹：節(jié)點(diǎn)xp和指針left ChildkUSTC圖圖G=(VE)，其中V為頂點(diǎn)集合，???????為邊所有的情況下 =如果圖示連通的(connected)， ?→og?? =g??)USTC給定G=(V,E)， =??，用矩陣????×??表示????, if(??,??)∈ A123A123410110200103000040010USTC給定G=(V,E)， =??，用鏈表??????[??]??表Adj[1]Adj[1]={2,Adj[2]=Adj[3]=Adj[4]=使用Θ(??+??)的存使用Θ(??+??)的存 —asparse對(duì)無(wú)向圖：∑v∈V=2USTCUSTC LEFT(i):returnRIGHT(i):return2

39324193241

USTC最大堆：A[PARENT(i)]≥A[iMAX-HEAPIFYBUILD-MAX-HEAP USTC????≤ +Θ?? =?? =??(logMAX-輸入A和i，假定當(dāng)前根節(jié)點(diǎn)的LEFT(i)和RIGHT(i)已經(jīng)都是二叉通過(guò)讓A[i]的值在最大堆中逐級(jí)下USTCMAX-通過(guò)讓A[i]的值在最大堆中逐級(jí)下USTC將一個(gè)數(shù)組A[1:n]變成一個(gè)最大loglog?? log= ?≤ =??(??)i+1,i+2,n在任意高度h上，之多有??/2?+1USTCUSTC初始時(shí)將數(shù)組A[1:n]建成一個(gè)最大互換A[1]和A[n]，然后迭代在A[1:n-1] 最大堆性每次調(diào)用BUILD-MAX-O(n)+(n-USTCUSTC(priority用 有一組元素構(gòu)成的集合，每個(gè)元素有一個(gè)支持操作(以最大優(yōu)先級(jí)隊(duì)列為例INSERT(S,把元素x插入集合S中，及返回SEXTRACT-去掉并返回S中具有最大關(guān)鍵字的元INCREASE-KEY(S,x,將元素x的關(guān)鍵字的值增加到k，這里k大于等于x的原關(guān)鍵USTC

USTC

USTChashUSTCTnTINSERT(T,DELETE(T,SEARCH(T,USTCU={0,1,…,m-用一個(gè)數(shù)組T[0:m-1]進(jìn)行USTC→USTC用一個(gè)hashh將關(guān)鍵字全域U映射到{0,1,…,m-USTCUSTC(simpleuniform每個(gè)key值等可能地被散列到任一槽中，且它們是相互獨(dú)立??=??/?? 素的期望時(shí)間為期望時(shí)間為Θ(1+??)(如果??=?? or??=??(??)，則期望時(shí)間為USTC相似的關(guān)鍵字具有截然不同的散列USTC? =??modm不應(yīng)該為2的冪2000個(gè)字符串，期望平均查找三次→即：???=??modUSTC常數(shù)因子? ??(????modm一般選取為2的冪次（移位運(yùn)算處理??

?1=525USTC用m表示一個(gè)素即：??= ??0,??1,?,?????1 with0≤????<???? ??0??1?????1，其中????是從{0,1,…m-1}中隨機(jī)選取定義?????

????????mod它在實(shí)際應(yīng)用中很有效，但計(jì)算代價(jià)較USTC每個(gè)表項(xiàng)或包含一個(gè)元素，或?yàn)楹锰幨?指針節(jié)省空間，從而提 的槽，同時(shí)提高效插入時(shí)要系統(tǒng)地探查所有表項(xiàng)直到找到一個(gè)空表項(xiàng)為這里的hash函數(shù)依賴于鍵值和探查號(hào)?:?? 0,1,…,??? →{0,1,…,???探查序列???,0,???,1??,???1)應(yīng)當(dāng)是0,1???的一個(gè)排當(dāng)表項(xiàng)被填滿時(shí)，刪除變得比USTCUSTCUSTCUSTC給定一個(gè)普通的hash函數(shù)?′??，線性探查采用如下hash???, ?′ +??mod該方法容易實(shí)現(xiàn)，但存在一次群集(primaryUSTC給定兩個(gè)普通的hash函數(shù)?1??和?2(??)，雙重散列采用???, ?1 +??? mod這里的?2??必須對(duì)??取m為2的冪次，?2??取m為素?cái)?shù)，?2??總是產(chǎn)生小于mUSTC給定裝載因子??=??<1的開放尋址hash表，對(duì)一次成功1/(1類似地，一次成功1 USTC參考如果??是一個(gè)常數(shù)，則 如果hash如果hash90%USTC USTC每一個(gè)把U映射到{0,1,…,m-如果對(duì)任意的??,??∈??,??≠??，滿足? =?(??)的?函數(shù)個(gè)數(shù)至多 ，則稱?是全域即x和y 幾率為1如果隨機(jī)地從?hash函USTC證明：參考CLRS-pp.150(Chinese =USTC情況下的搜索時(shí)間為USTCUSTCBinarysearchtree–設(shè)??為BST任一節(jié)點(diǎn)，??是左子樹任一節(jié)點(diǎn)，則??.????????.??????；是右子樹任一節(jié)點(diǎn)，則??.??????≥??.USTC包括SEARCH、MINIMUM、 假定樹的高度→TREE-SEARCH(x,ifx==NILorreturnifreturnTREE-SEARCH(x.left,

whilex≠NILandk≠ifreturnUSTCwhilex.left≠x=return

whilex.right≠x=returnifx.right≠returnTREE-y=whiley≠NILandreturn

ifx.left≠return y=whiley≠NILandreturnUSTCy=x=T.root;whilex≠NILifz.key<x.keyelsez.p=ify==T.root//emptyelseifz.key<y.leftelsey.right=z.key=v,z.left=NIL,z.right=USTCy是z的右孩y在右子樹中，但不是z的右孩USTCifu.p==T.rootelseifu.p.left=elseu.p.rightifv≠

ifz.left==elseifz.right==elsey=TREE-ify.p≠y.right=y.left=USTC創(chuàng)建一個(gè)空BST，按順序“TREE-INSERT(TUSTCUSTC??(log這不等價(jià)于樹的期望高度為??(log??)（實(shí)際上如此需要額外的證USTC定義 ????表示隨機(jī)BST的高度，????=2????k????=1+max?????1,????=2?max(?????1,?????) 量??????如下?????? iftheroothasrank0

Pr??????= =

=USTC???? ??????(2?max???1,?????→??[??]=?? ?? ??????(2?x,??) ??[??????(2?max?????1,???????= ??[??????]??[max?????1,???????2≤ ???????1+Eachtermappearstwice,andreindex.4Eachtermappearstwice,andreindex.==

USTC ??[??]≤ ???1

代入法可證明??[??]≤2??[????]≤?? =??

≤

≤3log??+

USTC??(logUSTC樹 1.23.每個(gè)葉節(jié)點(diǎn)(NIL)?=black-USTC樹示例4.如果一個(gè)結(jié)點(diǎn)是紅色的，則它的兩個(gè)子結(jié)點(diǎn)都是黑色USTC一棵具有n個(gè)鍵值 ?≤2log(??+USTC高度?′USTC ?′≥ 是??+1USTC樹上SEARCH、MIN、MAX、SUCCESSORPREDECESSOR的運(yùn)行時(shí)間為??(log操作INSERT和DELETE會(huì)引 操作本顏色修需要重構(gòu)樹的連接也保 性質(zhì)（通過(guò)“rotation”操作USTC保持中序的鍵值a∈α,b∈β,c∈γ?a≤≤b≤B≤在??(1)時(shí)間內(nèi)能夠完USTC將待插入節(jié)點(diǎn)x 通過(guò)重 性 USTC??=重USTC??=RIGHT-RIGHT-重USTCCasezyz重重USTCCase2：zyzCase3：zyzRIGHT-RIGHT-USTC??(log??(logCase1：重 Case2orcase3：執(zhí)行1-2次執(zhí)行次數(shù)??(log參考USTCOS-RANK(S,x)x→??(log 動(dòng)態(tài)集合USTCx.sizex.size=x.left.size+x.