一、簡介
手指樹（Finger Tree）是一種純函數(shù)式數(shù)據(jù)結(jié)構(gòu)，由 Ralf Hinze 和 Ross Paterson 提出。
二、為什么需要手指樹？
在函數(shù)式編程中，列表是十分常見的數(shù)據(jù)類型。對于基于序列的操作，包括在兩端添加和刪除元素（雙端隊列操作），在任意節(jié)點插入、連接、刪除，查找某個滿足要求的元素，將序列拆分為子序列，幾乎所有的函數(shù)型語言都支持。但是對于高效的更多操作，這些語言很難做到。即使有相對應(yīng)的實現(xiàn)，通常也都非常復(fù)雜，實際很難使用。
而指狀樹提供了一種純函數(shù)式的序列數(shù)據(jù)結(jié)構(gòu)，它可以在均攤常量時間（amortized constant time）內(nèi)完成訪問，添加到序列的前端和末尾等操作，以及在對數(shù)時間（logarithmic time）內(nèi)完成串聯(lián)和隨機訪問。除了良好的漸近運行時邊界外，手指樹還非常靈活：當(dāng)與元素上的幺半群標(biāo)記（monoidal tag）結(jié)合時，指狀樹可用于實現(xiàn)高效的隨機訪問序列、有序序列、間隔樹和優(yōu)先級隊列。
三、基本結(jié)構(gòu)
手指樹在樹的“手指”（葉子）的地方存儲數(shù)據(jù)，訪問時間為分?jǐn)偝Ａ俊Ｊ种甘且粋€可以訪問部分?jǐn)?shù)據(jù)結(jié)構(gòu)的點。在命令式語言（imperative language）中，這被稱做指針。在手指樹中，“手指”是指向序列末端或葉節(jié)點的結(jié)構(gòu)。手指樹還在每個內(nèi)部節(jié)點中存儲對其后代應(yīng)用一些關(guān)聯(lián)操作的結(jié)果。存儲在內(nèi)部節(jié)點中的數(shù)據(jù)可用于提供除樹類數(shù)據(jù)結(jié)構(gòu)之外的功能。
1. 手指樹的深度由下到上計算。
2. 手指樹的第一級，即樹的葉節(jié)點，僅包含值，深度為 。第二級為深度 。第三級為深度 ，依此類推。
3. 離根越近，節(jié)點指向的原始樹（在它是手指樹之前的樹）的子樹越深。這樣，沿著樹向下工作就是從葉子到樹的根，這與典型的樹數(shù)據(jù)結(jié)構(gòu)相反。為了獲得這種的結(jié)構(gòu)，我們必須確保原始樹具有統(tǒng)一的深度。在聲明節(jié)點對象時，必須通過子節(jié)點的類型進行參數(shù)化。深度為 及以上的脊椎上的節(jié)點指向樹，通過這種參數(shù)化，它們可以由嵌套節(jié)點表示。
將一棵樹變成手指樹
注釋：2-3樹是一種樹狀數(shù)據(jù)結(jié)構(gòu)，其中每個帶有子節(jié)點（內(nèi)部節(jié)點）的節(jié)點具有兩個子節(jié)點（ 節(jié)點）和一個數(shù)據(jù)元素或三個子節(jié)點（ 節(jié)點）和兩個數(shù)據(jù)元素。2-3樹是3階B樹。樹外部的節(jié)點（葉節(jié)點）沒有子節(jié)點和一兩個數(shù)據(jù)元素。
我們將從平衡 2-3 樹開始這個過程。為了使手指樹正常工作，所有的葉節(jié)點需要是水平的。如下圖所示：
手指是“一種結(jié)構(gòu)，可以有效地訪問靠近特定位置的樹的節(jié)點。”要制作手指樹，我們需要將手指放在樹的左右兩端，取樹的最左邊和最右邊的內(nèi)部節(jié)點并將它們拉起來，使樹的其余部分懸在它們之間，這為我們提供了對序列末尾的均攤常量訪問時間。
這種新的數(shù)據(jù)結(jié)構(gòu)被稱為手指樹。手指樹由沿其樹脊（棕色線）分布的幾層（下方藍色框）組成：
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
示例中的數(shù)字是帶有字母的節(jié)點。每個列表由樹脊上每個節(jié)點的前綴或后綴劃分。在轉(zhuǎn)換后的2-3樹中，頂層的數(shù)字列表似乎可以有兩個或三個長度，而較低級別的長度只有一或兩個。為了使手指樹的某些應(yīng)用程序能夠如此高效地運行，手指樹允許在每個級別上有1到4個子樹。手指樹的數(shù)字可以轉(zhuǎn)換成一個列表，如：
type Digit a = One a | Two a a | Three a a a | Four a a a a
頂層具有類型 a 的元素，下一層具有類型節(jié)點 a 的元素，因為樹脊和葉子之間的節(jié)點，這通常意味著樹的第 n 層具有元素類型為
，或 2-3 個深度為 n 的樹。這意味著 n 個元素的序列由深度為 Θ(log n) 的樹表示。距離最近端 d 的元素存儲在樹中 Θ(log d) 深度處。
雙向隊列操作
指狀樹也可以制作高效的雙向隊列。無論結(jié)構(gòu)是否持久，所有操作都需要 Θ(1) 時間。它可以被看作是的隱式雙端隊列的擴展：
（1）用 2-3 個節(jié)點替換對提供了足夠的靈活性來支持有效的串聯(lián)。（為了保持恒定時間的雙端隊列操作，必須將 Digit 擴展為四。）
（2）用幺半群（monoid）注釋內(nèi)部節(jié)點允許有效的分裂。
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
四、時間復(fù)雜度
手指樹提供了對樹的“手指”（葉子）的分?jǐn)偝Ａ繒r間訪問，這是存儲數(shù)據(jù)的地方，以及在較小部分的大小中連接和拆分對數(shù)時間。它還在每個內(nèi)部節(jié)點中存儲對其后代應(yīng)用一些關(guān)聯(lián)操作的結(jié)果。存儲在內(nèi)部節(jié)點中的“摘要”數(shù)據(jù)可用于提供除樹之外的數(shù)據(jù)結(jié)構(gòu)的功能。
| 操作 | 手指樹 | 注釋 2-3 樹 (annotated 2-3 tree) | 列表（list) | 向量（vector |
| const,snoc | O(1) | O(logn) | O(1)/O(n) | O(n) |
| viewl,viewr | O(1) | O(logn) | O(1)/O(n) | O(1) |
| measure/length | O(1) | O(1) | O(n) | O(1) |
| append | O(log min(l1, l2)) | O(logn) | O(n) | O(m+n) |
| split | O(log min(n, l-n)) | O(logn) | O(n) | O(1) |
| replicate | O(log n) | O(logn) | 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(logn) | O(n) | O(1) |
五、應(yīng)用
指狀樹可用于建造其他樹。例如，優(yōu)先級隊列可以通過樹中子節(jié)點的最小優(yōu)先級標(biāo)記內(nèi)部節(jié)點來實現(xiàn)，或者索引列表/數(shù)組可以通過節(jié)點的子節(jié)點中葉子的計數(shù)來標(biāo)記節(jié)點來實現(xiàn)。其他應(yīng)用包括隨機訪問序列（如下所述）、有序序列和區(qū)間樹。
手指樹可以提供平均O(1)的推、反轉(zhuǎn)、彈出， O(logn)追加和拆分；并且可以適應(yīng)索引或排序序列。和所有函數(shù)式數(shù)據(jù)結(jié)構(gòu)一樣，它本質(zhì)上是持久的；也就是說，始終保留舊版本的樹。
對于代碼實現(xiàn)，Haskell核心庫中的有限序列 Seq 的實現(xiàn)使用了2-3手指樹（Data.Sequence），OCaml 中 BatFingerTree 模塊的實現(xiàn) 也使用了通用手指樹數(shù)據(jù)結(jié)構(gòu)。手指樹可以使用或不使用惰性求值來實現(xiàn)，但惰性允許更簡單的實現(xiàn)。
C語言網(wǎng)提供由在職研發(fā)工程師或ACM藍橋杯競賽優(yōu)秀選手錄制的視頻教程，并配有習(xí)題和答疑，點擊了解：
一點編程也不會寫的：零基礎(chǔ)C語言學(xué)練課程
解決困擾你多年的C語言疑難雜癥特性的C語言進階課程
從零到寫出一個爬蟲的Python編程課程
只會語法寫不出代碼？手把手帶你寫100個編程真題的編程百練課程
信息學(xué)奧賽或C++選手的 必學(xué)C++課程
藍橋杯ACM、信息學(xué)奧賽的必學(xué)課程：算法競賽課入門課程
手把手講解近五年真題的藍橋杯輔導(dǎo)課程