跳转至

手指樹

注意

此章是選讀內容，在閲讀前請確定你對函數式編程（Functional Programming）有一定了解。

簡介

手指樹（Finger Tree）是一種 純函數式 數據結構，由 Ralf Hinze 和 Ross Paterson 提出。

為什麼需要手指樹

在函數式編程中，列表是十分常見的數據類型。對於基於序列的操作，包括在兩端添加和刪除元素（雙端隊列操作），在任意節點插入、連接、刪除，查找某個滿足要求的元素，將序列拆分為子序列，幾乎所有的函數型語言都支持。但是對於高效的更多操作，這些語言很難做到。即使有相對應的實現，通常也都非常複雜，實際很難使用。

而指狀樹提供了一種純函數式的序列數據結構，它可以在均攤常量時間（amortized constant time）內完成訪問，添加到序列的前端和末尾等操作，以及在對數時間（logarithmic time）內完成串聯和隨機訪問。除了良好的漸近運行時邊界外，手指樹還非常靈活：當與元素上的幺半羣標記（monoidal tag）結合時，指狀樹可用於實現高效的隨機訪問序列、有序序列、間隔樹和優先級隊列。

基本結構

手指樹在樹的「手指」（葉子）的地方存儲數據，訪問時間為分攤常量。手指是一個可以訪問部分數據結構的點。在命令式語言（imperative language）中，這被稱做指針。在手指樹中，「手指」是指向序列末端或葉節點的結構。手指樹還在每個內部節點中存儲對其後代應用一些關聯操作的結果。存儲在內部節點中的數據可用於提供除樹類數據結構之外的功能。

  1. 手指樹的深度由下到上計算。
  2. 手指樹的第一級，即樹的葉節點，僅包含值，深度為 \(0\)。第二級為深度 \(1\)。第三級為深度 \(2\)，依此類推。
  3. 離根越近，節點指向的原始樹（在它是手指樹之前的樹）的子樹越深。這樣，沿着樹向下工作就是從葉子到樹的根，這與典型的樹數據結構相反。為了獲得這種的結構，我們必須確保原始樹具有統一的深度。在聲明節點對象時，必須通過子節點的類型進行參數化。深度為 \(1\) 及以上的脊椎上的節點指向樹，通過這種參數化，它們可以由嵌套節點表示。

將一棵樹變成手指樹

註釋

2-3 樹 是一種樹狀數據結構，其中每個帶有子節點（內部節點）的節點具有兩個子節點（\(2\) 節點）和一個數據元素或三個子節點（\(3\) 節點）和兩個數據元素。2-3 樹是 \(3\) 階 B 樹。樹外部的節點（葉節點）沒有子節點和一兩個數據元素。

我們將從平衡 2-3 樹開始這個過程。為了使手指樹正常工作，所有的葉節點需要是水平的。如下圖所示（圖片取自手指樹論文）：

手指是「一種結構，可以有效地訪問靠近特定位置的樹的節點。」要製作手指樹，我們需要將手指放在樹的左右兩端，取樹的最左邊和最右邊的內部節點並將它們拉起來，使樹的其餘部分懸在它們之間，這為我們提供了對序列末尾的均攤常量訪問時間。

這種新的數據結構被稱為手指樹。手指樹由沿其樹脊（棕色線）分佈的幾層（下方藍色框）組成：

1
2
3
4
5
6
data FingerTree a = Empty
                  | Single a
                  | Deep (Digit a) (FingerTree (Node a)) (Digit a)

data Digit a = One a | Two a a | Three a a a | Four a a a a
data Node a = Node2 a a | Node3 a a a

示例中的數字是帶有字母的節點。每個列表由樹脊上每個節點的前綴或後綴劃分。在轉換後的 2-3 樹中，頂層的數字列表似乎可以有兩個或三個長度，而較低級別的長度只有一或兩個。為了使手指樹的某些應用程序能夠如此高效地運行，手指樹允許在每個級別上有 \(1\) 到 \(4\) 個子樹。手指樹的數字可以轉換成一個列表，如：

1
type Digit a = One a | Two a a | Three a a a | Four a a a a

頂層具有類型 \(a\) 的元素，下一層具有類型節點 \(a\) 的元素，因為樹脊和葉子之間的節點，這通常意味着樹的第 \(n\) 層具有元素類型為 \(Node^{n}\) \(a\)，或 2-3 個深度為 \(n\) 的樹。這意味着 \(n\) 個元素的序列由深度為 Θ(log n) 的樹表示。距離最近端 \(d\) 的元素存儲在樹中 Θ(log d) 深度處。

雙向隊列操作

指狀樹也可以製作高效的雙向隊列。無論結構是否持久，所有操作都需要 Θ(1) 時間。它可以被看作是的隱式雙端隊列的擴展1：

  1. 用 2-3 個節點替換對提供了足夠的靈活性來支持有效的串聯。（為了保持恆定時間的雙端隊列操作，必須將 Digit 擴展為四。）
  2. 用幺半羣（monoid）註釋內部節點允許有效的分裂。
1
2
3
4
5
data ImplicitDeque a = Empty
                     | Single a
                     | Deep (Digit a) (ImplicitDeque (a, a)) (Digit a)

data Digit a = One a | Two a a | Three a a a

時間複雜度

手指樹提供了對樹的「手指」（葉子）的分攤常量時間訪問，這是存儲數據的地方，以及在較小部分的大小中連接和拆分對數時間。它還在每個內部節點中存儲對其後代應用一些關聯操作的結果。存儲在內部節點中的「摘要」數據可用於提供除樹之外的數據結構的功能。

操作 手指樹 註釋 2-3 樹 (annotated 2-3 tree) 列表（list） 向量（vector）
const,snoc \(O(1)\) \(O(\log n)\) \(O(1)\)/\(O(n)\) \(O(n)\)
viewl,viewr \(O(1)\) \(O(\log n)\) \(O(1)\)/\(O(n)\) \(O(1)\)
measure/length \(O(1)\) \(O(1)\) \(O(n)\) \(O(1)\)
append \(O(\log \min(l1, l2))\) \(O(\log n)\) \(O(n)\) \(O(m+n)\)
split \(O(\log \min(n, l-n))\) \(O(\log n)\) \(O(n)\) \(O(1)\)
replicate \(O(\log n)\) \(O(\log n)\) \(O(n)\) \(O(n)\)
fromList,toList,reverse \(O(l)\)/\(O(l)\)/\(O(l)\) \(O(l)\) \(O(1)\)/\(O(1)\)/\(O(n)\) \(O(n)\)
index \(O(\log \min(n, l-n))\) \(O(\log n)\) \(O(n)\) \(O(1)\)

應用

指狀樹可用於建造其他樹。例如，優先級隊列可以通過樹中子節點的最小優先級標記內部節點來實現，或者索引列表/數組可以通過節點的子節點中葉子的計數來標記節點來實現。其他應用包括隨機訪問序列（如下所述）、有序序列和區間樹。

手指樹可以提供平均 \(O(1)\) 的推、反轉、彈出，\(O(\log n)\) 追加和拆分；並且可以適應索引或排序序列。和所有函數式數據結構一樣，它本質上是持久的；也就是説，始終保留舊版本的樹。

對於代碼實現，Haskell 核心庫中的有限序列 Seq 的實現使用了 2-3 手指樹（Data.Sequence），OCaml 中 BatFingerTree 模塊的 實現 也使用了通用手指樹數據結構。手指樹可以使用或不使用惰性求值來實現，但惰性允許更簡單的實現。

參考資料與拓展閲讀

  1. Ralf Hinze and Ross Paterson, "Finger trees: a simple general-purpose data structure", Journal of Functional Programming 16:2 (2006) pp 197-217.
  2. Finger Tree - Wikipedia

  1. Purely Functional Data Structures, Chris Okasaki (1999) ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：isdanni
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用