數(shù)據(jù)結(jié)構(gòu)培訓(xùn)教程課件

數(shù)據(jù)結(jié)構(gòu)2郭育晨tsuni@數(shù)據(jù)結(jié)構(gòu)2郭育晨1樹和森林連通無回路的無向圖樹的遞歸定義一棵樹要么為空，要么由根和它的子樹組成森林——樹的集合樹和森林連通無回路的無向圖2二叉樹左子樹、右子樹二叉樹左子樹、右子樹3遍歷前序遍歷中序遍歷后序遍歷練習(xí)已知前序遍歷和中序遍歷的序列，求后序遍歷的序列遍歷前序遍歷4思考：隔三遍歷隔三遍歷:即遍歷得到的序列(a1,a2,...,an)滿足:序列中任意兩個相鄰點(diǎn)在樹上的距離小于或等于3.例如下圖的一個合法遍歷為:1346527思考：隔三遍歷隔三遍歷:即遍歷得到的序列(a1,a2,...5隔三遍歷算法:由于規(guī)模大,考慮進(jìn)行構(gòu)造而不是搜索.由于是一般的樹,可以模仿二叉樹遍歷的方法.首先深度優(yōu)先遍歷無向圖成為一棵多叉樹,并標(biāo)上深度(depth),然后對每個結(jié)點(diǎn)x，考慮它的深度depth：如果depth為奇數(shù)，那么對結(jié)點(diǎn)x進(jìn)行先序遍歷；如果depth為偶數(shù)，那么對結(jié)點(diǎn)x進(jìn)行后序遍歷。用數(shù)學(xué)歸納法可以得證。隔三遍歷算法:6完全二叉樹除了底層，其他層都達(dá)到最大子節(jié)點(diǎn)個數(shù)自頂向下，同層從左往右編號0,1,2…,n-1對任意序號ii的父節(jié)點(diǎn)是(i-1)/2i的左子節(jié)點(diǎn)i*2+1i的右子節(jié)點(diǎn)i*2+2完全二叉樹除了底層，其他層都達(dá)到最大子節(jié)點(diǎn)個數(shù)7堆以小根堆為例所有父節(jié)點(diǎn)的值都小于等于子節(jié)點(diǎn)的值向上維護(hù)(插入),O(logn)向下維護(hù)(刪除),O(logn)一般用完全二叉樹實(shí)現(xiàn)堆以小根堆為例8問題總共輸入n(n<1000000)個不同的數(shù)，每個數(shù)介于(0-1000000)之間，輸入過程中會不定時修改某些數(shù)的大小，繼續(xù)維持堆的性質(zhì)。問題總共輸入n(n<1000000)個不同的數(shù)，每個數(shù)介于(9帶HASH的堆根據(jù)題中數(shù)據(jù)范圍以及兩兩不等。A[i]代表元素大小為i的元素在堆中的位置這樣修改的復(fù)雜度降為O(1)修改后調(diào)整復(fù)雜度為O(logn)總修改的復(fù)雜度為O(logn)應(yīng)用SPFA帶HASH的堆根據(jù)題中數(shù)據(jù)范圍以及兩兩不等。10優(yōu)先隊列一般支持的操作：1.支持插入，刪除元素（間接說明支持修改）2.支持查找最大或最小元素*3.不支持合并操作，但左偏樹等可并優(yōu)先隊列仍可以支持注意：所謂的支持的操作是指復(fù)雜度在線性以下可以完成，例如O(logN),O(1)，也有可以是O(N^0.5)優(yōu)先隊列一般支持的操作：11優(yōu)先隊列一般來說優(yōu)先隊列就是用堆例子dijkstra算法用優(yōu)先隊列優(yōu)化O((n+m)logn)動態(tài)維護(hù)中位數(shù)問題，一個集合，要支持插入操作和求當(dāng)前中位數(shù)的操作，容易想到的是編程極其復(fù)雜的平衡樹，但用優(yōu)先隊列會比較方便優(yōu)先隊列一般來說優(yōu)先隊列就是用堆12哈夫曼樹問題：給定10^4個數(shù)，每次合并其中兩個數(shù)a,b，合并代價為a+b,現(xiàn)在求合并代價總和的最小值哈夫曼樹問題：13Huffman樹每次合并當(dāng)前數(shù)組中最小的兩個數(shù)Huffman樹的由來一種貪心的思想暴力復(fù)雜度O(n^2)用優(yōu)先隊列優(yōu)化,復(fù)雜度為O(nlogn)Huffman樹每次合并當(dāng)前數(shù)組中最小的兩個數(shù)14數(shù)據(jù)結(jié)構(gòu)培訓(xùn)教程15排序算法插入排序O(n^2)在已有有序序列中每次插入一個元素選擇排序O(n^2)給每個位置選擇當(dāng)前元素最大(最小)歸并排序O(nlogn)把序列一分為二，對有序序列歸并排序算法插入排序O(n^2)16快速排序基本思想任取一個數(shù)把數(shù)列分成兩段——它左邊的數(shù)都比它小，它右邊的數(shù)都比它大此時這個數(shù)就在目標(biāo)序列中它的位置上對兩個子段分別進(jìn)行排序時間復(fù)雜度最壞O(n^2)，期望O(nlogn)快速排序基本思想17其他排序法堆排序O(nlogn)基數(shù)排序……..其他排序法堆排序O(nlogn)18穩(wěn)定性選擇排序不穩(wěn)定插入排序穩(wěn)定快速排序不穩(wěn)定歸并排序穩(wěn)定堆排序不穩(wěn)定穩(wěn)定性選擇排序不穩(wěn)定19哈希表Hashtable,也叫散列表是根據(jù)關(guān)鍵碼值(Keyvalue)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。Hash函數(shù)哈希表Hashtable,也叫散列表20字符串的hash函數(shù)intELFhash(char*key){unsignedlongh=0;while(*key){h=(h<<4)+*key++;unsignedlongg=h&0Xf0000000L;if(g)h^=g>>24;h&=~g;}returnh%M;}字符串的hash函數(shù)intELFhash(char*ke21沖突returnh%M;一般來說M是一個大質(zhì)數(shù)沖突的解決開散列法閉散列法沖突returnh%M;22幾個例子給一個學(xué)生信息的列表，根據(jù)姓名查詢學(xué)生信息走迷宮的時候判斷某個格子是否走過幾個例子給一個學(xué)生信息的列表，根據(jù)姓名查詢學(xué)生信息23Hash表推薦閱讀2005年IOI國家集訓(xùn)隊論文李羽修《Hash函數(shù)的設(shè)計優(yōu)化》另外為圖方便，C++里用map<T1,T2>（實(shí)際是紅黑樹）來實(shí)現(xiàn)hash的映射編程上會比較方便Hash表推薦閱讀24并查集查找一個元素在哪個集合中合并兩個集合用森林實(shí)現(xiàn)并查集，用樹根表示集合查找查找某個元素所在樹的樹根，同時壓縮路徑合并較小的集合樹根的父親設(shè)為較大集合的根并查集查找一個元素在哪個集合中25并查集時間效率O(m*f(m,n)),f是Ackermann函數(shù)的某個反函數(shù)，一般認(rèn)為小于5應(yīng)用查找兩個元素是否在同一個集合中并查集時間效率O(m*f(m,n)),26poi9806相等的單詞讓二進(jìn)制串a(chǎn),b,c,d,e分別為長度為4，2，4，4，2的5個變量。考慮以下等式：1bad1=acbe。問有多少種變量取值使得等式成立poi9806相等的單詞讓二進(jìn)制串a(chǎn),b,c,d,e分別為長27poi98061bad1=acbe位置組：(1,4,7,12),(2,5,9),(3,6,10),(8),(11)這個等式有16種不同的解答方案。poi98061bad1=acbe28排序二叉樹又稱二叉搜索樹,二叉檢索樹具有以下性質(zhì)對于任意一個父親節(jié)點(diǎn)的值k它的左子樹所有節(jié)點(diǎn)的值都<=k它的右子樹所有節(jié)點(diǎn)的值都>=k基本操作插入、刪除、查找排序二叉樹又稱二叉搜索樹,二叉檢索樹29平衡問題當(dāng)排序二叉樹的高度接近logn的時候，它是良態(tài)的，插入、刪除、查找O(logn)當(dāng)排序二叉樹的高度接近n的時候，比較像一個鏈，O(n)自平衡樹平衡問題當(dāng)排序二叉樹的高度接近logn的時候，它是良態(tài)的，插30平衡樹源自普通的排序二叉樹(二叉排序樹，BST)平衡樹的純手寫版現(xiàn)今比賽比較少用沒有用到高級功能的話一般用set或map代替，非常方便,甚至用來當(dāng)作優(yōu)先隊列如果要用到高級功能的話可以嘗試用線段樹或樹狀數(shù)組代替手寫版種類：RB-tree,AVL,splay,treap=tree+heap,SBT(推薦)平衡樹源自普通的排序二叉樹(二叉排序樹，BST)31平衡樹旋轉(zhuǎn)操作2007IOI國家集訓(xùn)隊論文陳啟峰 SizeBalancedTree平衡樹旋轉(zhuǎn)操作32平衡樹平衡樹常用基本功能：1.插入，刪除2.求最大，最小，求排序后的前驅(qū)和后繼平衡樹不太常用的高級功能1.求第K大2.合并NOI2004郁悶的出納員平衡樹平衡樹常用基本功能：33線段樹線段樹34線段樹區(qū)間統(tǒng)計問題線段覆蓋基本操作建樹、插入或刪除一條線段RMQ求數(shù)列任意區(qū)間的最大值、最小值線段樹區(qū)間統(tǒng)計問題35離散化統(tǒng)計離散化統(tǒng)計36例子在數(shù)軸上進(jìn)行一系列操作。每次操作有兩種類型，一種是在線段[a,b]上涂上顏色，另一種將[a,b]上的顏色擦去。問經(jīng)過一系列的操作后，有多少條單位線段[k,k+1]被涂上了顏色。例子在數(shù)軸上進(jìn)行一系列操作。每次操作有兩種類型，一種是在線段37刪除的改進(jìn)一般來說線段樹中線段的刪除只能把已經(jīng)放入的線段刪掉改進(jìn)的實(shí)現(xiàn)方法見IOI2004國家集訓(xùn)隊論文薛矛《解決動態(tài)統(tǒng)計問題的兩把利刃》刪除的改進(jìn)一般來說線段樹中線段的刪除只能把已經(jīng)放入的線段刪掉38推廣這是一棵以矩形(1,1,4,3)為根的矩形樹：(1,1)(4,3)(1,2)(2,3)(2,2)(4,3)(1,1)(2,2)(2,1)(4,2)(2,2)(3,3)(3,2)(4,3)(2,1)(3,2)(3,1)(4,2)推廣這是一棵以矩形(1,1,4,3)為根的矩形樹：(1,1)39樹狀數(shù)組相對于線段樹而言：局限性：修改操作必須針對點(diǎn)查詢操作區(qū)間左端點(diǎn)必須是起點(diǎn)優(yōu)點(diǎn)：編程復(fù)雜度巨低時空效率遠(yuǎn)高于線段樹樹狀數(shù)組相對于線段樹而言：40問題給定1000個字符串，每個長度不超過10000，現(xiàn)在請統(tǒng)計出現(xiàn)次數(shù)在前100次的字符串內(nèi)容，并將其內(nèi)容以及次數(shù)輸出注：只有小寫字母問題給定1000個字符串，每個長度不超過10000，現(xiàn)在請統(tǒng)41Trie（字典樹）structnode{ charc; structnode*a[26];}考慮時間？考慮空間？時間復(fù)雜度1000*10000*（對當(dāng)前所有字符串取出前100個)加堆優(yōu)化以后(1000*10000*log100)=7*10^75S可以通過空間復(fù)雜度(最壞不到10^7)，實(shí)際中大大節(jié)省空間Trie（字典樹）structnode42Trie樹優(yōu)化字符串查找，查找復(fù)雜度為字符串長度，經(jīng)常作為某一個算法某一步的優(yōu)化經(jīng)典應(yīng)用，最短分詞算法1.給出詞典2.給出句子3.用最少詞組切分句子Trie樹進(jìn)階：字符串匹配自動機(jī)Trie樹優(yōu)化字符串查找，查找復(fù)雜度為字符串長度，經(jīng)常作為某43LCA問題在一棵有根樹上，對給定任意兩個節(jié)點(diǎn)u,v求它們的最近公共祖先樸素算法在線算法離線算法Tarjan算法2007年IOI國家集訓(xùn)隊論文郭華陽 RMQ與LCA問題LCA問題在一棵有根樹上，對給定任意兩個節(jié)點(diǎn)u,v求它們的最44練習(xí)題Huffman樹PKU3253優(yōu)先隊列PKU1442HashPKU2503并查集PKU2236PKU2492實(shí)現(xiàn)樸素的排序二叉樹(插入、刪除、查找)NOI2004郁悶的出納員(平衡樹)掌握線段樹，PKU2528,2828,2777,2886,2750練習(xí)題Huffman樹PKU325345演講完畢，謝謝觀看！演講完畢，謝謝觀看！46數(shù)據(jù)結(jié)構(gòu)2郭育晨tsuni@數(shù)據(jù)結(jié)構(gòu)2郭育晨47樹和森林連通無回路的無向圖樹的遞歸定義一棵樹要么為空，要么由根和它的子樹組成森林——樹的集合樹和森林連通無回路的無向圖48二叉樹左子樹、右子樹二叉樹左子樹、右子樹49遍歷前序遍歷中序遍歷后序遍歷練習(xí)已知前序遍歷和中序遍歷的序列，求后序遍歷的序列遍歷前序遍歷50思考：隔三遍歷隔三遍歷:即遍歷得到的序列(a1,a2,...,an)滿足:序列中任意兩個相鄰點(diǎn)在樹上的距離小于或等于3.例如下圖的一個合法遍歷為:1346527思考：隔三遍歷隔三遍歷:即遍歷得到的序列(a1,a2,...51隔三遍歷算法:由于規(guī)模大,考慮進(jìn)行構(gòu)造而不是搜索.由于是一般的樹,可以模仿二叉樹遍歷的方法.首先深度優(yōu)先遍歷無向圖成為一棵多叉樹,并標(biāo)上深度(depth),然后對每個結(jié)點(diǎn)x，考慮它的深度depth：如果depth為奇數(shù)，那么對結(jié)點(diǎn)x進(jìn)行先序遍歷；如果depth為偶數(shù)，那么對結(jié)點(diǎn)x進(jìn)行后序遍歷。用數(shù)學(xué)歸納法可以得證。隔三遍歷算法:52完全二叉樹除了底層，其他層都達(dá)到最大子節(jié)點(diǎn)個數(shù)自頂向下，同層從左往右編號0,1,2…,n-1對任意序號ii的父節(jié)點(diǎn)是(i-1)/2i的左子節(jié)點(diǎn)i*2+1i的右子節(jié)點(diǎn)i*2+2完全二叉樹除了底層，其他層都達(dá)到最大子節(jié)點(diǎn)個數(shù)53堆以小根堆為例所有父節(jié)點(diǎn)的值都小于等于子節(jié)點(diǎn)的值向上維護(hù)(插入),O(logn)向下維護(hù)(刪除),O(logn)一般用完全二叉樹實(shí)現(xiàn)堆以小根堆為例54問題總共輸入n(n<1000000)個不同的數(shù)，每個數(shù)介于(0-1000000)之間，輸入過程中會不定時修改某些數(shù)的大小，繼續(xù)維持堆的性質(zhì)。問題總共輸入n(n<1000000)個不同的數(shù)，每個數(shù)介于(55帶HASH的堆根據(jù)題中數(shù)據(jù)范圍以及兩兩不等。A[i]代表元素大小為i的元素在堆中的位置這樣修改的復(fù)雜度降為O(1)修改后調(diào)整復(fù)雜度為O(logn)總修改的復(fù)雜度為O(logn)應(yīng)用SPFA帶HASH的堆根據(jù)題中數(shù)據(jù)范圍以及兩兩不等。56優(yōu)先隊列一般支持的操作：1.支持插入，刪除元素（間接說明支持修改）2.支持查找最大或最小元素*3.不支持合并操作，但左偏樹等可并優(yōu)先隊列仍可以支持注意：所謂的支持的操作是指復(fù)雜度在線性以下可以完成，例如O(logN),O(1)，也有可以是O(N^0.5)優(yōu)先隊列一般支持的操作：57優(yōu)先隊列一般來說優(yōu)先隊列就是用堆例子dijkstra算法用優(yōu)先隊列優(yōu)化O((n+m)logn)動態(tài)維護(hù)中位數(shù)問題，一個集合，要支持插入操作和求當(dāng)前中位數(shù)的操作，容易想到的是編程極其復(fù)雜的平衡樹，但用優(yōu)先隊列會比較方便優(yōu)先隊列一般來說優(yōu)先隊列就是用堆58哈夫曼樹問題：給定10^4個數(shù)，每次合并其中兩個數(shù)a,b，合并代價為a+b,現(xiàn)在求合并代價總和的最小值哈夫曼樹問題：59Huffman樹每次合并當(dāng)前數(shù)組中最小的兩個數(shù)Huffman樹的由來一種貪心的思想暴力復(fù)雜度O(n^2)用優(yōu)先隊列優(yōu)化,復(fù)雜度為O(nlogn)Huffman樹每次合并當(dāng)前數(shù)組中最小的兩個數(shù)60數(shù)據(jù)結(jié)構(gòu)培訓(xùn)教程61排序算法插入排序O(n^2)在已有有序序列中每次插入一個元素選擇排序O(n^2)給每個位置選擇當(dāng)前元素最大(最小)歸并排序O(nlogn)把序列一分為二，對有序序列歸并排序算法插入排序O(n^2)62快速排序基本思想任取一個數(shù)把數(shù)列分成兩段——它左邊的數(shù)都比它小，它右邊的數(shù)都比它大此時這個數(shù)就在目標(biāo)序列中它的位置上對兩個子段分別進(jìn)行排序時間復(fù)雜度最壞O(n^2)，期望O(nlogn)快速排序基本思想63其他排序法堆排序O(nlogn)基數(shù)排序……..其他排序法堆排序O(nlogn)64穩(wěn)定性選擇排序不穩(wěn)定插入排序穩(wěn)定快速排序不穩(wěn)定歸并排序穩(wěn)定堆排序不穩(wěn)定穩(wěn)定性選擇排序不穩(wěn)定65哈希表Hashtable,也叫散列表是根據(jù)關(guān)鍵碼值(Keyvalue)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。Hash函數(shù)哈希表Hashtable,也叫散列表66字符串的hash函數(shù)intELFhash(char*key){unsignedlongh=0;while(*key){h=(h<<4)+*key++;unsignedlongg=h&0Xf0000000L;if(g)h^=g>>24;h&=~g;}returnh%M;}字符串的hash函數(shù)intELFhash(char*ke67沖突returnh%M;一般來說M是一個大質(zhì)數(shù)沖突的解決開散列法閉散列法沖突returnh%M;68幾個例子給一個學(xué)生信息的列表，根據(jù)姓名查詢學(xué)生信息走迷宮的時候判斷某個格子是否走過幾個例子給一個學(xué)生信息的列表，根據(jù)姓名查詢學(xué)生信息69Hash表推薦閱讀2005年IOI國家集訓(xùn)隊論文李羽修《Hash函數(shù)的設(shè)計優(yōu)化》另外為圖方便，C++里用map<T1,T2>（實(shí)際是紅黑樹）來實(shí)現(xiàn)hash的映射編程上會比較方便Hash表推薦閱讀70并查集查找一個元素在哪個集合中合并兩個集合用森林實(shí)現(xiàn)并查集，用樹根表示集合查找查找某個元素所在樹的樹根，同時壓縮路徑合并較小的集合樹根的父親設(shè)為較大集合的根并查集查找一個元素在哪個集合中71并查集時間效率O(m*f(m,n)),f是Ackermann函數(shù)的某個反函數(shù)，一般認(rèn)為小于5應(yīng)用查找兩個元素是否在同一個集合中并查集時間效率O(m*f(m,n)),72poi9806相等的單詞讓二進(jìn)制串a(chǎn),b,c,d,e分別為長度為4，2，4，4，2的5個變量。考慮以下等式：1bad1=acbe。問有多少種變量取值使得等式成立poi9806相等的單詞讓二進(jìn)制串a(chǎn),b,c,d,e分別為長73poi98061bad1=acbe位置組：(1,4,7,12),(2,5,9),(3,6,10),(8),(11)這個等式有16種不同的解答方案。poi98061bad1=acbe74排序二叉樹又稱二叉搜索樹,二叉檢索樹具有以下性質(zhì)對于任意一個父親節(jié)點(diǎn)的值k它的左子樹所有節(jié)點(diǎn)的值都<=k它的右子樹所有節(jié)點(diǎn)的值都>=k基本操作插入、刪除、查找排序二叉樹又稱二叉搜索樹,二叉檢索樹75平衡問題當(dāng)排序二叉樹的高度接近logn的時候，它是良態(tài)的，插入、刪除、查找O(logn)當(dāng)排序二叉樹的高度接近n的時候，比較像一個鏈，O(n)自平衡樹平衡問題當(dāng)排序二叉樹的高度接近logn的時候，它是良態(tài)的，插76平衡樹源自普通的排序二叉樹(二叉排序樹，BST)平衡樹的純手寫版現(xiàn)今比賽比較少用沒有用到高級功能的話一般用set或map代替，非常方便,甚至用來當(dāng)作優(yōu)先隊列如果要用到高級功能的話可以嘗試用線段樹或樹狀數(shù)組代替手寫版種類：RB-tree,AVL,splay,treap=tree+heap,SBT(推薦)平衡樹源自普通的排序二叉樹(二叉排序樹，BST)77平衡樹旋轉(zhuǎn)操作2007IOI國家集訓(xùn)隊論文陳啟峰 SizeBalancedTree平衡樹旋轉(zhuǎn)操作78平衡樹平衡樹常用基本功能：1.插入，刪除2.求最大，最小，求排序后的前驅(qū)和后繼平衡樹不太常用的高級功能1.求第K大2.合并NOI2004郁悶的出納員平衡樹平衡樹常用基本功能：79線段樹線段樹80線段樹區(qū)間統(tǒng)計問題線段覆蓋基本操作建樹、插入或刪除一條線段RMQ求數(shù)列任意區(qū)間的最大值、最小值線段樹區(qū)間統(tǒng)計問題81離散化統(tǒng)計離散化統(tǒng)計82例子在數(shù)軸上進(jìn)行一系列操作。每次操作有兩種類型，一種是在線段[a,b]上涂上顏色，另一種將[a,b]上的顏色擦去。問經(jīng)過一系列的操作后，有多少條單位線段[k,k+1]被涂上了顏色。例子在數(shù)軸上進(jìn)行一系列操作。每次操作有兩種類型，一種是在線段83刪除的改進(jìn)一般來說線段樹中線段的刪除只能把已經(jīng)放入的線段刪掉改進(jìn)的實(shí)現(xiàn)方法見IOI2004國家集訓(xùn)隊論文薛矛《解決動態(tài)統(tǒng)計問題的兩把利刃》刪除的改進(jìn)一般來說線段樹中線段的刪除只能把已經(jīng)放入的線段刪掉84推廣這是一棵以矩形(1,1,4,3)為根的矩形樹：(1,1)(4,3)(1,2)(2,3)(2,2)(4,