算法合集之左偏樹的特點及其應(yīng)用(已修改)
2024-10-28 20:30 本頁面
【正文】 左偏樹的特點及其應(yīng)用 廣東省中山市第一中學(xué) 黃源河 Winter Camp 2021 演示稿 2 左偏樹的定義 ? 左偏樹 (Leftist Tree)是一種 可并堆 (Mergeable Heap) ，它除了支持優(yōu)先隊列的三個基本操作（插入，刪除，取最小節(jié)點），還支持一個很特殊的操作 ——合并操作。 ? 左偏樹是一棵 堆有序 (Heap Ordered)二叉樹。 ? 左偏樹滿足 左偏性質(zhì) (Leftist Property)。 Winter Camp 2021 演示稿 3 左偏樹的定義 —— 左偏性質(zhì) ? 定義一棵左偏樹中的 外節(jié)點 (External Node) 為左子樹或右子樹為空的節(jié)點。 ? 定義節(jié)點 i 的 距離 (dist(i)) 為節(jié)點 i 到它的后代中，最近的外節(jié)點所經(jīng)過的邊數(shù)。 ? 任意節(jié)點的左子節(jié)點的距離不小于右子節(jié)點的距離（左偏性質(zhì)）。 ? 由左偏性質(zhì)可知，一個節(jié)點的距離等于以該節(jié)點為根的子樹最右路徑的長度。 Winter Camp 2021 演示稿 4 左偏樹的性質(zhì) ? 定理：若一棵左偏樹有 N個節(jié)點，則該左偏樹的距離不超過 ?log(N+1)? 1。 最右路徑 : A－ C－ G 最右路徑節(jié)點數(shù) = 3 距離 = 2 8個節(jié)點的左偏樹的最大距離： ?log(8+1)? 1 = 2 A B D 0 0 0 1 2 E H F 0 G 0 1 C 最右路徑長度即為左偏樹的距離 Winter Camp 2021 演示稿 5 左偏樹的操作 ? 左偏樹支持下面這些操作： – MakeNull —— 初始化一棵空的左偏樹 – Merge —— 合并兩棵左偏樹 – Insert —— 插入一個新節(jié)點 – Min —— 取得最小節(jié)點 – DeleteMin —— 刪除最小節(jié)點 – Delete —— 刪除任意已知節(jié)點 – Decrease —— 減小一個節(jié)點的鍵值 Winter Camp 2021 演示稿 6 左偏樹的操作 —— 合并 ? 合并操作是遞歸進(jìn)行的 a b a
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1