紅黑樹資料結構深入剖析

– 8 分鐘閱讀

紅黑樹是一種自平衡的二元搜尋樹，它在保持資料有序性的同時，提供了高效的插入、刪除和查詢操作。透過引入節點顏色（紅或黑）以及一系列嚴格的規則，紅黑樹能夠有效控制樹的高度，確保在各種操作下維持平衡，避免效能退化。這使得紅黑樹在需要頻繁變更資料的場景中，相較於其他樹狀結構，更能展現其優勢。理解紅黑樹的特性和實作原理，對於提升程式效能至關重要。

樹狀結構的平衡藝術

在探討資料結構時，我們經常會遇到一種既簡單又複雜，但最重要的特點是可以達到平衡的結構——樹。樹狀結構可以被遞迴地定義為：要麼是一個空樹，要麼是一個節點指向零個或多個子樹。

樹的基本組成

每個非空樹都有一個起始節點（根節點），它連線到零個或多個子節點（內部節點），而這些子節點又可以連線到更多的節點。有些節點沒有子節點，我們稱之為葉節點。每個子節點（除了根節點）都有且僅有一個父節點，這一規則確保了樹不會形成環而變成圖。

節點的高度與層級

一個重要的屬性是節點的高度，它被定義為從該節點到其可達的任一葉節點的最長路徑。樹的高度則是根節點的高度。根據定義，葉節點的高度為0。一個節點的高度也可以遞迴地定義：如果它沒有子節點，則高度為0；否則，其高度是其子節點高度的最大值加一。

另一個有用的屬性是節點的層級，它被定義為該節點與樹根之間的連線數。

二元樹與平衡

在電腦科學中，二元樹因其簡單易用而被廣泛使用。二元樹是一種特殊的樹，其中每個節點最多有兩個子節點。我們也稱每個節點都有左、右子樹（其中任一可能為空）。然而，二元樹並非萬能，其他常見的樹結構包括2-3樹、B樹和B+樹。

為了獲得最佳效能，我們希望樹盡可能平衡。一個平衡的二元樹是指其左右子樹的高度差不超過1。對於非二元樹，我們可以計算每個節點所有子節點的高度，如果最小和最大高度差不超過1，則該樹是平衡的。

有序二元樹（BST）

在實務應用中，每個節點除了儲存連線資訊外，還會持有一個我們感興趣的值。實際上，這個值才是節點的重要部分。有序二元樹（BST）是一種特殊的二元樹，其中每個節點左子樹的值都小於父節點的值，而右子樹的值都大於父節點的值。這種結構使得所有操作都能達到O(log n)的時間複雜度。

然而，保持BST平衡是一個挑戰。當我們向樹中插入新值時，可能會導致樹失去平衡。此時，我們需要透過一系列旋轉操作來重新平衡樹。

紅黑樹

紅黑樹是一種特殊的BST，它透過引入顏色屬性（紅或黑）並施加特定約束來保持自平衡。紅黑樹的定義包括以下屬性：

  • 每個節點都有顏色（紅或黑）
  • 紅節點只能有黑子節點
  • 從任一節點到其所有後代葉節點的路徑上，黑節點數量相同

這種結構確保了紅黑樹在插入和刪除操作後仍能保持平衡，從而保證搜尋操作的時間複雜度為O(log n)，且平均而言，平衡操作的時間複雜度為O(1)。

紅黑樹的操作解密：

紅黑樹透過旋轉和重新著色來保持平衡。在插入或刪除節點後，紅黑樹可能會違反其定義屬性，此時需要進行調整以還原平衡。

class Node:
    def __init__(self, value, color='red'):
        self.value = value
        self.color = color
        self.left = None
        self.right = None
        self.parent = None

class RedBlackTree:
    def __init__(self):
        self.NIL = Node(None, color='black')
        self.root = self.NIL

    def insert(self, value):
        node = Node(value)
        node.parent = None
        node.left = self.NIL
        node.right = self.NIL

        # 插入邏輯
        # ...

        # 插入後調整以保持紅黑樹性質
        self.fix_insert(node)

    def fix_insert(self, node):
        # 調整邏輯，包括旋轉和重新著色
        # ...

內容解密：

  1. Node類別代表紅黑樹中的一個節點，包含值、顏色、左右子節點和父節點。
  2. RedBlackTree類別代表整個紅黑樹，包含一個特殊的NIL節點代表空節點。
  3. insert方法用於插入新節點，並在插入後呼叫fix_insert方法以保持紅黑樹的性質。
  4. fix_insert方法負責在插入後進行必要的調整，包括旋轉和重新著色，以確保紅黑樹的平衡。

圖表翻譯：

此圖示展示了一個紅黑樹的例子，其中每個節點都有顏色標註，並且滿足紅黑樹的所有定義屬性。透過觀察這個圖表，我們可以看到紅黑樹如何透過顏色屬性和特定的結構約束來保持自平衡。

圖表翻譯： 圖中展示了一棵紅黑樹，其根節點為黑色，所有路徑上的黑色節點數量一致，且沒有兩個連續的紅色節點。這個結構保證了搜尋、插入和刪除操作的高效性。

紅黑樹的儲存與遍歷最佳化

紅黑樹是一種自平衡的二元搜尋樹，能夠在保持資料有序的同時，提供高效的插入、刪除和查詢操作。紅黑樹透過節點的顏色（紅色或黑色）來維持樹的平衡，確保樹的高度保持在對數級別，從而實作快速的資料存取。

紅黑樹的特性與優勢

紅黑樹具有以下幾個關鍵特性：

  1. 節點顏色：每個節點要麼是紅色，要麼是黑色。
  2. 根節點：根節點是黑色的。
  3. 葉節點：所有葉節點（NIL節點）都是黑色的。
  4. 紅色節點限制：如果一個節點是紅色的，則它的兩個子節點都必須是黑色的。
  5. 黑色高度：對於任意節點，其到達所有葉節點的路徑上，黑色節點的數量是相同的。

這些特性確保了紅黑樹在最壞情況下的高度為 $2\log(n+1)$，從而保證了插入、刪除和查詢操作的高效性。

節點顏色的編碼與最佳化

由於節點顏色只有兩種可能（紅色和黑色），可以用一個位元來表示。Spring框架透過將顏色資訊隱藏在節點之間的指標中，實作了對記憶體的高效利用。這種最佳化方法可以避免額外的記憶體開銷。

程式碼實作：顏色資訊的提取

const
  ColorMask = IntPtr(1);
  PointerMask = not ColorMask;

function TRedBlackTree.TNode.GetColor: TNodeColor;
begin
  Result := TNodeColor(IntPtr(fParent) and ColorMask);
end;

function TRedBlackTree.TNode.GetParent: PNode;
begin
  Result := Pointer(IntPtr(fParent) and PointerMask);
end;

#### 內容解密：

  • ColorMask 和 PointerMask 用於從 fParent 欄位中提取顏色資訊和父節點指標。
  • GetColor 方法透過將 fParent 與 ColorMask 進行位元與運算，取得節點的顏色。
  • GetParent 方法透過將 fParent 與 PointerMask 進行位元與運算，取得父節點的指標。

紅黑樹的操作介面

Spring框架中的紅黑樹實作提供了簡單易用的介面，包括插入、刪除、查詢和遍歷等操作。主要的介面包括 IRedBlackTree<T> 和 IRedBlackTree<TKey, TValue>，前者用於儲存單一型別的值，後者用於儲存鍵值對。

程式碼實作：紅黑樹的操作介面

IBinaryTree<T> = interface(IBinaryTree)
  function Add(const key: T): Boolean;
  function Delete(const key: T): Boolean;
  function Exists(const key: T): Boolean;
  function Find(const key: T; var value: T): Boolean;
  procedure Clear;
  function GetEnumerator: IEnumerator<T>;
  function ToArray: TArray<T>;
  property Root: TNodes<T>.PRedBlackTreeNode read GetRoot;
end;

IRedBlackTree<T> = interface(IBinaryTree<T>)
  function FindNode(const value: T): TNodes<T>.PRedBlackTreeNode;
  procedure DeleteNode(node: TNodes<T>.PRedBlackTreeNode);
end;

#### 內容解密：

  • Add、Delete 和 Exists 方法分別用於插入、刪除和查詢節點。
  • FindNode 方法用於查詢特定的節點，並傳回其指標。
  • DeleteNode 方法用於刪除指定的節點。
  • GetEnumerator 和 ToArray 方法用於遍歷和匯出樹中的所有節點。

紅黑樹的遍歷方法

紅黑樹支援多種遍歷方式，包括深度優先遍歷（前序、中序、後序）和廣度優先遍歷。中序遍歷常用於按順序存取樹中的節點。

程式碼實作：遍歷紅黑樹

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 i in tree do s := s + IntToStr(i) + ' ';
  ListBox1.Items.Add('Enumerator: ' + s);
  
  s := '';
  for node in tree.Root.InOrder do
    s := s + IntToStr(node.Key) + ' ';
  ListBox1.Items.Add('InOrder: ' + s);
  
  s := '';
  for node in tree.Root.PreOrder do
    s := s + IntToStr(node.Key) + ' ';
  ListBox1.Items.Add('PreOrder: ' + s);
  
  s := '';
  for node in tree.Root.PostOrder do
    s := s + IntToStr(node.Key) + ' ';
  ListBox1.Items.Add('PostOrder: ' + s);
end;

#### 內容解密：

  • 使用 for .. in 陳述式遍歷樹中的所有節點，並輸出其值。
  • 使用 InOrder、PreOrder 和 PostOrder 方法分別進行中序、前序和後序遍歷，並輸出遍歷結果。

紅黑樹的遍歷與實作

在探討紅黑樹（Red-Black Tree）的遍歷方式時，我們可以觀察到不同的遍歷方法對於樹的結構有著不同的影響。深度優先（Depth-First）遍歷是一種常見的方法，它按照一定的順序存取樹中的節點。

深度優先遍歷

深度優先遍歷可以進一步分為前序（Pre-order）、中序（In-order）和後序（Post-order）三種遍歷方式。其中，中序遍歷對於紅黑樹來說尤其重要，因為它能夠按照排序順序傳回節點的值。

程式碼範例：

// 深度優先遍歷（中序）
procedure TfrmTrees.btnRBTree1Click(Sender: TObject);
var
  tree: IRedBlackTree<integer>;
  node: integer;
begin
  tree := TRedBlackTree<integer>.Create;
  // 新增節點
  for node in tree do
    ListBox1.Items.Add(IntToStr(node));
end;

內容解密：

  1. 建立紅黑樹例項：TRedBlackTree<integer>.Create用於建立一個整數型別的紅黑樹。
  2. 新增節點：雖然程式碼中未明確展示新增節點的過程，但在實際應用中，我們會透過Add方法向樹中新增節點。
  3. 中序遍歷：for node in tree實作了對紅黑樹的中序遍歷，遍歷結果按升序排列。

廣度優先遍歷

廣度優先遍歷（Breadth-First Traversal）則是按照層級順序存取節點。雖然Spring框架未直接提供廣度優先遍歷的實作，但我們可以透過使用佇列（Queue）來實作。

程式碼範例：

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 '
      else begin
        s := s + IntToStr(node.Key) + IfThen(node.Color = Black, 'b ', 'r ');
        q2.Enqueue(node.Left);
        q2.Enqueue(node.Right);
      end;
    end;
    ListBox1.Items.Add(s);
    q := q2;
  end;
end;

內容解密：

  1. 建立佇列：使用TCollections.CreateQueue建立兩個佇列q和q2，用於存放當前層級和下一層級的節點。
  2. 根節點入佇列：將紅黑樹的根節點加入初始佇列q。
  3. 迴圈處理佇列：透過雙層迴圈實作廣度優先遍歷，外層迴圈處理當前層級的所有節點，內層迴圈則將下一層級的節點加入q2。
  4. 輸出結果：每一層級的節點資訊被新增到ListBox1中，顯示節點的值、顏色等資訊。

紅黑樹的操作複雜度

紅黑樹的各項操作具有對數時間複雜度，這使得它在需要頻繁插入、刪除和查詢操作的場景下表現出色。

  • 存取：O(log n)
  • 搜尋：O(log n)
  • 插入：O(log n)
  • 刪除：O(log n)
玄貓 BlackCat

玄貓 BlackCat

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