跳轉到內容

F# 程式設計/高階資料結構

Add links
來自華夏公益教科書
< F# 程式設計
最新修訂版本於 2022年4月29日 稽核。目前有 1 個待稽核更改。
上一節：主動模式 索引 下一節：反射
F#：高階資料結構

F# 自帶了一套資料結構，但瞭解如何從頭開始實現資料結構非常重要。

順便說一下，數百位作者已經撰寫了數千本關於這個主題的冗長書籍，因此在本書有限的空間內提供資料結構的全面概述是不現實的。相反，本章旨在介紹使用 F# 開發不可變資料結構的基礎知識。鼓勵讀者使用本頁底部列出的資源來更全面地瞭解演算法和資料結構。

棧

[編輯 | 編輯原始碼]

F# 的內建 列表 資料結構本質上是一個不可變的棧。雖然它當然可以使用，但為了編寫探索性程式碼的目的，我們將從頭開始實現一個棧。我們可以使用一個簡單的聯合來表示棧中的每個節點

type 'a stack =
    | EmptyStack
    | StackNode of 'a * 'a stack

使用以下程式碼很容易建立棧的例項

let stack = StackNode(1, StackNode(2, StackNode(3, StackNode(4, StackNode(5, EmptyStack)))))

每個 StackNode 包含一個值和一個指向列表中下一個棧的指標。結果資料結構可以繪製如下

 ___    ___    ___    ___    ___ 
|_1_|->|_2_|->|_3_|->|_4_|->|_5_|->Empty

我們可以建立如下所示的棧模組模板

module Stack =
    type 'a stack =
        | EmptyStack
        | StackNode of 'a * 'a stack
        
    let hd = function
        | EmptyStack -> failwith "Empty stack"
        | StackNode(hd, tl) -> hd
        
    let tl = function
        | EmptyStack -> failwith "Empty stack"
        | StackNode(hd, tl) -> tl
        
    let cons hd tl = StackNode(hd, tl)
    
    let empty = EmptyStack

假設我們想要為我們的棧新增一些方法，例如，一種更新特定索引處項的方法。由於我們的節點是不可變的，我們無法就地更新列表；我們需要複製所有節點，直到我們要更新的節點。

Setting item at index 2 to the value 9.

         0      1      2      3      4
          ___    ___    ___    ___    ___ 
let x =  |_1_|->|_2_|->|_3_|->|_4_|->|_5_|->Empty
                              ^
                             /
          ___    ___    ___ /
let y =  |_1_|->|_2_|->|_9_|

因此，我們將複製所有節點，直到索引 2，然後重用剩餘的節點。編寫這樣的函式非常容易

let rec update index value s =
    match index, s with
    | index, EmptyStack -> failwith "Index out of range"
    | 0, StackNode(hd, tl) -> StackNode(value, tl)
    | n, StackNode(hd, tl) -> StackNode(hd, update (index - 1) value tl)

將一個棧中的項追加到另一個棧的尾部使用類似的技術。由於我們無法就地修改棧，因此我們透過複製來自“前面”棧的所有節點並指向最後一個複製節點到我們的“後面”棧來追加兩個棧，結果如下

Append x and y

          ___    ___    ___    ___    ___ 
let x =  |_1_|->|_2_|->|_3_|->|_4_|->|_5_|->Empty
                                             ___    ___    ___ 
let y =                                     |_6_|->|_7_|->|_8_|->Empty
                                            ^
                                           /
          ___    ___    ___    ___    ___ /
let z =  |_1_|->|_2_|->|_3_|->|_4_|->|_5_|

我們可以使用以下程式碼輕鬆實現此功能

let rec append x y =
    match x with
    | EmptyStack -> y
    | StackNode(hd, tl) -> StackNode(hd, append tl y)

棧非常易於使用和實現。複製節點以“修改”棧的原理對於所有持久資料結構來說都是一樣的。

完整棧模組 

module Stack =
    type 'a stack =
        | EmptyStack
        | StackNode of 'a * 'a stack
        
    let hd = function
        | EmptyStack -> failwith "Empty stack"
        | StackNode(hd, tl) -> hd
        
    let tl = function
        | EmptyStack -> failwith "Emtpy stack"
        | StackNode(hd, tl) -> tl
        
    let cons hd tl = StackNode(hd, tl)
    
    let empty = EmptyStack
    
    let rec update index value s =
        match index, s with
        | index, EmptyStack -> failwith "Index out of range"
        | 0, StackNode(hd, tl) -> StackNode(value, tl)
        | n, StackNode(hd, tl) -> StackNode(hd, update (index - 1) value tl)
        
    let rec append x y =
        match x with
        | EmptyStack -> y
        | StackNode(hd, tl) -> StackNode(hd, append tl y)

    let rec map f = function
        | EmptyStack -> EmptyStack
        | StackNode(hd, tl) -> StackNode(f hd, map f tl)
        
    let rec rev s =
        let rec loop acc = function
            | EmptyStack -> acc
            | StackNode(hd, tl) -> loop (StackNode(hd, acc)) tl
        loop EmptyStack s

    let rec contains x = function
        | EmptyStack -> false
        | StackNode(hd, tl) -> hd = x || contains x tl
        
    let rec fold f seed = function
        | EmptyStack -> seed
        | StackNode(hd, tl) -> fold f (f seed hd) tl

佇列

[編輯 | 編輯原始碼]

樸素佇列

[編輯 | 編輯原始碼]

佇列不像棧那麼簡單。樸素佇列可以使用棧來實現，前提是

  • 項始終追加到列表的末尾，並從棧的頭部出隊。
  • - 或者 - 項預先追加到棧的前面，並透過反轉棧並獲取其頭部來出隊。
(* AwesomeCollections.fsi *)

type 'a stack =
  | EmptyStack
  | StackNode of 'a * 'a stack
  
module Stack = begin
  val hd : 'a stack -> 'a
  val tl : 'a stack -> 'a stack
  val cons : 'a -> 'a stack -> 'a stack
  val empty : 'a stack
  val rev : 'a stack -> 'a stack
end

[<Class>]
type 'a Queue =
    member hd : 'a
    member tl : 'a Queue
    member enqueue : 'a -> 'a Queue
    static member empty : 'a Queue

(* AwesomeCollections.fs *)

type 'a stack =
    | EmptyStack
    | StackNode of 'a * 'a stack
        
module Stack =        
    let hd = function
        | EmptyStack -> failwith "Empty stack"
        | StackNode(hd, tl) -> hd
        
    let tl = function
        | EmptyStack -> failwith "Emtpy stack"
        | StackNode(hd, tl) -> tl
        
    let cons hd tl = StackNode(hd, tl)
    
    let empty = EmptyStack
        
    let rec rev s =
        let rec loop acc = function
            | EmptyStack -> acc
            | StackNode(hd, tl) -> loop (StackNode(hd, acc)) tl
        loop EmptyStack s
    
type Queue<'a>(item : stack<'a>) =
    member this.hd
        with get() = Stack.hd (Stack.rev item)
        
    member this.tl
        with get() = Queue(item |> Stack.rev |> Stack.tl |> Stack.rev)
        
    member this.enqueue(x) = Queue(StackNode(x, item))
    
    override this.ToString() = sprintf "%A" item
    
    static member empty = Queue<'a>(Stack.empty)

我們使用一個介面檔案來隱藏 Queue 類的建構函式。雖然這在技術上滿足了佇列的功能，但每次出隊都是一個 O(n) 操作，其中 n 是佇列中的專案數量。有許多相同方法的變體，但在實踐中，這些方法通常並不實用。我們當然可以改進不可變佇列的實現。

兩個棧實現的佇列

[編輯 | 編輯原始碼]

上面的實現效率不高，因為它需要多次反轉我們的底層資料表示。為什麼不保留這些反轉的棧以備將來使用？與其使用一個棧，我們可以使用兩個棧：一個前面棧 f 和一個後面棧 r。

棧 f 按正確順序儲存專案，而棧 r 按反向順序儲存專案；這允許 f 中的第一個元素成為佇列的頭部，r 中的第一個元素成為佇列的最後一個專案。因此，數字 1 .. 6 的佇列可以用 f = [1;2;3] 和 r = [6;5;4] 表示。

要入隊新專案，將其預先追加到 r 的前面；要出隊專案，將其從 f 中彈出。入隊和出隊都是 O(1) 操作。當然，在某個時刻，f 會為空，並且沒有更多專案可出隊；在這種情況下，只需將所有專案從 r 移動到 f 並反轉列表。雖然佇列確實具有 O(n) 的最壞情況行為，但它具有可接受的 O(1) 的均攤（平均情況）邊界。

此實現的程式碼很簡單

type Queue<'a>(f : stack<'a>, r : stack<'a>) =
    let check = function
        | EmptyStack, r -> Queue(Stack.rev r, EmptyStack)
        | f, r -> Queue(f, r)

    member this.hd =
        match f with
        | EmptyStack -> failwith "empty"
        | StackNode(hd, tl) -> hd
        
    member this.tl =
        match f, r with
        | EmptyStack, _ -> failwith "empty"
        | StackNode(x, f), r -> check(f, r)
        
    member this.enqueue(x) = check(f, StackNode(x, r))
    
    static member empty = Queue<'a>(Stack.empty, Stack.empty)

這是一個簡單、常用且有用的不可變佇列實現。魔法在於 check 函式，該函式始終維護 f 在有專案可用時始終包含專案。

注意： 佇列的週期性 O(n) 最壞情況行為會使其響應時間不可預測，特別是在高度依賴永續性的應用程式中，因為每次訪問佇列時都有可能遇到病態情況。但是，這種特定佇列實現對於大多數不需要永續性或一致響應時間的應用程式來說是完全足夠的。

如上所示，我們通常希望將底層資料結構包裝在類中，原因有兩個

  1. 簡化資料結構的介面。例如，客戶端既不知道也不關心我們的佇列使用兩個棧；他們只知道佇列中的專案遵循先進先出的原則。
  2. 防止客戶端將底層資料放入資料結構中無效狀態。

除了棧之外，幾乎所有資料結構都足夠複雜，需要包裝類以隱藏複雜細節，不讓客戶端看到。

二叉搜尋樹

[編輯 | 編輯原始碼]

二叉搜尋樹類似於棧，但每個節點指向另外兩個節點，稱為左子節點和右子節點

type 'a tree =
    | EmptyTree
    | TreeNode of 'a * 'a tree * 'a tree

此外，樹中的節點以特定方式排序：樹中的每個專案都大於其左子節點中的所有專案，小於其右子節點中的所有專案。

由於我們的樹是不可變的，因此我們透過返回一個帶有插入節點的新樹來“插入”樹。這個過程比聽起來更有效：我們在向下遍歷樹時複製節點，因此我們只複製插入節點路徑上的節點。編寫二叉搜尋樹相對簡單

(* AwesomeCollections.fsi *)

[<Class>]
type 'a BinaryTree =
    member hd : 'a
    member exists : 'a -> bool
    member insert : 'a -> 'a BinaryTree

(* AwesomeCollections.fs *)

type 'a tree =
    | EmptyTree
    | TreeNode of 'a * 'a tree * 'a tree
    
module Tree =
    let hd = function
        | EmptyTree -> failwith "empty"
        | TreeNode(hd, l, r) -> hd
        
    let rec exists item = function
        | EmptyTree -> false
        | TreeNode(hd, l, r) ->
            if hd = item then true
            elif item < hd then exists item l
            else exists item r
            
    let rec insert item = function
        | EmptyTree -> TreeNode(item, EmptyTree, EmptyTree)
        | TreeNode(hd, l, r) as node ->
            if hd = item then node
            elif item < hd then TreeNode(hd, insert item l, r)
            else TreeNode(hd, l, insert item r)
    
type 'a BinaryTree(inner : 'a tree) =
    member this.hd = Tree.hd inner
        
    member this.exists item = Tree.exists item inner
            
    member this.insert item = BinaryTree(Tree.insert item inner)
    
    member this.empty = BinaryTree<'a>(EmptyTree)

我們使用一個介面和一個包裝類來隱藏樹的實現細節，否則使用者可以構建一個違反二叉樹中使用的特定排序規則的樹。

此實現很簡單，允許我們在 O(log n) 最佳情況時間內新增和查詢樹中的任何專案。但是，它有一個病態情況：如果我們按排序順序或幾乎按排序順序新增專案，那麼樹可能會變得非常不平衡。例如，以下程式碼

[1 .. 7] |> Seq.fold (fun (t : BinaryTree<_>) x -> t.insert(x)) BinaryTree.empty

生成這棵樹

    1
   / \
  E   2
     / \
    E   3
       / \
      E   4
         / \
        E   5
           / \
          E   6
             / \
            E   7
               / \
              E   E

這樣的樹與我們上面提到的低效佇列實現並沒有太大區別！樹在高度最小且儘可能飽滿時效率最高。理想情況下，我們希望將上面的樹表示如下

         
        _ 4 _
       /     \
      2       6
     / \     / \
    1   3   5   7
   / \ / \ / \ / \
   E E E E E E E E

樹的最小高度為 ceiling(log n + 1)，其中 n 是列表中的專案數量。當我們將專案插入樹時，我們希望樹能夠自行平衡以保持最小高度。有許多自我平衡樹實現，其中許多實現很容易作為不可變資料結構來實現。

紅黑樹

[編輯 | 編輯原始碼]

紅黑樹是自我平衡樹，它們為樹中的每個節點附加一個“顏色”屬性。除了定義二叉搜尋樹的規則之外，紅黑樹還必須維護以下規則集

  1. 節點要麼是紅色，要麼是黑色。
  2. 根節點始終是黑色。
  3. 沒有紅色節點有紅色子節點。
  4. 從給定節點到其任何後代葉子的每條簡單路徑都包含相同數量的黑色節點。
紅黑樹的一個例子

我們可以透過以下方式為二叉樹新增顏色欄位

type color = R | B    
type 'a tree =
    | E
    | T of color * 'a * 'a tree * 'a tree

當我們在樹中插入節點時，我們需要重新平衡樹以恢復規則。特別地，我們需要刪除具有紅色子節點的節點。一個紅色節點可能具有紅色子節點的四種情況。它們在下面的圖表中由頂部、右側、底部和左側樹表示。中間樹是平衡版本。

                        B(z)
                        /  \
                      R(x)  d
                      /  \
                     a   R(y)
                         /  \
                        b    c
  
                         ||
                         \/

      B(z)              B(y)                 B(x)
      /  \              /  \                 /  \
    R(y)  d    =>     R(x) R(z)    <=       a   R(y)
    /  \              / \  / \                  /  \
  R(x)  c             a b  c d                 b   R(z)
  /  \                                             /  \
 a    b                                           c    d

                         /\
                         ||

                       B(x)
                       /  \
                      a   R(z)
                          /  \
                        R(y)  d
                        /  \
                       b    c

我們可以修改我們的二叉樹類，如下所示

(* AwesomeCollections.fsi *)

[<Class>]
type 'a BinaryTree =
    member hd : 'a
    member left : 'a BinaryTree
    member right : 'a BinaryTree
    member exists : 'a -> bool
    member insert : 'a -> 'a BinaryTree
    member print : unit -> unit
    static member empty : 'a BinaryTree

(* AwesomeCollections.fs *)

type color = R | B    
type 'a tree =
    | E
    | T of color * 'a tree * 'a * 'a tree
    
module Tree =
    let hd = function
        | E -> failwith "empty"
        | T(c, l, x, r) -> x
        
    let left = function
        | E -> failwith "empty"
        | T(c, l, x, r) -> l
    
    let right = function
        | E -> failwith "empty"
        | T(c, l, x, r) -> r
        
    let rec exists item = function
        | E -> false
        | T(c, l, x, r) ->
            if item = x then true
            elif item < x then exists item l
            else exists item r
            
    let balance = function                              (* Red nodes in relation to black root *)
        | B, T(R, T(R, a, x, b), y, c), z, d            (* Left, left *)
        | B, T(R, a, x, T(R, b, y, c)), z, d            (* Left, right *)
        | B, a, x, T(R, T(R, b, y, c), z, d)            (* Right, left *)
        | B, a, x, T(R, b, y, T(R, c, z, d))            (* Right, right *)
            -> T(R, T(B, a, x, b), y, T(B, c, z, d))
        | c, l, x, r -> T(c, l, x, r)
    
    let insert item tree =
        let rec ins = function
            | E -> T(R, E, item, E)
            | T(c, a, y, b) as node ->
                if item = y then node
                elif item < y then balance(c, ins a, y, b)
                else balance(c, a, y, ins b)

        (* Forcing root node to be black *)                
        match ins tree with
            | E -> failwith "Should never return empty from an insert"
            | T(_, l, x, r) -> T(B, l, x, r)
            
    let rec print (spaces : int) = function
        | E -> ()
        | T(c, l, x, r) ->
            print (spaces + 4) r
            printfn "%s %A%A" (new System.String(' ', spaces)) c x
            print (spaces + 4) l
    
type 'a BinaryTree(inner : 'a tree) =
    member this.hd = Tree.hd inner
    member this.left = BinaryTree(Tree.left inner)
    member this.right = BinaryTree(Tree.right inner)
    member this.exists item = Tree.exists item inner
    member this.insert item = BinaryTree(Tree.insert item inner)
    member this.print() = Tree.print 0 inner
    static member empty = BinaryTree<'a>(E)

使這棵樹起作用的所有“魔力”都在 balance 函式中。我們沒有對樹進行任何非常複雜的轉換，但它最終變得相對平衡（實際上，這棵樹的最大深度為 2 * ceil(log n + 1)）。

AVL 樹

[編輯 | 編輯原始碼]

AVL 樹以其兩位發明者 G.M. Adelson-Velskii 和 E.M. Landis 的名字命名。這些樹是自平衡的，因為任何節點的兩個子樹的高度之差僅為 0 或 1；因此，這些樹被稱為高度平衡。

樹中的空節點的高度為 0；非空節點的高度 >= 1。我們可以在樹定義中儲存每個節點的高度

type 'a tree =
    | Node of int * 'a tree * 'a * 'a tree  (* height, left child, value, right child *)
    | Nil

任何節點的高度等於 max(左高度，右高度) + 1。為了方便起見，我們將使用以下建構函式來建立樹節點並初始化其高度

let height = function
    | Node(h, _, _, _) -> h
    | Nil -> 0
    
let make l x r =
    let h = 1 + max (height l) (height r)
    Node(h, l, x ,r)

在 AVL 樹中插入節點與在不平衡二叉樹中插入節點非常相似，唯一的例外是：在插入節點後，我們使用一系列樹旋轉來重新平衡樹。每個節點都有一個隱含的屬性，即其平衡因子，它指的是左子節點的高度減去右子節點的高度；正平衡因子表示樹向左傾斜，負平衡因子表示樹向右傾斜，否則樹是平衡的。

我們只需要在節點的平衡因子為 +/-2 時重新平衡樹。有四種情況會導致我們的樹變得不平衡

左-左情況：根平衡因子 = +2，左子節點的平衡因子 = +1。透過將根節點向右旋轉來平衡

         5                            3
       /   \    Root                /   \
      3     D   Right rotation     2     5
    /  \            ----->        / \   / \
   2    C                        A   B C   D
  / \
 A   B

左-右情況：根平衡因子 = +2，右子節點的平衡因子 = -1。透過將左子節點向左旋轉，然後將根節點向右旋轉來平衡（此操作稱為雙重右旋轉）

       5                              5                                 4
     /   \      Left child          /   \        Root                 /   \
   3      D     Left rotation      4     D       Right rotation      3     5
  / \                ----->       / \               ----->          / \   / \
 A   4                           3   C                             A   B C   D
    / \                         / \
   B   C                       A   B

右-右情況：根平衡因子 = -2，右子節點的平衡因子 = -1。透過將根節點向左旋轉來平衡

    3                                 5
  /   \         Root                /   \
 A     5        Left rotation      3     7
      / \           ----->        / \   / \
     B   7                       A   B C   D
        / \
       C   D

右-左情況：根平衡因子 = -2，右子節點的平衡因子 = +1。透過將右子節點向右旋轉，然後將根節點向左旋轉來平衡（此操作稱為雙重左旋轉）

     3                               3                                 4
   /   \        Right child        /   \        Root                 /   \
  A      5      Right rotation    A     4       Left rotation       3     5
        / \         ----->             / \         ----->          / \   / \
       4   D                          B   5                       A   B C   D
      / \                                / \
     B   C                              C   D

考慮到這一點，我們可以很容易地組合我們的 AVL 樹的其餘部分

(* AwesomeCollections.fsi *)
[<Class>]
type 'a AvlTree =
    member Height : int
    member Left : 'a AvlTree
    member Right : 'a AvlTree
    member Value : 'a
    member Insert : 'a -> 'a AvlTree
    member Contains : 'a -> bool

module AvlTree =
    [<GeneralizableValue>]
    val empty<'a> : AvlTree<'a>

(* AwesomeCollections.fs *)

type 'a tree =
    | Node of int * 'a tree * 'a * 'a tree
    | Nil
    
(*
    Notation:
        h = height
        x = value
        l = left child
        r = right child
        
        lh = left child's height
        lx = left child's value
        ll = left child's left child
        lr = left child's right child
        
        rh = right child's height
        rx = right child's value
        rl = right child's left child
        rr = right child's right child
*)
    
let height = function
    | Node(h, _, _, _) -> h
    | Nil -> 0
    
let make l x r =
    let h = 1 + max (height l) (height r)
    Node(h, l, x ,r)

let rotRight = function
    | Node(_, Node(_, ll, lx, lr), x, r) ->
        let r' = make lr x r
        make ll lx r'
    | node -> node
    
let rotLeft = function
    | Node(_, l, x, Node(_, rl, rx, rr)) ->
        let l' = make l x rl
        make l' rx rr
    | node -> node
    
let doubleRotLeft = function
    | Node(h, l, x, r) ->
        let r' = rotRight r
        let node' = make l x r'
        rotLeft node'
    | node -> node
    
let doubleRotRight = function
    | Node(h, l, x, r) ->
        let l' = rotLeft l
        let node' = make l' x r
        rotRight node'
    | node -> node
    
let balanceFactor = function
    | Nil -> 0
    | Node(_, l, _, r) -> (height l) - (height r)
    
let balance = function
    (* left unbalanced *)
    | Node(h, l, x, r) as node when balanceFactor node >= 2 ->
        if balanceFactor l >= 1 then rotRight node      (* left left case *)
        else doubleRotRight node                        (* left right case *)
    (* right unbalanced *)
    | Node(h, l, x, r) as node when balanceFactor node <= -2 ->
        if balanceFactor r <= -1 then rotLeft node      (* right right case *)
        else doubleRotLeft node                         (* right left case *)
    | node -> node
    
let rec insert v = function
    | Nil -> Node(1, Nil, v, Nil)
    | Node(_, l, x, r) as node ->
        if v = x then node
        else
            let l', r' = if v < x then insert v l, r else l, insert v r
            let node' = make l' x r'
            balance <| node'
            
let rec contains v = function
    | Nil -> false
    | Node(_, l, x, r) ->
        if v = x then true
        else
            if v < x then contains v l
            else contains v r

type 'a AvlTree(tree : 'a tree) =
    member this.Height = height tree
    
    member this.Left =
        match tree with
        | Node(_, l, _, _) -> new AvlTree<'a>(l)
        | Nil -> failwith "Empty tree"
    
    member this.Right =
        match tree with
        | Node(_, _, _, r) -> new AvlTree<'a>(r)
        | Nil -> failwith "Empty tree"
        
    member this.Value =
        match tree with
        | Node(_, _, x, _) -> x
        | Nil -> failwith "Empty tree"
        
    member this.Insert(x) = new AvlTree<'a>(insert x tree)
    
    member this.Contains(v) = contains v tree
    
module AvlTree =
    [<GeneralizableValue>]
    let empty<'a> : AvlTree<'a> = new AvlTree<'a>(Nil)
注意：[<GeneralizableValue>] 屬性指示 F# 該構造可以透過型別推斷產生泛型程式碼。如果沒有該屬性，F# 將推斷 AvlTree.empty 的型別為未定義型別 AvlTree<'_a>，導致在編譯時出現“值限制”錯誤。
最佳化技巧：這棵樹支援在 log(n) 時間內進行插入和查詢，其中 n 是樹中節點的數量。這已經相當不錯了，但我們可以透過消除不必要的比較來使其更快。請注意，當我們將節點插入到樹的左側時，我們只能向左子節點新增權重；但是，balance 函式在每次插入時都會檢查樹的兩側。透過將 balance 重寫為 balance_left 和 balance_right 函式來分別處理，我們可以分別處理左子節點和右子節點的插入。類似的最佳化也可以在紅黑樹實現中進行。

AVL 樹的高度限制為 1.44 * log(n)，而紅黑樹的高度限制為 2 * log(n)。AVL 樹更小的高度和更嚴格的平衡導致插入/刪除速度更慢，但檢索速度比紅黑樹更快。在實踐中，差異幾乎不會顯著：在 10,000,000 個節點的 AVL 樹上進行查詢最多需要 34 次比較，而在紅黑樹上進行查詢最多需要 47 次比較。

堆

[編輯 | 編輯原始碼]

二叉搜尋樹可以有效地查詢集合中的任意元素，但有時也可以有效地訪問集合中的最小元素。堆是一種特殊的資料結構，它滿足堆屬性：每個節點的值都大於其任何子節點的值。此外，我們可以使用左式屬性來保持樹的近似平衡，這意味著任何左子堆的高度至少與它的右兄弟一樣大。我們可以在每個堆節點中儲存每個樹的高度。

最後，由於堆可以實現為最小堆或最大堆，其中根元素要麼是集合中最大的元素，要麼是最小的元素，因此我們透過將排序函式傳遞到堆的建構函式中來支援兩種型別的堆，如下所示

type 'a heap =
    | EmptyHeap
    | HeapNode of int * 'a * 'a heap * 'a heap
    
type 'a BinaryHeap(comparer : 'a -> 'a -> int, inner : 'a heap) =
    static member make(comparer) = BinaryHeap<_>(comparer, EmptyHeap)
注意：透過將 comparer 函式傳遞到 BinaryHeap 建構函式中獲得的功能近似於 OCaml 函式，但它並不像那麼優雅。

左式屬性的一個有趣的結果是，堆中任何路徑上的元素都按排序順序儲存。這意味著我們可以透過合併它們的右脊柱並根據需要交換子節點來恢復左式屬性來合併任何兩個堆。由於每個右脊柱包含的節點數量至少與左脊柱一樣多，因此每個右脊柱的高度與堆中元素數量的對數成正比，因此合併兩個堆可以在 O(log n) 時間內完成。我們可以如下實現堆的所有屬性

(* AwesomeCollections.fsi *)

[<Class>]
type 'a BinaryHeap =
    member hd : 'a
    member tl : 'a BinaryHeap
    member insert : 'a -> 'a BinaryHeap
    member merge : 'a BinaryHeap -> 'a BinaryHeap
    interface System.Collections.IEnumerable
    interface System.Collections.Generic.IEnumerable<'a>
    static member make : ('b -> 'b -> int) -> 'b BinaryHeap

(* AwesomeCollections.fs *)

type 'a heap =
    | EmptyHeap
    | HeapNode of int * 'a * 'a heap * 'a heap
 
module Heap =
    let height = function
        | EmptyHeap -> 0
        | HeapNode(h, _, _, _) -> h
 
    (* Helper function to restore the leftist property *)        
    let makeT (x, a, b) =
        if height a >= height b then HeapNode(height b + 1, x, a, b)
        else HeapNode(height a + 1, x, b, a)
 
    let rec merge comparer = function
        | x, EmptyHeap -> x
        | EmptyHeap, x -> x
        | (HeapNode(_, x, l1, r1) as h1), (HeapNode(_, y, l2, r2) as h2) ->
            if comparer x y <= 0 then makeT(x, l1, merge comparer (r1, h2))
            else makeT (y, l2, merge comparer (h1, r2))
 
    let hd = function
        | EmptyHeap -> failwith "empty"
        | HeapNode(h, x, l, r) -> x
 
    let tl comparer = function
        | EmptyHeap -> failwith "empty"
        | HeapNode(h, x, l, r) -> merge comparer (l, r)
        
    let rec to_seq comparer = function
        | EmptyHeap -> Seq.empty
        | HeapNode(h, x, l, r) as node -> seq { yield x; yield! to_seq comparer (tl comparer node) }
 
type 'a BinaryHeap(comparer : 'a -> 'a -> int, inner : 'a heap) =
    (* private *)
    member this.inner = inner
 
    (* public *)
    member this.hd = Heap.hd inner
    member this.tl = BinaryHeap(comparer, Heap.tl comparer inner)
    member this.merge (other : BinaryHeap<_>) = BinaryHeap(comparer, Heap.merge comparer (inner, other.inner))
    member this.insert x = BinaryHeap(comparer, Heap.merge comparer (inner,(HeapNode(1, x, EmptyHeap, EmptyHeap))))
    
    interface System.Collections.Generic.IEnumerable<'a> with
        member this.GetEnumerator() = (Heap.to_seq comparer inner).GetEnumerator()
            
    interface System.Collections.IEnumerable with
        member this.GetEnumerator() = (Heap.to_seq comparer inner :> System.Collections.IEnumerable).GetEnumerator()
 
    static member make(comparer) = BinaryHeap<_>(comparer, EmptyHeap)

此堆實現了 IEnumerable<'a> 介面，允許我們像 seq 一樣迭代它。除了上面顯示的左式堆之外，還可以非常輕鬆地在 F# 中實現不可變的 splay 堆、二項式堆、斐波那契堆、配對堆和許多其他樹狀資料結構的版本。

惰性資料結構

[編輯 | 編輯原始碼]

值得注意的是，上面的一些純函式資料結構不如它們的命令式實現效率高。例如，將兩個不可變堆疊 x 和 y 連線在一起需要 O(n) 時間，其中 n 是堆疊 x 中元素的數量。但是，我們可以利用 惰性 以使純函式資料結構與它們的命令式對應物一樣高效。

例如，可以很容易地建立一個類似堆疊的資料結構，它將所有計算延遲到真正需要的時候

type 'a lazyStack =
    | Node of Lazy<'a * 'a lazyStack>
    | EmptyStack
 
module LazyStack =
    let (|Cons|Nil|) = function
        | Node(item) ->
            let hd, tl = item.Force()
            Cons(hd, tl)
        | EmptyStack -> Nil
 
    let hd = function
        | Cons(hd, tl) -> hd
        | Nil -> failwith "empty"
 
    let tl = function
        | Cons(hd, tl) -> tl
        | Nil -> failwith "empty"
 
    let cons(hd, tl) = Node(lazy(hd, tl))
    
    let empty = EmptyStack
 
    let rec append x y =
        match x with
        | Cons(hd, tl) -> Node(lazy(printfn "appending... got %A" hd; hd, append tl y))
        | Nil -> y
 
    let rec iter f = function
        | Cons(hd, tl) -> f(hd); iter f tl
        | Nil -> ()

在上面的示例中，append 操作返回一個節點，並將其餘的計算延遲，因此連線兩個列表將發生在常數時間內。上面添加了一個 printfn 語句來演示我們實際上直到第一次訪問連線的值時才計算它們

> open LazyStack;;
> let x = cons(1, cons(2, cons(3, cons(4, EmptyStack))));;

val x : int lazyStack = Node <unevaluated>

> let y = cons(5, cons(6, cons(7, EmptyStack)));;

val y : int lazyStack = Node <unevaluated>

> let z = append x y;;

val z : int lazyStack = Node <unevaluated>

> hd z;;
appending... got 1
val it : int = 1

> hd (tl (tl z) );;
appending... got 2
appending... got 3
val it : int = 3

> iter (fun x -> printfn "%i" x) z;;
1
2
3
appending... got 4
4
5
6
7
val it : unit = ()

有趣的是，append 方法顯然在 O(1) 時間內執行，因為實際的連線操作被延遲到使用者獲取列表頭部時。同時，獲取列表頭部可能會產生副作用，即最多觸發一次對連線方法的呼叫，而不會導致對資料結構其餘部分進行整體重建，因此獲取頭部本身也是一個 O(1) 操作。此堆疊實現支援常數時間內進行追加和連線，以及線性時間內進行查詢。

類似地，惰性佇列的實現也存在，它們支援所有操作的 O(1) 最壞情況行為。

其他資源

[編輯 | 編輯原始碼]
上一節：主動模式 索引 下一節：反射
取自"https://wikibook.tw/w/index.php?title=F_Sharp_Programming/Advanced_Data_Structures&oldid=4207759"
華夏公益教科書