認識演算法：常用資料結構

在 認識演算法：啟程 這篇文章中，我們提到可以幫助更好的設計演算法的其中一個策略是使用資料結構。

我們也有提到資料結構是一種儲存和組織資料的方式，目的是為了讓資料的存取和修改更加方便。並且，資料結構有很多類型，為特定問題選擇合適的資料結構是演算法設計中的重要一環。

這篇文章我們要來更進一步的介紹常用資料結構。

以下是本篇文章的目錄：

1. 陣列 (Array)
2. 矩陣 (Matrix)
3. 鏈結串列 (Linked List)
4. 堆疊 (Stack)
5. 佇列 (Queue)
6. 有根樹 (Rooted Tree)
   • 二元樹 (Binary Tree)
   • 二元搜尋樹 (Binary Search Tree, BST)
   • 堆積 (Heap)
   • 紅黑樹 (Red-Black Tree)
7. 雜湊表 (Hash Table)

陣列(Array)

陣列是一種將資料元素(element)儲存在記憶體中一塊連續、不間斷空間的資料結構。

陣列的核心特性可以從它在記憶體中的儲存方式來理解，這直接決定了它的存取效率和限制。

• 連續的記憶體儲存(Contiguous Memory Storage)
  這是陣列最根本的特性。當我們宣告一個陣列時，計算機會在記憶體中找到一塊足夠大的、連續的空間，然後將陣列的所有元素一個接著一個放進去。例如，一個包含 6 個整數的陣列，在記憶體中就是 6 個整數佔用的空間緊密相連。

• 常數時間存取(Constant-Time Access)
  由於元素是連續儲存的，我們可以透過數學計算快速定位到任何一個元素的位置，這個過程所需的時間是固定的，不會因為陣列大小或元素位置而改變，時間複雜度為 $O(1)$。

  詳細的計算過程如下：

  • 假設陣列的起始記憶體位址是 $a$。

  • 每個元素佔用 $b$ 個位元組(bytes)。

  • 陣列的起始索引是 $s$ (例如，在某些語言中是 0，有些是 1)。

  • 那麼，要存取索引為 $i$ 的元素，它的記憶體位址可以透過公式 $a + b \times (i - s)$ 計算出來。

  因為這個計算非常簡單直接，電腦可以立即跳到指定的記憶體位置去讀取或寫入資料，這也是陣列最主要的優勢之一。

• 元素大小均一(Uniform Element Size)
  上述的快速存取公式能夠成立，前提是陣列中的每一個元素都佔用相同大小的記憶體空間——也就是公式中的 $b$ 是一個常數。大部分程式語言都強制要求陣列中的所有元素必須是相同型別的，例如一個整數陣列或一個字元陣列。

• 對不同大小元素的處理方式
  如果現實中需要儲存大小不同的物件（例如，不同長度的字串），直接用陣列儲存會有困難。此時的解決方案是，陣列本身不直接儲存物件，而是儲存指向這些物件的「指標」(pointer)。因為指標本身的大小是固定的，所以陣列仍然可以維持「元素大小均一」的特性，讓我們能夠快速定位到某個指標，然後再透過該指標去存取實際的物件。

陣列這個資料結構的存在，主要是為了利用電腦記憶體連續儲存的特性，來實現對資料集合最高效率的隨機存取。它的核心優勢如下：

• 極致的存取效率：如上所述，無論陣列有多大，存取任何一個元素的時間都是固定的常數時間 $O(1)$。這與我們之後會介紹到的鏈結串列(Linked List)形成鮮明對比，在鏈結串列中要找到第 $k$ 個元素，必須從頭開始一個個走訪，需要 $\Theta(k)$ 的時間。

• 高記憶體使用效率：當使用單一陣列來表示二維矩陣等結構時，所有資料都緊密地儲存在一起，沒有額外的指標來佔用空間，這在現代電腦上通常更有效率。

但陣列還是有一些劣勢與限制，包含：

• 插入與刪除效率低：陣列的優勢同時也帶來了劣勢。由於它的記憶體位置是連續固定的，若要在陣列的開頭或中間插入一個新元素，所有後續的元素都必須向後移動一個位置來騰出空間。同理，刪除一個元素後，也需要將後續元素往前移動來填補空缺。在最壞的情況下，這些操作需要移動 $n-1$ 個元素，時間複雜度為 $\Theta(n)$。

• 大小固定：傳統陣列在宣告時通常需要指定大小，且之後難以改變。如果空間用完，就會發生「溢位」(overflow) 錯誤。雖然現代程式語言提供了一些動態陣列的實現，但其背後通常也涉及到重新配置一個更大的陣列並複製所有元素的過程，成本較高。

• 靈活性較差：對於非線性或結構不規則的資料，例如每行長度不同的「不規則陣列」(ragged arrays)，使用單一的連續陣列來表示就顯得非常困難且不靈活。

矩陣(Matrix)

矩陣(Matrix)是一種二維陣列，通常會透過一種或多種一維陣列來實現它在記憶體中的儲存。

矩陣的特性主要體現在它多樣的記憶體儲存方式上。我們有幾種將二維邏輯結構映射到一維線性記憶體中的策略，這些策略直接影響了資料的存取效率和使用彈性。

• 單一陣列表示法(Single-Array Representation)

  這種方法將整個 $m \times n$ 的矩陣存放在一個連續的一維陣列中。主要有兩種順序：

  • 列為主序(Row-Major Order)：這是最常見的儲存方式。它將矩陣的每一列逐一串接起來存放。例如，對於矩陣 $M = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}$，它在記憶體中會被儲存為 1 2 3 4 5 6 的序列。

  • 行為主序(Column-Major Order)：這種方式則是將矩陣的每一行逐一串接。對於同一個矩陣 $M$，它會被儲存為 1 4 2 5 3 6 的序列。

  在這兩種方式下，要存取特定元素 $M[i, j]$，電腦需要透過公式計算它在一維陣列中的索引位置，這個過程非常快速，時間複雜度為 $O(1)$。

• 多重陣列表示法(Multiple-Array Representation)

  這種方法不使用單一的連續記憶體區塊，而是使用一個主陣列來存放指向其他子陣列的指標(pointer)。

  • 以列為主的版本：主陣列有 $m$ 個元素，每個元素都是一個指標，分別指向 $m$ 個獨立的、儲存著每一列資料的子陣列。

  • 以行為主的版本：相對地，主陣列有 $n$ 個元素，每個指標分別指向 $n$ 個儲存著每一行資料的子陣列。

• 區塊表示法(Block Representation)

  這是一種較不常見但依然存在的儲存策略。它將整個矩陣分割成數個小的子矩陣(區塊)，然後將這些區塊連續地儲存在記憶體中。例如，一個 $4 \times 4$ 的矩陣可以被視為四個 $2 \times 2$ 的區塊，儲存順序可能是先存完左上角的區塊，再存右上角的，依此類推。

矩陣可以有效的組織和表示具有二維——或更高維——關係的數據集。凡是資料本身帶有「列」和「行」的邏輯概念，例如表格、棋盤、圖像像素等，使用矩陣來表示都是非常自然且直觀的。

鏈結串列(Linked List)

鏈結串列(Linked List)是一種資料結構，其中的物件透過各自內部的指標(pointer)來決定它的線性排列順序，而不是像陣列那樣由記憶體中的連續位置決定。

鏈結串列是一種極具彈性的動態集合表示方式，它的核心特性圍繞著「節點」與「指標」兩個概念。以下是關於鏈結串列特性的詳細介紹：

1. 節點(Node)結構

   • 鏈結串列中的每一個元素都是一個獨立的物件，通常稱為「節點」。

   • 每個節點至少包含兩個屬性：一個是用於儲存資料的 key，以及一個或多個用於指向其他節點的指標(pointer)。節點也可以包含其他的附屬資料。

2. 指標決定順序

   • 與陣列不同，鏈結串列的線性順序是由節點內的指標決定的。在一個雙向鏈結串列(doubly linked list) 中，每個節點 x 會有：

     • x.next：指向其後繼節點。

     • x.prev：指向其前驅節點。

   • 串列的第一個元素稱為「頭」(head)，其 prev 指標為 NIL(空)。最後一個元素稱為「尾」(tail)，其 next 指標為 NIL。整個串列的開頭由一個指向 head 的屬性 L.head 來標識。

3. 多樣的形式

   • 鏈結串列可以根據結構和用途的不同，分為多種類型：

     • 單向(Singly Linked) vs. 雙向(Doubly Linked)：單向串列的節點只有 next 指標，而雙向串列則同時有 next 和 prev 指標。

     • 排序(Sorted) vs. 未排序(Unsorted)：排序串列中的元素會根據其 key 值的大小進行排列，最小值在頭部，最大值在尾部。未排序串列則沒有此限制。

     • 環狀(Circular) vs. 非環狀：環狀串列的尾部 next 指標會指向頭部，而頭部的 prev 指標會指向尾部，形成一個環。

4. 哨兵(Sentinel)的應用

   • 為了簡化處理邊界條件——例如：在串列的頭部或尾部進行插入/刪除），可以引入一個稱為「哨兵」的虛設物件 L.nil。

   • 這個哨兵位於頭部和尾部之間，使串列變成一個環狀結構。例如：哨兵的 next 指向真正的頭部，prev 指向真正的尾部。這樣一來，所有的插入和刪除操作都可以視為在兩個節點之間進行，無需再針對頭/尾的特殊情況撰寫額外程式碼，從而簡化了實作。

鏈結串列的主要目的是提供一個對於「動態集合」更具彈性的表示方式。在許多應用場景中，我們需要一個可以高效新增、刪除元素的資料集合，而傳統陣列在這些操作上有效能瓶頸。鏈結串列的線性順序是由指標決定的，而非固定的記憶體索引，這正是它靈活性的根源。而根據以上的說明，我們可以整理出兩大鏈結串列的優勢：

• 高效的插入與刪除：這是鏈結串列最顯著的優勢。要在串列中插入或刪除一個元素，只需要修改周圍節點的指標即可，這個操作的時間複雜度是 $O(1)$。相較之下，在陣列的開頭插入或刪除元素，需要移動所有後續元素，最壞情況下的時間複雜度為 $\Theta(n)$。

• 彈性的空間使用：鏈結串列的節點在記憶體中無需連續存放，可以在需要時才動態配置空間，因此不會像陣列一樣預先佔用一塊固定大小的記憶體，空間使用上更有效率。

然而，鏈結串列也有它的劣勢存在：

• 低效的元素存取與搜尋：鏈結串列無法像陣列一樣在 $O(1)$ 時間內直接存取第 $k$ 個元素。要找到第 $k$ 個元素，必須從頭部開始，沿著指標逐一走訪 $k$ 次，時間複雜度為 $\Theta(k)$。

• 搜尋效能差：同樣地，要在一個包含 $n$ 個元素的鏈結串列中搜尋一個特定 key 值的元素，最壞的情況下需要遍歷整個串列，這是一個線性搜尋，時間複雜度為 $\Theta(n)$。

• 額外的指標空間：每個節點都需要額外的空間來儲存一或多個指標，當儲存的資料本身很小時，這些指標所佔的空間開銷會相對顯著。

鏈結串列的常見應用包括：

• 實作其他資料結構：由於其高效的插入和刪除特性，鏈結串列是實作堆疊(Stack)和佇列(Queue)的理想選擇，PUSH/POP 和 ENQUEUE/DEQUEUE 操作都可以達到 $O(1)$ 的時間複雜度。

• 雜湊表(Hash Table)的碰撞處理：在雜湊表中，當多個不同的鍵值被雜湊到同一個索引位置時，就會發生「碰撞」。解決這個問題的一個常用方法是「鏈結法」(Chaining)，即將所有碰撞的元素用一個鏈結串列串起來存放在該索引位置。

• 表示動態集合：在需要頻繁變動成員的集合應用中，例如編譯器的符號表(雖然雜湊表更常用），鏈結串列提供了一個簡單且靈活的基礎結構。

堆疊(Stack)

堆疊(Stack)是一種動態集合(dynamic set)，它刪除的元素永遠是最近被插入的那一個，因此實踐了「後進先出」(Last-In, First-Out, LIFO) 的原則。以下是堆疊特性的詳細介紹：

• 核心原則：後進先出(LIFO)

  這是堆疊最根本的特性。我們可以想像成自助餐廳裡的盤子堆：最新放上去的盤子會疊在最上面，而當我們要取一個盤子時，也只能從最上面拿。因此，盤子被取出的順序，正好與它們被放進去的順序相反。只有最頂端的元素是可以直接存取的。

• 主要操作：PUSH 和 POP

  • PUSH(推入)：相當於 INSERT (插入) 操作，將一個新元素放置在堆疊的最頂端。

  • POP(彈出)：相當於 DELETE (刪除) 操作，它不需要指定參數，因為它永遠是移除並返回堆疊最頂端的元素。

  這兩個修改堆疊內容的操作，它的執行時間都只需要 $O(1)$，代表它們非常有效率。

• 基於陣列的實現(Array-based Implementation)

  堆疊可以透過陣列來實現，我們將此陣列表示為 S[1:n] 來做以下說明。這個實現有幾個關鍵屬性：

  • S.top: 這是一個索引值，永遠指向堆疊中「最頂端」——也就是最近插入——的元素。

  • S.size: 這代表用來儲存堆疊的陣列大小，也就是堆疊的容量上限。

  • 堆疊中的實際元素儲存在 S[1...S.top] 的範圍內。S[1] 是堆疊底部的元素，而 S[S.top] 則是頂部的元素。當 S.top 為 0 時，代表堆疊是空的。

• 邊界條件：溢位(Overflow) 與下溢(Underflow)

  • 溢位(Overflow)：如果我們試圖對一個已經滿的堆疊——也就是 S.top 已經等於陣列大小 S.size——執行 PUSH 操作，就會發生錯誤，因為沒有空間可以存放新元素了。

  • 下溢(Underflow)：如果我們試圖對一個空的堆疊執行 POP 操作時，也會發生錯誤，因為裡面已經沒有元素可以移除了。

堆疊這個資料結構的存在，是為了解決一類具有「後進先出」特性的問題。它的設計簡單而專一，從而帶來了顯著的優勢，但也伴隨著一些限制。以下整理出堆疊的優勢與劣勢：

• 優勢

  1. 極高的效率：堆疊最核心的優勢在於它的操作效率。PUSH 和 POP 操作都只涉及對 top 索引的增減和陣列的單一位置存取，因此時間複雜度都是 $O(1)$。這意味著無論堆疊有多大，新增和移除頂端元素的速度都一樣快，這在需要頻繁進行這類操作的場景中至關重要。

  2. 結構簡單：基於陣列的堆疊實現起來非常直觀，只需要一個陣列和一個指向頂端的變數即可。這種簡單性使得程式碼更容易編寫、理解和除錯。

• 劣勢

  1. 容量固定(在基於陣列的實現中)：當使用陣列來實現堆疊時，它的大小在初始化時就固定了。如果儲存的元素數量超過了陣列大小，就會導致「溢位」(overflow)錯誤。雖然可以使用動態陣列或連結串列(Linked List)等方式來克服，但最基礎的實現有此限制。

  2. 存取受限：堆疊的設計使它只能存取頂端的元素。我們無法直接讀取或修改堆疊中間的元素，除非將它上面的所有元素都先 POP 出來。這種 LIFO 的存取方式雖然是它的特性，但在需要隨機存取元素的場景下就成了一大劣勢。

管理副程式呼叫(Subroutine Linkage) 是堆疊最經典的應用之一。當我們的程式碼呼叫一個函式時，系統會將返回位址、參數和區域變數等資訊 PUSH 到一個稱為「呼叫堆疊」(Call Stack) 的記憶體區域。如果這個函式又呼叫了另一個函式，新的資訊會再次被 PUSH 到堆疊頂部。當函式執行完畢返回時，對應的資訊會從堆疊中 POP 出來，程式流程就能回到之前的位置。這種後進先出的機制完美地處理了函式的巢狀呼叫。

佇列(Queue)

佇列(Queue)是一種動態集合(dynamic set)，它是一種遵循「先進先出」（First-In, First-Out, FIFO）原則的資料結構，就像現實生活中的排隊隊伍一樣，最先進入佇列的元素，將會是第一個被移除的元素。以下是佇列特性的詳細介紹：

• 先進先出(FIFO)原則

  這是佇列最根本的特性。與堆疊(Stack) 的「後進先出」(LIFO)相反，佇列嚴格遵守「先進先出」(FIFO)的策略。我們可以想像佇列就像一群排隊等待服務的顧客。新來的顧客總是排在隊伍的末尾，而最先獲得服務的，永遠是排在隊伍最前端、等待時間最長的顧客。

• 擁有「頭」與「尾」

  佇列有兩個重要的位置：頭(head) 和尾(tail)。

  • 頭(head)：指向隊伍的最前端，也就是下一個將被移除的元素。

  • 尾(tail)：指向隊伍的末端，代表新加入的元素將被放置的位置。

• 主要操作

  • ENQUEUE(入隊)：這是佇列的 INSERT (插入) 操作。當一個新元素被「enqueued」，它會被放置在佇列的尾端。

  • DEQUEUE(出隊)：這是佇列的 DELETE (刪除) 操作。這個操作會移除佇列頭端的元素，也就是在佇列中停留最久的元素。值得注意的是，DEQUEUE 操作不需要指定要移除哪個元素，因為目標永遠是固定的。

• 基於陣列的實現(Array-based Implementation)

  佇列可以透過陣列來實現，我們將此陣列表示為 Q[1:n] 來做以下說明。這種實現非常巧妙。

  • 它使用一個大小為 n 的陣列 Q[1:n]，並透過 Q.head 和 Q.tail 兩個屬性(attributes)來分別索引頭部和尾部。

  • 為了避免在移除頭部元素後需要移動陣列中所有其他元素，這種實現採用了「環繞(wrap around)」的方式。當索引到達陣列末端 n 時，下一個位置會回到開頭的 1，形成一個環狀結構。

  • 在這種實現下，ENQUEUE 和 DEQUEUE 操作都只需要移動索引指標，因此時間複雜度可以達到 O(1)，非常高效。

佇列的存在是為了解決那些需要按順序處理任務或資料的場景。它的核心價值在於它內建的「公平性」和「順序性」。當多個項目需要共享有限的資源時（例如：一台印表機、一個 CPU 核心），佇列提供了一種簡單且可預測的管理機制，確保先到的請求會被先處理。它將現實世界中「排隊」這個公平的行為，抽象化為一種電腦科學中的資料結構。以下整理出佇列的優勢與劣勢：

優勢

• 高效的操作：對於主要的 ENQUEUE 和 DEQUEUE 操作，無論是使用前面提到的環形陣列實現，還是使用鏈結串列(linked list)實現，它的時間複雜度都是 O(1)。這意味著無論佇列中有多少元素，新增和移除基本元素的時間都是固定的，效率極高。

• 直觀且易於理解：FIFO 的概念與我們的日常生活經驗完全一致，因此非常容易理解和應用。

• 保證順序：佇列的 FIFO 特性確保了資料或任務的處理順序與它們的到達順序一致，這在許多演算法和系統設計中是至關重要的。

劣勢

• 存取不靈活：佇列的主要限制是，我們只能從頭部移除元素，並從尾部添加元素。無法直接存取或移除佇列中間的元素。用另外一種說法，被刪除的元素是「預先指定的」(prespecified)，這正是佇列局限性的體現。若要搜尋特定元素，最壞的情況下需要將該元素前的所有元素都 DEQUEUE，效率很低。

• 可能有容量限制(基於陣列實現)：如果使用固定大小的陣列來實現佇列，當佇列滿了之後，再嘗試 ENQUEUE 就會導致「溢位 (overflow)」錯誤。雖然這個問題可以透過動態陣列或鏈結串列來解決，但在基礎的陣列實現中這是一個需要考量的問題。

佇列的 FIFO 特性使它在電腦科學領域有著廣泛的應用，以下是一些常見的例子：

• 任務排程：作業系統常用佇列來管理待處理的行程(processes)。CPU 會按照一定的排程演算法——例如：先到先服務——從佇列中取出行程來執行。

• 緩衝區(Buffers)：在不同速度的兩個處理程序間傳輸資料時，佇列常被用作緩衝區。例如：當你在網路上觀看串流影片時，播放器會將預先下載的資料放入一個佇列，然後依序取出播放，以應對網路速度的波動。

• 印表機佇列：當多個使用者向同一台印表機發送列印請求時，這些請求會被放入一個佇列中，印表機再按照順序逐一處理。

• 廣度優先搜尋(Breadth-First Search, BFS)：在圖論(Graph Theory) 或樹(Tree) 的遍歷中，BFS 演算法會使用佇列來存放待訪問的節點，確保節點是按照與起點的距離逐層被訪問的。

• 訊息佇列(Message Queues)：在分散式系統中，不同服務之間會透過訊息佇列來非同步地傳遞訊息，確保訊息能夠被可靠地、按順序地處理。

有根樹(Rooted Tree)

有根樹是一種透過節點物件與指標(pointers)來表示非線性階層關係的連結式資料結構。它的核心特性在於其節點的組織方式以及節點間的連結關係。以下我們先來介紹有根樹的基本特性：

• 節點是基本單位

  樹中的每一個節點都被視為一個物件。如同連結串列(linked lists)，每個節點物件都包含一個 key 屬性用來儲存其值，而其他的屬性則是指向其他節點的指標，這些指標的設計會根據樹的類型而有所不同。

• 指標定義了階層關係

  與只能表示線性關係的連結串列不同，樹狀結構透過指標來建立父子、兄弟等階層關係。

  這邊有一個特別值得提的實作方法叫做左子右兄弟表示法(Left-child, Right-sibling Representation)，這種表示法非常巧妙，專門用來解決節點子節點數量不固定的「無界分支」(unbounded branching)問題。在這種結構中，每個節點 x 依然有指向父節點的 x.p 指標，但對於子節點，它只用了兩個指標：

  1. x.left-child：指向 x 的最左邊的那個子節點。

  2. x.right-sibling：指向 x 的右邊相鄰的那個兄弟節點。

  如果節點 x 沒有任何子節點，它的 x.left-child 為 NIL。如果 x 是它的父節點最右邊的子節點，那麼 x.right-sibling 為 NIL。這種表示法僅使用 O(n) 的空間，非常節省記憶體。

現實世界中大量的關係本質上是非線性的。傳統的連結串列(Linked lists)非常適合表示序列、隊伍這類線性關係的資料。然而，當我們需要模擬或處理具有階層、分支或從屬關係的資料時，例如公司組織圖、資料夾結構、家族譜系等，線性結構就顯得力不從心。有根樹提供了一種直觀且高效的方式來模型化這些複雜的非線性階層關係。

以下我們更進一步的來介紹常見的有根樹類型：

二元樹(Binary Tree)

二元樹是一種每個節點最多擁有兩個子節點（一個左子節點和一個右子節點）的樹狀資料結構。這是最基礎的樹狀表示法之一。以下介紹二元樹的特性：

• 核心屬性(指標)：在一個典型的二元樹中，每個節點 x 包含三個關鍵的指標屬性。

  • x.p：指向其父節點(parent) 的指標。

  • x.left：指向其左子節點(left child) 的指標。

  • x.right：指向其右子節點(right child) 的指標。

• 特殊節點的判定：

  • 根節點(Root)：如果一個節點 x 的父指標 x.p 為 NIL (空值)，那麼 x 就是整棵樹的根節點。整棵樹的根節點由一個名為 T.root 的屬性來指向。

  • 空樹(Empty Tree)：如果 T.root 的值為 NIL，則表示這棵樹是空的。

  • 葉節點(Leaf Node) / 缺少子節點：如果節點 x 沒有左子節點，則 x.left 為 NIL；同樣地，若沒有右子節點，則 x.right 為 NIL。

堆積(Heap)

堆積(Heap)是一種陣列物件，我們可以將它視為一個近似完整的二元樹(nearly complete binary tree)。

堆積是一個非常高效的資料結構，其核心特性圍繞著它的特殊結構與元素排序規則。以下來詳細介紹堆積的特性：

• 結構：近似完整的二元樹

  堆積在概念上是一棵二元樹，這棵樹的所有層級都完全填滿，除了可能的最底層，最底層的節點會由左至右填入。雖然我們將它看作一棵樹，但它實際上是儲存在一個陣列中的。陣列的第一個元素 $A$ 就是樹的根節點。

• 父子節點的索引關係

  由於堆積是使用陣列來實作的，因此任何一個節點的父節點、左子節點和右子節點的索引都可以透過簡單的數學運算快速計算出來：

  • PARENT(i): $\lfloor i/2 \rfloor$

  • LEFT(i): $2i$

  • RIGHT(i): $2i+1$

  在大多數電腦上，這些運算可以透過高效的位元移位操作來完成，例如計算 $2i$ 相當於將 $i$ 的二進位表示左移一位，這使得操作非常快速。

• 堆積屬性(Heap Property)

  堆積分為兩種主要類型，它們都滿足特定的「堆積屬性」，這個屬性決定了節點與它的父節點之間的關係：

  • 最大堆積(Max-Heap)：除了根節點外，對於每一個節點 $i$，它的父節點的值都大於或等於該節點的值——也就是 $A[\text{PARENT}(i)] \geq A[i]$。這意味著最大堆積中的最大元素永遠儲存在根節點。

  • 最小堆積(Min-Heap)：與最大堆積相反，除了根節點外，對於每一個節點 $i$，它的父節點的值都小於或等於該節點的值——也就是 $A[\text{PARENT}(i)] \leq A[i]$。因此，最小堆積中的最小元素永遠儲存在根節點。

• 高度與操作時間
  一個包含 $n$ 個元素的堆積，它的高度為 $\Theta(\lg n)$。堆積上的基本操作（如維護堆積特性、插入、提取等）的執行時間最多與樹的高度成正比，因此時間複雜度為 $O(\lg n)$。

• 與垃圾回收的「堆」的區別
  需要特別注意的是，資料結構中的「堆(Heap)」與程式語言（如 Java、Python）中用於「垃圾回收儲存(garbage-collected storage)」的「堆」是完全不同的概念。本文中提到的「堆」始終指稱前者這種特定的資料結構。

堆積這個資料結構的出現，主要是為了解決特定演算法的效率問題，並提供一種高效管理資訊的設計技巧。常見應用包含堆積排序(Heapsort)和優先佇列(Priority Queue)。

二元搜尋樹(Binary Search Trees)

二元搜尋樹是一種根植於二元樹的資料結構，它的組織方式滿足一個關鍵特性：對於樹中的任何節點 x，其左子樹中所有節點的值都小於或等於 x 的值，而其右子樹中所有節點的值都大於或等於 x 的值。

二元搜尋樹的核心特性都圍繞著它獨特的「二元搜尋樹屬性」(binary-search-tree property) 展開，這也決定了它的結構與行為。以下詳細介紹二元搜尋樹的特性：

• 二元搜尋樹屬性(The Binary-Search-Tree Property)

  這是此資料結構最根本的規則。明確來說，假設 x 是樹中的任意一個節點：

  • 如果 y 是 x 左子樹中的一個節點，那麼 y.key ≤ x.key。

  • 如果 y 是 x 右子樹中的一個節點，那麼 y.key ≥ x.key。

  這個屬性不僅適用於根節點，也同樣適用於樹中的每一個節點。

• 結構化表示(Structural Representation)
  二元搜尋樹的物理結構是一個鏈結資料結構(linked data structure)。每個節點物件除了包含一個鍵(key)和附屬資料(satellite data)外，還包含三個指標屬性：left、right 和 p，分別指向其左子節點、右子節點和父節點。如果某個子節點或父節點不存在，則對應的指標值為 NIL。樹的根節點是唯一一個父節點為 NIL 的節點。

• 可按序遍歷(Sorted Order Traversal)
  由於二元搜尋樹的屬性，我們可以使用一種稱為「中序遍歷」(inorder tree walk)的簡單遞迴演算法，來按照排序順序列印出樹中所有的鍵。這個演算法的原理是先遞迴遍歷左子樹，然後印出根節點的鍵，最後再遞迴遍歷右子樹。對任何二元搜尋樹執行中序遍歷，都能以 Θ(n) 的時間複雜度得到一個排序好的鍵值序列。

紅黑樹(red-black trees)

紅黑樹是一種自平衡的二元搜尋樹，它透過為每個節點賦予「紅色」或「黑色」的顏色屬性，並遵循一套特定的規則，來確保樹中從根到葉子的最長路徑不會超過最短路徑的兩倍長，從而將樹的高度維持在對數級別 $O(\lg n)$，進而保證了搜尋、插入和刪除等操作都能在最壞情況下維持高效能。

紅黑樹的核心在於它不僅僅是一棵二元搜尋樹，還必須始終滿足以下五個「紅黑特性」。正是這些特性的共同作用，才使得紅黑樹能夠自我維持平衡。

首先，我們需要理解紅黑樹的結構。除了像普通二元搜尋樹一樣擁有 key（鍵值）、left（左子節點）、right（右子節點）和 p（父節點）之外，每個節點還額外儲存一個 color 屬性，其值為「紅色」或「黑色」。

以下是紅黑樹必須遵守的五個特性：

1. 每個節點不是紅色就是黑色。

   這是最基本的顏色規定，確保了每個節點都有一個明確的顏色狀態。

2. 根節點(Root)必須是黑色。

   此規則確保了從根節點開始的路徑總是從一個黑色節點出發。

3. 每個葉子節點(NIL)都是黑色。

   這裡的「葉子節點」是一個非常關鍵的概念。在紅黑樹的理論模型中，它指的不是沒有子節點的鍵值節點，而是指向的空（NIL）位置。為了方便程式碼實作，通常會用一個稱為「哨兵」(sentinel)的單一黑色節點 T.nil 來代表所有這些NIL葉子，以及根節點的父節點。

4. 如果一個節點是紅色的，那麼它的兩個子節點都必須是黑色的。

   這個特性是維持平衡的關鍵之一。它直接禁止了任何路徑上出現兩個連續的紅色節點。這也意味著，從任何節點出發向下的路徑中，紅色節點的數量不會超過黑色節點。

5. 對於每個節點，從該節點到其所有後代葉子節點的每條簡單路徑上，都包含相同數量的黑色節點。

   這個特性是紅黑樹最精妙也最強大的規則。它定義了一個概念叫做「黑高(black-height)」，指從某個節點 x 出發（不含 x 本身）到其後代葉子節點的任何路徑上的黑色節點數量，記為 $\operatorname { b h } ( x )$。此規則確保了對於任何一個節點，其所有向下的路徑「黑色長度」都是相等的。結合第四個特性，這保證了沒有任何一條路徑會比其他路徑長太多，從而讓樹保持「近似平衡」。

標準的二元搜尋樹在理想情況下效能很好，但它有一個致命的缺點：它的效能完全取決於樹的高度 h，所有基本操作的時間複雜度都是 $O(h)$。如果插入的資料是隨機的，樹的高度期望值是 $O(\lg n)$，效能優異。但如果插入的資料是已排序的（例如，依序插入 1, 2, 3, 4, 5），二元搜尋樹會退化成一個鏈結串列(linked list)，樹高 h 會變成 $n$，此時操作的效能會急遽下降到 $O(n)$，完全喪失了樹狀結構的優勢。

紅黑樹的誕生就是為了解決這個「最壞情況」下的效能崩潰問題。它透過上述的五個特性，強制約束樹的結構，確保樹的高度始終維持在 $O(\lg n)$ 的量級。如此一來，即使在最壞的情況下，紅黑樹的各種動態集合操作（如搜尋、插入、刪除、找最大/最小值等）的時間複雜度也能保證為 $O(\lg n)$。

介紹完以上四種常見的有根樹類型，我們可以用以下簡單的比喻來更清楚的了解它們之間的關係：

首先，二元樹(Binary Tree) 是這個家族的始祖。而堆積(Heap) 和二元搜尋樹(Binary Search Tree) 是始祖的兩個孩子，它們繼承了始祖的特徵，但發展出完全不同的個性。最後，紅黑樹(Red-Black Tree) 則是二元搜尋樹這個孩子為了讓自己更強大、更可靠，而進化出的「專家」型態。

雜湊表(Hash Tables)

雜湊表是一種高效的資料結構，它透過一個稱為雜湊函數(hash function)的特殊函數，將一個鍵(key)直接計算並對應到陣列中的特定位置——稱為槽位(slot)，以實現快速的資料存取。

要深入理解雜湊表，我們可以將它的特性拆解為以下幾個核心觀念：

• 核心運作：透過雜湊函數進行映射

  雜湊表的根本思想是使用一個雜湊函數(hash function)，這個函數的任務是將一個龐大甚至無限的「所有可能的鍵的宇宙(universe of keys, $U$)」，轉換或映射到一個大小固定且小得多的陣列索引範圍內，通常是 $\{0, 1, ..., m-1\}$，其中 $m$ 是雜湊表——也就是底層陣列——的大小。

  • 雜湊值(Hash Value)：對於一個給定的鍵 $k$，經過雜湊函數計算出的索引值 $h(k)$ 就是它的雜湊值。

  • 理想的雜湊函數：一個好的雜湊函數應該近似於「獨立均勻雜湊(independent uniform hashing)」，意思是每個鍵都應該有均等的機率被雜湊到任何一個槽位，且與其他鍵被雜湊到哪裡無關。實際上，要設計一個對所有可能的輸入都表現完美的固定函數是很困難的，因此現代方法傾向於從一個函數家族中隨機挑選一個來使用，這就是所謂的隨機雜湊(random hashing)。

• 核心問題：碰撞(Collision)

  當雜湊函數將兩個或多個不同的鍵映射到同一個槽位時，這種情況就稱為「碰撞」。由於可能的鍵的數量 $|U|$ 通常遠大於槽位的數量 $m$，碰撞是不可避免的。因此，如何有效處理碰撞是雜湊表設計的關鍵，這也衍生出主要的解決策略。

• 核心策略：碰撞解決方法

  兩種主流的碰撞解決方法：

  • 鏈結法(Chaining) —— 外部儲存

    • 概念：將雜湊到同一個槽位的所有元素，用一個鏈結串列(linked list)儲存起來。雜湊表的每個槽位實質上是一個指向該串列頭部的指標。

    • 運作：

      • 插入(INSERT)：計算雜湊值，直接將新元素加到對應鏈結串列的最前端，時間複雜度為 $O(1)$。

      • 搜尋(SEARCH)：計算雜湊值，然後在對應的鏈結串列中進行線性搜尋。

      • 刪除(DELETE)：如果串列是雙向的(doubly linked)，刪除操作也只需要 $O(1)$ 的時間。

    • 效能：平均效能取決於「負載因子(load factor)」 $\alpha$，定義為 $\alpha = n / m$（元素數量 / 槽位數量），它代表了每個鏈結串列的平均長度。在獨立均勻雜湊的假設下，無論成功或失敗的搜尋，平均時間複雜度都是 $\Theta(1 + \alpha)$。

  • 開放定址法(Open Addressing) —— 內部消化

    • 概念：所有元素都直接儲存在雜湊表這個陣列本身，不使用任何外部儲存結構（如鏈結串列）。當發生碰撞時，它會去探測(probe) 表格中的下一個可用槽位，直到找到空位為止。

    • 探測序列：每個鍵的探測順序由一個擴展的雜湊函數 $h(k, i)$ 決定，其中 $i$ 是探測的次數（從 0 開始）。一個好的探測序列應該能遍歷所有槽位。

      • 線性探測(Linear Probing)：最簡單，但也最笨拙。如果位置 i 被佔，就試 i+1，再試 i+2... 這種方法會導致「一次群聚」，也就是佔用的槽位會連成一片，嚴重影響效能。

      • 雙重雜湊(Double Hashing)：更聰明的方法。它用兩個雜湊函數，一個決定起始位置，另一個決定探測的「步長」。這使得探測序列更加分散，效能接近理想狀態。

    • 效能：效能同樣與負載因子 $\alpha$ 密切相關，但這裡 $\alpha$ 不能超過 1。當表格越滿（$\alpha$ 趨近於 1），找到空槽位的預期探測次數會急劇增加。

• 實際應用的考量：記憶體階層

  傳統分析通常假設記憶體存取時間是固定的，但在現代電腦架構中，CPU 快取 (cache)的存在改變了遊戲規則。

  • 線性探測的優勢：雖然在理論模型中，線性探測因主叢集(primary clustering) 問題——也就是被佔用的槽位會傾向於連成一長串——而效能較差，但在有記憶體階層的系統中，這反而成為優點。因為連續的探測很有可能都命中同一個快取區塊(cache block)，這遠比隨機存取不同記憶體位置來得快。

  • 複雜的雜湊函數：因為複雜的計算（如加密等級的雜湊函數）可以在 CPU 的快速暫存器中完成，它的耗時可能比一次主記憶體讀取還少。因此，在現代硬體上，使用一個計算上更複雜但隨機性更好的雜湊函數，搭配具有良好局部性(locality) 的線性探測，反而能達到極高的整體效能。

雜湊表的出現主要是為了解決直接定址表(Direct-address Table) 的根本性限制。

• 直接定址表的概念：這是一種最簡單的想法，直接將鍵 $k$ 作為陣列的索引值，也就是把資料存在陣列的第 $k$ 個位置。這種方式非常快，所有操作都是 $O(1)$。

• 直接定址表的困境：這個方法只有在「所有可能的鍵的宇宙 $U$」很小的時候才可行。舉例來說，如果你的鍵是英文單字或人名（字串），可能的組合數量是天文數字。若要為每一個可能的鍵都預留一個陣列槽位，將會需要不切實際、甚至不可能實現的龐大記憶體空間，而且其中絕大多數空間都會被浪費掉。

• 雜湊表的解決方案：雜湊表完美地解決了這個問題。它使用的陣列大小通常只與「實際儲存的元素數量」成正比，而不是與「所有可能的鍵的數量」成正比。透過雜湊函數，它將龐大的鍵空間壓縮到一個可管理的陣列大小中，從而大幅節省了儲存空間。

雜湊表的優勢包含以下：

• 極高的平均速度：這是雜湊表最核心的優勢。在合理的假設下——例如：使用一個好的雜湊函數，雜湊表支援的插入、搜尋和刪除等字典操作的平均時間複雜度為 $O(1)$。這比基於樹狀結構的 $O(\lg n)$ 搜尋時間還要快，使它成為實現需要高速查找的動態集合的絕佳選擇。

• 空間效率：當實際儲存的鍵集合 $K$ 相對於所有可能的鍵宇宙 $U$ 非常小時，雜湊表所需的儲存空間遠小於直接定址表，空間利用率極高。

然而，雜湊表還是有它的劣勢：

• 糟糕的最壞情況效能：這是雜湊表最主要的缺點。如果雜湊函數設計不佳，或者有惡意攻擊者刻意構造一組特定的鍵，可能導致所有鍵都「碰撞」到同一個槽位。在這種情況下：

  • 如果使用鏈結法(Chaining)，雜湊表會退化成一個長度為 $n$ 的鏈結串列，搜尋時間從 $O(1)$ 惡化到 $O(n)$。

  • 如果使用開放定址法(Open Addressing)，表格會很快被填滿，導致後續操作的探測次數急劇增加。

• 對負載因子敏感：特別是對於開放定址法，當負載因子 $\alpha$ 升高——也就是表格變滿——時，效能會顯著下降。

• 無序性：雜湊表中的元素是根據它的雜湊值存放的，這通常是無序的。因此，雜湊表不適合需要範圍查詢、或需要快速找到最大/最小值、前驅/後繼元素的應用。這些操作在如二元搜尋樹等有序的資料結構中更有效率。

參考資料

Introduction to Algorithms, fourth edition

附錄

本文為系列文章，目前寫了五篇:

1. 認識演算法：啟程
2. 認識演算法：常用資料結構
3. 認識演算法：各種比較排序
4. 認識演算法：各種線性時間排序
5. 認識演算法：選擇問題