樹的相關知識ppt課件(編輯修改稿)
2025-02-09 19:55 本頁面
【文章內(nèi)容簡介】 trie。我們的動機是：利用串的公共前綴來節(jié)約內(nèi)存，加快檢索速度。 ? 例如，需要保存“ puter”和“ mand”，由于它們的前三個字母是相同的，所以希望它們共享前三個字母，而只有剩下部分才進行分開儲存。 ? 例如，需要保存以下 8個單詞： ? because ? before ? beg ? beggar ? belong ? below ? day ? dead Trie的特點 ? 根節(jié)點不包含字母，除根節(jié)點外每一個節(jié)點都僅包含一個英文字母 ? 從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字母依次連起來所構(gòu)成的字母序列，稱為該節(jié)點對應的單詞。 ? 每個節(jié)點的所有兒子包含的字母都不相同。 ? 插入和刪除的時間均為 O(L) ? L為字符串的長度 應用：最長前綴 ? 給定 n個字符串，即基元 ? 給定一個字符串 T，即生物體的結(jié)構(gòu) ? 要找出字符串 T由基元構(gòu)成的前綴，使得該前綴的長度最大 ? N=100,Len(T)=500000,基元長度 L =20 樣例 基元： A， AB， BBC， CA， BA T: ABABACABAABCB ?最長前綴構(gòu)成有三種方法 ? A+BA+BA+CA+BA+AB ? AB+AB+A+CA+BA+AB ? AB+A+BA+CA+BA+AB ?長度為 11 分析 ? 為了盡快的查找到基元，我們把基元構(gòu)成一個單詞樹，也叫 trie樹。如下圖為樣例的單詞樹。 ? 該樹最多為 26叉樹，任何單詞要么是某個單詞的前綴，要么為從根到葉子結(jié)點組成的單詞。 ? 這樣我們只需要 O(L)的時間即可查找到某個單詞， L為單詞的長度。 動態(tài)規(guī)劃 ? 我們設前 j個字符已經(jīng)匹配，考慮前 i個字符是否能匹配，主要看從 i+1…j組成的字符串是否是單詞 ? 因此設 f(i)表示前 i個字符是否已匹配，若能匹配則為真 (用 1表示 ),否則為假 (用 0表示 )。則有： ??? ???，其他情況是基元，0],1[1)(1)(ijw or dandjfif時間復雜度分析 ? 每次求 f(i)需要向前找 f(j)， ijL,每移動一次 j需要判定 word(j+1,i)是否是單詞 ? 1=i=len(T),1=ijL ? 查找單詞時間復雜度為 O(L) ? 因此總時間復雜度為 O(len(T)*L2)。 ? 因為 T=500000,L=20,因此 ,5*105*202=2*108 并查集引例 ? 寫一個數(shù)據(jù)結(jié)構(gòu)，支持一下兩種操作： ? 現(xiàn)有若干個隊伍， ? 詢問兩個人是否屬于同一個隊伍 ? 合并兩個人所在的隊伍 輸入樣例 ? 第一行 n m 表示有 n個人（用 1到 n表示），在開始時沒有兩個人是屬于同一個隊伍。接下來 m行，表示 m次操作。 ? 每行操作有 2種可能： ? 1 x y 表示詢問 x和 y是不是在同一個隊伍 ? 2 x y 合并 x和 y所在的隊伍（如果 x和 y已經(jīng)在同一隊伍，不做任何操作） 樣例 ? 4 5 ? 1 1 3 ? 2 1 3 ? 1 1 3 ? 2 3 4 ? 1 4 1 ? n=100000 ? m=100000 ? NO ? YES ? YES 分析 ? 每個隊伍實際上是一個集合，兩個操作相當于： ? 詢問兩個元素是否在同一個集合 ? 合并兩個集合 ? 嘗試用樹結(jié)構(gòu)表示一個集合 ? A與 B是父子關系表示 A與 B 在同一個隊伍 問題一 ? 如何知道兩個節(jié)點是否在同一顆樹中？ 問題二 ? 怎樣合并兩顆樹？ 用雙親表示法存儲樹結(jié)構(gòu) ? 若兩種操作都解決了，如何儲存這顆樹呢？ ? n 表示一共 n個節(jié)點 ? father[1],father[2],…,father[n] ? 表示每個節(jié)點的父親節(jié)點是誰。 ? 如果 t為根，則 father[t]=0 如何尋找根節(jié)點？ ? function find(t:longint):longint。 ? var f:longint。 ? begin ? f:=t。 ? while father[f]0 do f:=father[f]。 ? find:=f。 ? end。 ? int find(int t) ? { ? int f。 ? f=t。 ? while(father[f]!=0) f=father[f]。 ? return(f)。 ? } 啟發(fā)式合并 如何合并？ ? procedure unionxy(x,y:longint)。 ? begin ? x:=find(x)。 ? y:=find(y)。 ? if xy then father[x]:=y。 ? end。 ? void ? unionxy(int x,int y) ? { ? x=find(x)。 ? y=find(y)。 ? if(x!=y) father[x]=y。 ? return。 ? } 效率分析 ? 不斷詢問紅色節(jié)點所在的根節(jié)點 路徑壓縮！ 路徑壓縮 ? f為根節(jié)點 ? while father[t]0 do ? begin ? p:=father[t]。 ? father[t]:=f。 ? t:=p。 ? end。 ? f為根節(jié)點 ? while(father[t]!=0) ? { ? p=father[t]。 ? father[t]=f。 ? t=p。 ? } 并查集的時間復雜度 ? 可以證明，經(jīng)過啟發(fā)式合并和路徑壓縮之后的并查集，執(zhí)行 m次查找的復雜度為O(mα(m)) ? 其中 α(m)是 Ackermann函數(shù)的某個反函數(shù)，你可以近似的認為它是小于 5的。所以并查集的單次查找操作的時間復雜度也幾乎是常數(shù)級的。 應 用 1： friend ? 有一個鎮(zhèn)有 N個居民。當然其中有許多人是朋友的關系。根據(jù)有名的諺語：“我朋友的朋友也是我的朋友”，所以如果 A和 B是朋友， B和 C是朋友，那么 A和 C也是朋友。 ? 你的任務是算出在這個鎮(zhèn)中最大的朋友集團為多少人。 【輸入文件】 ? 輸入文件的第一行有 2個正整數(shù)
教學課件相關推薦
鄂ICP備17016276號-1