樹的相關(guān)知識ppt課件-資料下載頁
2025-01-13 19:55本頁面
【正文】 2)將根節(jié)點的左兒子和最后一個節(jié)點交換 (3)將新的節(jié)點不斷下調(diào) ， 直到滿足堆的性質(zhì) 2 2 刪除 (實際上是不斷向下調(diào)整的過程 ) PROC down(k:longint)。{把第 k個結(jié)點往下調(diào) } begin while k+k=n do begin i:=min{ 2k,2k+1}。 {如果 2k+1不存在直接返回 k+k否則返回 2個中間的值較小的元素 } if st[i]st[k] then begin swap(i,k)。 k:=i。 end else exit end。 end。 堆的構(gòu)造就是不斷插入到堆的過程 6 2 3 5 1 分別插入權(quán)為 6,2,3,5,1的元素 6 (1) 6 (2) 2 6 (3) 2 3 6 (4) 2 3 5 6 (5) 2 3 5 1 堆的插入 .刪除 PROC add(x:longint)。 {添加一個值為 x的元素 } begin inc(n)。 st[n]:=x。 up(n) end。 PROC del(x:longint)。 {刪除一個值為 x的元素 } begin a[n]:=a[x]。 down(x) end。 ? 給定 m個實數(shù) w1, w2,…, wm,(m=2) ,要求一個具有 m個外部節(jié)點的擴(kuò)充二叉樹，每個外部 ki節(jié)點有一個 wi與之對應(yīng)，作為它的權(quán) ,使得帶權(quán)外部路徑長度 最小，其中 li是從根到外部節(jié)點的路徑長度。 應(yīng)用 1：哈夫曼樹 ??miiilw1算法 m個只有 1個節(jié)點的樹 ，并將該數(shù)的根節(jié)點權(quán)之為左右兒子權(quán)值之和 ，直到剩下一棵樹為止 應(yīng)用 2：任務(wù) ? 有 n個任務(wù)，每個任務(wù)有一個截止完成的時間 Ti和完成需要的時間 Ci?，F(xiàn)在你一個人希望從 0時刻開始完成盡量多的任務(wù)。問最多能完成多少任務(wù)？ 引例：數(shù)列操作 假設(shè)有一列數(shù) {Ai}(1≤i≤n)，支持如下兩種操作： 1. 將 Ak的值加 D。（ k, D是輸入的數(shù)） 2. 輸出 As+As+1+…+At。（ s, t都是輸入的數(shù)， S≤T） 輸入：第一行一個整數(shù) n， 第二行為 n個整數(shù)，表示 {Ai}的初始值。 第三行為一個整數(shù) m，表示操作數(shù) 下接 m行，每行描述一個操作，有如下兩種情況： ADD k d (表示將 Ak加 d， 1=k=n， d為整數(shù) ) SUM s t （表示輸出 As+…+At） 輸出：對于每一個 SUM提問，輸出結(jié)果 ? 如果按題目要求直接模擬： –每一個 ADD操作的復(fù)雜度是 O(1) –每一個 SUM操作的復(fù)雜度是 O(N) ? 可見對于 M次 SUM詢問，復(fù)雜度是 O(NM) ? 有沒有更好的方法呢？這里我們提出一種稱之為線段樹的數(shù)據(jù)結(jié)構(gòu)。 用隊列直接模擬 線段樹的定義 ? 線段樹是一棵二叉樹，記為 T(a, b)，參數(shù) a,b表示區(qū)間 [a,b]，其中 ba稱為區(qū)間的長度，記為 L。 ? 線段樹 T(a,b)也可遞歸定義為： ? 若 L1 : [a, (a+b) div 2]為 T的左兒子； ? [(a+b) div 2,b]為 T 的右兒子。 ? 若 L=1 : T為葉子節(jié)點。 表示區(qū)間 [1, 10]的線段樹樣例： [1,10] [1,5] [5,10] [1,3] [3,5] [5,7] [7,10] [1,2] [2,3] [3,4] [4,5] [5,6] [6,7] [7,8] [8,10] [8,9] [9,10] 線段樹的建立 ? 我們知道，對于長度為 n的線段建立的線段樹，至多只有 nlogn個節(jié)點，故建立線段樹的復(fù)雜度是 O(nlogn) Procedure MakeTree(a,b) Var Now:Longint Begin tot ← tot + 1 Now ← tot Tree[Now].a ← a Tree[Now].b ← b If a +1 b then Tree[Now].Left ← tot + 1 MakeTree(a, ) Tree[Now].Right ← tot + 1 MakeTree( , b) End ? ?2/)( ba ?? ?2/)( ba ?回到原問題 ? 我們用線段樹來維護(hù)序列。 ? 給線段樹的每個節(jié)點增加一個域 Tree[i].S，表示該區(qū)間內(nèi)所有值的和。 ? 對于 ADD k d操作，只需要從根節(jié)點開始遍歷線段樹中每個包含了 k的區(qū)間節(jié)點，然后修改 S域。 ? 由于這樣的區(qū)間至多只有 logn個，所以一次 ADD操作的復(fù)雜度是 O(logn) SUM操作 ? 對于待計算的區(qū)間 [s,t]： Function getsum(v):integer。 if (s=Tree[v].a) and (Tree[v].b=t) then getsum:=Tree[v].S else begin tot:=0。 if [s,t]和 Tree[v].Left表示的區(qū)間相交 then tot:=tot+getsum(Tree[v].Left)。 if [s,t]和 Tree[v].Right表示的區(qū)間相交 then tot:=tot+getsum(Tree[v].Right)。 getsum:=tot end。 ? 我們不難發(fā)現(xiàn)這個過程中所遍歷到的區(qū)間數(shù)（節(jié)點數(shù)）和線段樹的深度同階，因此時間復(fù)雜度是 O(logn) 問題的解決 ? 綜上， M次操作的時間復(fù)雜度為 O(Mlogn) ? 通過引入線段樹的數(shù)據(jù)結(jié)構(gòu)，雖然 ADD操作的復(fù)雜度提高到了 O(logn)。但 SUM操作變得更快 (O(logn))。從而也使得算法在大數(shù)據(jù)處理上更加高效。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1