Java 中的紅黑樹

1. 紅黑樹
2. 確定紅黑樹的平衡
3. 紅黑樹中的子樹旋轉
4. 搜尋演算法：紅黑樹
5. 插入：紅黑樹 Java
6. 概括
7. 參考

本教程對最著名的資料結構技術之一紅黑樹進行了最新和深入的檢查。此外，我們還針對我們認為你必須理解的基本元素執行了一些 Java 演示程式。

儘管本文結合了紅黑樹的所有基本特徵，但我們的目標是使其儘可能簡單。但是，我們也知道初學者理解這個主題可能具有挑戰性。

紅黑樹

紅黑樹是電腦科學中獨特的二叉搜尋樹，特別是在資料結構和演算法方面。我們使用它來對複雜問題陳述的可比較資料位進行分組。

下表包含有關紅黑樹的一般資訊。

圖 1：典型的紅黑樹（演示示例）。

紅黑樹的性質

紅黑樹必須滿足以下條件。

1. 每個節點都有紅色或黑色。
2. 我們將 NIL (= NONE)- 孩子`` 稱為樹的葉子。
3. 每個 NIL-leaf 都是黑色的。
4. 樹的根也必須是黑色的。
5. 假設一個節點是紅色的，那麼這個節點的兩個孩子都必須是黑色的。
6. 從節點到後代葉子的所有路徑必須包含相同數量的每個節點的黑色節點。

紅黑樹的高度定義

圖 2：樹的黑色高度。

樹中節點的屬性

樹節點應包含以下屬性。

1. 顏色
2. 鍵
3. 左孩子
4. 右孩子
5. 父節點（不包括根節點）

以下是我們稍後將如何處理 Java 程式中的節點。

// class node
public class BlackRedTreeNode {
  int Ndata; // The data of the node
  BlackRedTreeNode P; // parent
  BlackRedTreeNode L; // Left
  BlackRedTreeNode R; // Right
  int Nclr; // Color of the node
} // end of class

確定紅黑樹的平衡

我們將假設使用一種資料結構演算法的方法來解決如何平衡紅黑樹結構的問題陳述。

節點顏色限制確保從根到葉的任何簡單路徑不超過任何其他此類路徑的兩倍。它增加了紅黑樹的自平衡能力。

1. 節點高度：Hn
2. T 作為樹

你可以看到通往葉子的最長路徑的邊緣。

3. node-x 的黑色高度：

bh(x) 表示黑色節點的數量，包括從 x 到葉子的路徑上的 nil [T]，但不包括 x。

4. 無葉子：

樹中的這些屬性僅用於計數（屬性編號 6）。

5. 引理：具有 n 個節點的紅黑樹的高度：
   
   
   $$
   ≤ 2 log (n+1)
   $$
   
   

6. 證明：以任意節點 x 為根的子樹至少包含：
   
   
   $$
   2^bh(x) -1
   $$
   
   

因此，黑色高度為 bh(x) 的最小子樹和完整樹具有 n 個內部節點：


$$
2^bh(root[T]) -1 ≤ n
$$

紅黑樹中的子樹旋轉

旋轉是為自平衡二叉搜尋樹設計的獨特操作，需要 O(1) 才能完成。此外，相同的旋轉有助於保持鍵的有序遍歷。

此外，在旋轉操作期間交換子樹節點的位置。當其他操作，如插入和刪除，違反了紅黑樹的屬性時，會執行旋轉操作來恢復它們。

旋轉分為兩種：

被評估的節點的阿姨會影響進行旋轉或顏色更改（當前節點）的選擇。如果節點有黑阿姨，我們就輪換。

如果節點有一個紅色阿姨，我們反轉顏色。我們必須在旋轉樹後對其進行顏色修復。

在這些操作之後，樹應該被終止，如下所示。

右旋轉的示例 Java 程式碼：

// function
// n as node
// P as Parent
// R as Right
// L as Left
// LC as LeftChild
private void RightRotation(TreeNode n) {
  TreeNode paPrent = n.P;
  TreeNode LC = n.L;
  n.L = LC.R;
  if (LC.R != null) {
    LC.R.P = n;
  }
  LC.right = n;
  n.P = LC;
  Replace(P, n, LC);
} // end of function

Java 中的左旋轉示例：

// function left rotation
private void LeftRotation(TreeNode n) {
  TreeNode P = n.P;
  TreeNode Rc = n.R;
  n.R = Rc.L;
  if (Rc.L != null) {
    Rc.left.P = n;
  }
  Rc.left = n;
  n.P = Rc;
  replace(P, n, Rc);
} // end of function

搜尋演算法：紅黑樹

搜尋的工作方式與任何二叉搜尋樹的工作方式相同。我們首先將搜尋鍵與根進行比較。

如果你的搜尋關鍵字較小，則在左子樹中繼續搜尋；如果搜尋關鍵字更重要，則在右子樹中繼續搜尋。

我們重複這個過程，直到找到我們想要的節點。換句話說，直到我們到達一個零葉點。

假設我們到達一個零葉子，這意味著我們正在尋找的鍵不在樹中。

程式碼：搜尋

// Sn as Search Nodes
// k as Key
// n as node
// r as Right
// d as Data of the data
// L as left
// Function starts here
public TreeNode Sn(int k) {
  TreeNode n = r;
  // determine the search by applying while loop
  //  loop starts
  while (n != null) {
    // checking the key
    if (k == n.d) {
      return n;
    } else if (k < n.d) {
      n = n.L;
    } else {
      n = n.R;
    } // condition ends
  } // loop ends
  return null;
} // Function ends here

插入：紅黑樹 Java

下面的程式演示了一個函式，我們可以使用它在黑紅樹中插入節點。儘管就資料結構的觀點而言它遵循正確的順序，但完整的執行將因你的方法而異。

下面的程式碼對於初學者來說還是足夠了，尤其是對於初學者。

程式碼：插入

// iN as insertion node
//  k as key of the tree
// r as root of the node
// R as right node
// L as left node
// d as data
// p as parent
public void iN(int k) {
  TreeNode n = r;
  TreeNode P = null;
  // Swaping the nodes
  while (n != null) {
    p = n;
    if (k < n.d) {
      n = n.L;
    } else if (k > n.d) {
      n = n.R;
    } else {
      throw new IllegalArgumentException(
          "The Binary Search Tree  already has a node with this key: " + k);
    }
  }
  // A rough example of how you can apporach insertion of the new node in the tree using BST
  TreeNode newN = new TreeNode(k);
  newN.clr = red;
  if (p == null) {
    r = newN;
  } else if (k < p.d) {
    p.L = newN;
  } else {
    pt.R = newN;
  }
  newN.p = p;
  // Fixing the tree after the insetion
  fixingTreeAfterInsertion(newN);
}

紅黑樹的應用

在 Java 集合庫中，紅黑樹已用於 TreeSet、TreeMap 和 Hashmap。它也用於 Linux 核心：Completely Fair Scheduler、File、Memory 和 Mapping。

此外，Linux 在 mmap 和 munmap 操作中使用它。此外，它們還用於降低 K-mean 聚類演算法的時間複雜度。

此外，MySQL 為表搜尋實現了紅黑樹。我們為什麼用它？

紅黑樹確保 O(log(n)) 的插入和刪除時間。它們是穩定的搜尋樹，因此，它們始終保持對數高度 (n)。

考慮將整數 1,2,3,4,5 放入二叉樹中。它將 1 設為根，所有後續元素將向右移動，形成一個有效的連結串列（並且每個操作都需要 O(n) 時間）。

即使平均時間複雜度相同，如果我們考慮最壞的情況，紅黑樹在時間複雜度方面超過二叉搜尋樹。

概括

本教程教你什麼是紅黑樹、控制它的規則以及如何評估這些規則。我們還粗略地演示瞭如何使用 Java 程式來處理它。

本教程中的一些重要內容：

一、紅黑樹簡介
2. 典型的紅黑樹：演示示例
3. 樹中節點的屬性
4. 利用資料結構確定紅黑樹的平衡
5. 紅黑樹的子樹旋轉
6. 右旋轉
7. 左旋轉
8. 旋轉、搜尋和插入的演示程式碼示例

參考

1. 紅黑樹-維基百科
2. 開原始碼-GitHub
3. 二叉搜尋樹（附 Java 程式碼）
4. 資料結構演算法解析：紅黑樹