深入解析樹狀結構、紅黑樹與雜湊表

– 11 分鐘閱讀

在資料結構的世界中，樹狀結構、紅黑樹和雜湊表扮演著重要的角色。理解這些結構的特性和應用，對於軟體開發至關重要。本文首先以雙向佇列的 Pascal 示例作為開場，引出資料結構的討論。接著，我們深入探討樹狀結構的定義、高度、層級，以及二元樹、平衡二元樹、有序二元樹等概念。接著，文章比較了二元搜尋樹和紅黑樹，並詳細介紹了紅黑樹的特性、優點、實作步驟以及遍歷方法。同時，我們也探討了樹狀結構的遍歷方法，包括深度優先遍歷（前序、中序、後序）和廣度優先遍歷，並提供了 Delphi 程式碼示例。此外，文章還涵蓋了雜湊表的工作原理、優缺點，以及 Spring 中的雜湊表應用、ISet 和 IOrderedSet 介面。最後，我們討論了集合和字典的區別，以及多重集合的特性和應用，並提供了 Pascal 程式碼示例。

雙向佇列的操作

以下是使用雙向佇列的示例：

var
  i: integer;
  llDeque: IDeque<string>;
  s: string;
begin
  llDeque := TCollections.CreateDeque<string>;
  
  for i := 1 to 7 do
  begin
    if Odd(i) then
      llDeque.AddFirst(IntToStr(i))
    else
      llDeque.AddLast(IntToStr(i));
  end;
  
  ListBox1.Items.Add('Deque: ' + ''.Join(' ', llDeque.ToArray));
  s := 'Deque remove: ';
  
  for i := 1 to 7 do
  begin
    if Odd(i) then
      s := s + llDeque.RemoveFirst + ' '
    else
      s := s + llDeque.RemoveLast + ' ';
  end;
  
  ListBox1.Items.Add(s);
end;

這個示例建立了一個雙向佇列，增加了從 1 到 7 的字串，然後移除元素並顯示結果。

樹狀結構簡介

樹狀結構是一種常見的資料結構，與堆積疊和佇列不同，它可以被視為一個有節點和邊的圖形。每個節點可以有零個或多個子節點，子節點又可以有自己的子節點，以此類推。樹狀結構的特點是，每個節點都有一個父節點，除了根節點之外。

樹狀結構的定義

樹狀結構可以被定義為一個空樹或一個節點指向零個或多個樹的結構。每個非空樹都有一個根節點，根節點連線到零個或多個子節點，子節點又連線到零個或多個子節點，以此類推。沒有子節點的節點被稱為葉節點。

樹狀結構的高度

樹狀結構的高度是從根節點到葉節點的最長路徑。每個節點的高度可以被定義為從該節點到其子節點的最長路徑的長度。葉節點的高度為0。

樹狀結構的層級

樹狀結構的層級是從根節點到某個節點的連線數量。根節點的層級為0，其子節點的層級為1，以此類推。

二元樹

二元樹是一種特殊的樹狀結構，每個節點最多有兩個子節點。二元樹的特點是，每個節點都有一個左子樹和一個右子樹，任何一個子樹都可以是空的。

平衡二元樹

平衡二元樹是一種二元樹，其左子樹和右子樹的高度差不超過1。這種樹狀結構可以保證查詢、插入和刪除操作的時間複雜度為O(log n)。

有序二元樹

有序二元樹是一種二元樹，其節點的值遵循一定的順序。每個節點的左子樹的值都小於該節點的值，右子樹的值都大於該節點的值。這種樹狀結構被稱為二元查詢樹。

二元查詢樹的優點和缺點

二元查詢樹的優點是查詢、插入和刪除操作的時間複雜度為O(log n)。但是，二元查詢樹的缺點是它很難保持平衡，尤其是在插入和刪除操作之後。

平衡二元查詢樹

平衡二元查詢樹是一種二元查詢樹，其左子樹和右子樹的高度差不超過1。這種樹狀結構可以保證查詢、插入和刪除操作的時間複雜度為O(log n)。但是，平衡二元查詢樹的實作比較複雜。

  graph TD
    A[根節點] --> B[左子樹]
    A --> C[右子樹]
    B --> D[葉節點]
    C --> E[葉節點]

圖表翻譯：

此圖示為一棵簡單的二元樹，根節點A連線到左子樹B和右子樹C，左子樹B連線到葉節點D，右子樹C連線到葉節點E。這種樹狀結構可以用於查詢、插入和刪除操作。

二元搜尋樹（BST）與紅黑樹（Red-Black Tree）

二元搜尋樹（BST）是一種特殊的樹狀資料結構，它的每個節點最多有兩個子節點，分別是左子節點和右子節點。每個節點的值大於其左子節點的值，且小於其右子節點的值。這種結構使得二元搜尋樹可以快速地進行搜尋、插入和刪除操作。

然而，二元搜尋樹有一個缺點，就是它可能會變得不平衡，導致搜尋效率下降。為瞭解決這個問題，紅黑樹（Red-Black Tree）被提出。紅黑樹是一種自平衡的二元搜尋樹，它透過對節點的顏色進行標記和調整，來保持樹的平衡。

紅黑樹的特性

紅黑樹具有以下特性：

  • 每個節點都有一個顏色，分別是紅色和黑色。
  • 根節點的顏色是黑色。
  • 如果一個節點是紅色，那麼它的子節點必須是黑色。
  • 每個節點到其子孫節點的黑色節點數量是相同的。

這些特性確保了紅黑樹的平衡，從而保證了搜尋、插入和刪除操作的效率。

紅黑樹的優點

紅黑樹具有以下優點：

  • 自平衡：紅黑樹可以自動調整其結構，以保持平衡，從而保證搜尋效率。
  • 高效的搜尋：紅黑樹的搜尋效率是 O(log n)，遠高於一般的二元搜尋樹。
  • 高效的插入和刪除：紅黑樹的插入和刪除操作也很高效，時間複雜度是 O(log n)。

實作紅黑樹

紅黑樹的實作需要考慮以下幾個步驟：

  1. 建立節點：每個節點需要有一個值、左子節點、右子節點和顏色。
  2. 插入節點：當插入一個新節點時，需要調整樹的結構，以保持平衡。
  3. 刪除節點：當刪除一個節點時，需要調整樹的結構，以保持平衡。
  4. 搜尋節點：紅黑樹的搜尋效率是 O(log n)，可以快速地找到目標節點。

遍歷紅黑樹

紅黑樹的遍歷可以分為兩種：深度優先遍歷（Depth-First Traversal）和廣度優先遍歷（Breadth-First Traversal）。

  • 深度優先遍歷：先存取根節點，然後存取其左子節點和右子節點，直到存取到葉節點。
  • 廣度優先遍歷：先存取根節點，然後存取其所有子節點，直到存取到葉節點。

紅黑樹的遍歷可以使用遞迴或迭代的方式實作。

// 深度優先遍歷
fn depth_first_traversal(node: &Option<Box<Node>>) {
    match node {
        Some(node) => {
            println!("{}", node.value);
            depth_first_traversal(&node.left);
            depth_first_traversal(&node.right);
        }
        None => {}
    }
}

// 廣度優先遍歷
fn breadth_first_traversal(node: &Option<Box<Node>>) {
    let mut queue = Vec::new();
    queue.push(node);
    while let Some(node) = queue.pop() {
        match node {
            Some(node) => {
                println!("{}", node.value);
                queue.push(&node.left);
                queue.push(&node.right);
            }
            None => {}
        }
    }
}

樹狀結構的遍歷和實作

樹狀結構是一種基本的資料結構，遍歷樹狀結構可以使用多種方法，包括深度優先遍歷（Depth-First Traversal）和廣度優先遍歷（Breadth-First Traversal）。

深度優先遍歷

深度優先遍歷是指從樹的根節點開始，沿著左子樹或右子樹不斷向下遍歷，直到到達葉節點。深度優先遍歷可以分為三種：前序遍歷（Pre-Order）、中序遍歷（In-Order）和後序遍歷（Post-Order）。

前序遍歷

前序遍歷是指先存取根節點，然後遍歷左子樹和右子樹。以下是前序遍歷的實作：

procedure TfrmTrees.btnRBTree1Click(Sender: TObject);
var
  tree: IRedBlackTree<integer>;
  i: integer;
  node: TNodes<integer>.PRedBlackTreeNode;
  s: string;
begin
  tree := TRedBlackTree<integer>.Create;
  for i := 15 downto 1 do
    tree.Add(i);
  s := '';
  for node in tree.Root.PreOrder do
    s := s + IntToStr(node.Key) + ' ';
  ListBox1.Items.Add('PreOrder: ' + s);
end;

中序遍歷

中序遍歷是指先遍歷左子樹，然後存取根節點，最後遍歷右子樹。以下是中序遍歷的實作：

procedure TfrmTrees.btnRBTree1Click(Sender: TObject);
var
  tree: IRedBlackTree<integer>;
  i: integer;
  node: TNodes<integer>.PRedBlackTreeNode;
  s: string;
begin
  tree := TRedBlackTree<integer>.Create;
  for i := 15 downto 1 do
    tree.Add(i);
  s := '';
  for node in tree.Root.InOrder do
    s := s + IntToStr(node.Key) + ' ';
  ListBox1.Items.Add('InOrder: ' + s);
end;

後序遍歷

後序遍歷是指先遍歷左子樹和右子樹，然後存取根節點。以下是後序遍歷的實作：

procedure TfrmTrees.btnRBTree1Click(Sender: TObject);
var
  tree: IRedBlackTree<integer>;
  i: integer;
  node: TNodes<integer>.PRedBlackTreeNode;
  s: string;
begin
  tree := TRedBlackTree<integer>.Create;
  for i := 15 downto 1 do
    tree.Add(i);
  s := '';
  for node in tree.Root.PostOrder do
    s := s + IntToStr(node.Key) + ' ';
  ListBox1.Items.Add('PostOrder: ' + s);
end;

廣度優先遍歷

廣度優先遍歷是指從樹的根節點開始，先遍歷所有的子節點，然後遍歷子節點的子節點，直到到達葉節點。以下是廣度優先遍歷的實作：

procedure TfrmTrees.btnRBTree2Click(Sender: TObject);
var
  q, q2: IQueue<TNodes<integer>.PRedBlackTreeNode>;
  node: TNodes<integer>.PRedBlackTreeNode;
  t: IRedBlackTree<integer>;
  i: integer;
  s: string;
begin
  t := TRedBlackTree<integer>.Create;
  for i := 15 downto 1 do
    t.Add(i);
  q := TCollections.CreateQueue<TNodes<integer>.PRedBlackTreeNode>;
  q.Enqueue(TNodes<integer>.PRedBlackTreeNode(t.Root));
  while not q.IsEmpty do
  begin
    s := '';
    q2 := TCollections.CreateQueue<TNodes<integer>.PRedBlackTreeNode>;
    while not q.IsEmpty do
    begin
      node := q.Dequeue;
      if not assigned(node) then
        s := s + 'x ';
      // ...
    end;
  end;
end;

資料結構：紅黑樹的實作和應用

紅黑樹是一種自平衡的二元搜尋樹，它的每個節點都有一個顏色（紅色或黑色），並且根節點是黑色的。紅黑樹的實作可以用於多種資料結構，包括集合和字典。

紅黑樹的特性

紅黑樹具有以下特性：

  • 每個節點都有一個顏色（紅色或黑色）
  • 根節點是黑色的
  • 每個葉節點（NULL）是黑色的
  • 如果一個節點是紅色的，則它的兩個子節點必須是黑色的
  • 對於任何節點，從該節點到其子孫葉節點的所有路徑必須包含相同數量的黑色節點

紅黑樹的實作

紅黑樹的實作可以用於多種資料結構，包括集合和字典。以下是紅黑樹的實作範例：

procedure TfrmTrees.btnRBTree3Click(Sender: TObject);
var
  tree: IRedBlackTree<integer, string>;
  node: TPair<integer, string>;
begin
  tree := TRedBlackTree<integer, string>.Create;
  tree.Add(3, 'three');
  tree.Add(1, 'one');
  tree.Add(2, 'two');
  tree.Add(1, 'One');

  for node in tree do
    ListBox1.Items.Add(IntToStr(node.Key) + ': ' + node.Value);
end;

在這個範例中，紅黑樹的實作使用了 TRedBlackTree 類別，該類別提供了 Add 方法用於插入資料。紅黑樹的實作也提供了 IRedBlackTree 介面，用於存取樹中的資料。

紅黑樹的複雜度

紅黑樹的複雜度如下：

  • 重平衡：O(1)
  • 存取：O(log n)
  • 搜尋：O(log n)
  • 插入：O(log n)
  • 刪除：O(log n)

集合和字典

紅黑樹的實作也可以用於集合和字典。集合是一種資料結構，包含了一組唯一的元素，而字典是一種資料結構，包含了一組鍵值對。

圖表翻譯：
  graph LR
    A[紅黑樹] --> B[集合]
    A --> C[字典]
    B --> D[唯一元素]
    C --> E[鍵值對]

在這個圖表中，紅黑樹是一種資料結構，包含了集合和字典。集合包含了一組唯一的元素，而字典包含了一組鍵值對。

什麼是雜湊表（Hash Table）？

雜湊表是一種資料結構，它使用雜湊函式將鍵（key）轉換為索引（index），以便存取和管理資料。它是一種高效的資料結構，能夠快速地新增、刪除和查詢資料。

雜湊表的工作原理

雜湊表使用雜湊函式將鍵轉換為索引，然後使用這個索引來存取和管理資料。當我們新增或刪除資料時，雜湊表會自動更新索引，以確保資料的正確性和效率。

雜湊表的優點

雜湊表有一些優點，包括：

  • 快速的新增、刪除和查詢資料
  • 高效的資料管理
  • 支援大型資料集

雜湊表的缺點

雜湊表也有一些缺點，包括：

  • 雜湊函式可能會產生碰撞（collision），導致資料的不正確性
  • 雜湊表可能需要更多的記憶體空間來儲存索引

Spring 中的雜湊表

Spring 中的雜湊表是一種高效的資料結構，能夠快速地新增、刪除和查詢資料。它使用雜湊函式將鍵轉換為索引，然後使用這個索引來存取和管理資料。

ISet 介面

ISet 介面是一種集合介面，能夠儲存和管理一組唯一的資料。它提供了一些方法，包括新增、刪除和查詢資料。

ISet 的方法

ISet 介面提供了一些方法，包括：

  • Add：新增資料到集合中
  • Remove：刪除資料從集合中
  • Contains：查詢資料是否存在於集合中
  • ExceptWith：從集合中刪除指定的資料
  • IntersectWith：傳回集合中與指定集合共同的資料
  • UnionWith：傳回集合中與指定集合合併的資料
  • IsSubsetOf：查詢集合是否為指定集合的子集
  • IsSupersetOf：查詢集合是否為指定集合的超集
  • SetEquals：查詢集合是否與指定集合相等
  • Overlaps：查詢集合是否與指定集合有交集

Spring 中的 ISet 實作

Spring 中的 ISet 介面有兩種實作：正常的集合和排序的集合。正常的集合使用雜湊表來儲存和管理資料，而排序的集合使用紅黑樹來儲存和管理資料。

IOrderedSet 介面

IOrderedSet 介面是一種有序的集合介面，能夠儲存和管理一組唯一的資料。它提供了一些方法，包括新增、刪除和查詢資料。

IOrderedSet 的方法

IOrderedSet 介面提供了一些方法，包括：

  • Add：新增資料到集合中
  • Remove：刪除資料從集合中
  • Contains：查詢資料是否存在於集合中
  • IndexOf：傳回資料在集合中的索引
  • Items：傳回集合中的資料

集合和字典

在電腦科學中，集合（Set）是一種資料結構，用於儲存唯一的元素。然而，在實際應用中，我們經常需要儲存相同的元素多次，這就是多重集合（MultiSet）的用途。

集合的時間複雜度

集合的時間複雜度取決於其實作方式。未排序的集合使用雜湊表實作，操作速度快於排序集合，後者使用樹實作。

  • 存取：未排序集合的最佳情況為 O(1)，最壞情況為 O(n)，排序集合不適用。
  • 搜尋：未排序集合為 O(1)，排序集合為 O(log n)。
  • 插入：未排序集合為 O(1)，排序集合為 O(log n)。
  • 刪除：未排序集合為 O(1)，排序集合為 O(log n)。

多重集合

多重集合是一種可以儲存相同元素多次的集合。它由 IMultiSet<T> 介面定義，該介面繼承自 ICollection<T>。

TMultiSetEntry<T> = packed record
  Item: T;
  Count: Integer;
end;

IMultiSet<T> = interface(ICollection<T>)
  function Add(const item: T; count: Integer): Integer;
  function Remove(const item: T; count: Integer): Integer;
  function SetEquals(const other: IEnumerable<T>): Boolean;
  function OrderedByCount: IReadOnlyMultiSet<T>;
  property Entries: IReadOnlyCollection<TMultiSetEntry<T>>
    read GetEntries;
  property Items: IReadOnlyCollection<T> read GetItems;
  property ItemCount[const item: T]: Integer
    read GetItemCount write SetItemCount; default;
end;

與正常集合不同，多重集合不實作標準的集合操作（聯合、交集等）。但是，它可以傳回不同資料檢視。Entries 屬性傳回一個唯讀集合，包含（值，計數）對；Items 屬性傳回一個只包含值的集合；ItemCount 屬性傳回或設定元素的出現次數。

實作和使用

Spring 實作了兩種多重集合：未排序和排序。未排序的多重集合使用雜湊表實作，排序的多重集合使用紅黑樹實作。

class function CreateMultiSet<T>: IMultiSet<T>;
class function CreateSortedMultiSet<T>: IMultiSet<T>;

以下程式碼示範了多重集合的基本使用：

procedure TfrmSetMultiMap.TestSet(const name: string;
  const aset: ICollection<integer>);

var
  i: integer;

begin
  for i := 4 downto 1 do
    aset.Add(i);
  aset.Add(1);
  ListBox1.Items.Add(name + ': ' + Join(' ', aset));
end;

procedure TfrmSetMultiMap.btnSetClick(Sender: TObject);

begin
  TestSet('Set', TCollections.CreateSet<integer>);
  TestSet('SortedSet', TCollections.CreateSortedSet<integer>);
  TestSet('MultiSet', TCollections.CreateMultiSet<integer>);
  TestSet('SortedMultiSet', TCollections.CreateSortedMultiSet<integer>);
end;

字典與集合的比較

在集合中，我們可以看到「正常」版本的輸出元素按照插入順序，而「排序」版本的輸出元素按照排序順序。此外，集合中只包含一個值1的出現，而多重集合中包含兩個值1的出現。

從資料結構的底層實作到高階應用的全面檢視顯示，理解資料結構的特性與應用場景至關重要。本文探討了多種資料結構，包含雙向佇列、樹狀結構（特別是二元樹、紅黑樹）、雜湊表、集合以及多重集合，分析了它們的優缺點、操作方法以及時間複雜度。由於不同資料結構的特性不同，例如紅黑樹的自平衡特性使其在搜尋、插入和刪除操作上效率更高，而雜湊表則更適用於快速的資料存取，因此，選擇合適的資料結構對於提升程式效能至關重要。技術團隊應著重於理解各種資料結構的特性和使用限制，例如雜湊表的碰撞問題或二元搜尋樹的不平衡問題，才能根據實際需求選擇最佳方案。隨著資料量的增長和應用場景的複雜化，我們預見更高效、更專精的資料結構將持續發展，並在不同領域發揮關鍵作用。對於追求效能最佳化的開發者而言，深入理解並善用這些資料結構將是提升程式碼品質和效率的關鍵。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。