請啟用 Javascript 查看內容

JavaScript 學演算法（十七）- 紅黑樹（中）：新增操作

 ·  ☕ 6 分鐘

這週是六角鼠年鐵人賽第二十五週。

上週我們簡單說明了紅黑樹的基本性質與理解 B 樹、2-3-4 樹，接下來，我們來看紅黑樹和 2-3-4 樹的等價關係與新增操作。

  1. 紅黑樹（上）：B 樹、2-3-4 樹
  2. 紅黑樹（中）：新增操作
  3. 紅黑樹（下）：刪除操作
Featured Image

紅黑樹和 2-3-4 樹的等價關係

2-3-4 樹在多數程式語言中實現起來相對困難，因為在樹上的操作涉及大量的特殊情況。而 紅黑樹 是基於它的理論基礎所發明的，實現起來更簡單一些。

因此 紅黑樹本質上就是 2-3-4 樹，所有性質都可以從 2-3-4樹 來理解。

1. 黑色節點

黑色節點，其實就是 2-3-4 樹的 2-節點，為一個中位數。。

graph TB;
  N[_ 40 _];
  
  A((40)) --- n1 & n2;

  class A black;
  class n1,n2 transparent;
  
  classDef black fill:black,stroke:black,color:white;
  classDef transparent fill:transparent,stroke:transparent,color:transparent;

2. 紅色節點

黑色節點的子樹如果是紅色節點，表示彼此融合的意思，其實就是 2-3-4 樹的 3-節點、4-節點。

3-節點：

graph TB;
  N[30 40 _];
  A((40)) --- B((30)) & n1;
  N2[_ 40 50 ];
  AA((40)) --- n2 & BB((50));
  
  class A,AA black;
  class B,BB red;
  class n1,n2 transparent;
  
  classDef black fill:black,stroke:black,color:white;
  classDef red fill:red,stroke:red,color:white;
  classDef transparent fill:transparent,stroke:transparent,color:transparent;

4-節點：

graph TB;
  N[30 40 50];
  A((40)) --- B((30)) & C((50));

  class A black;
  class B,C red;
  
  classDef black fill:black,stroke:black,color:white;
  classDef red fill:red,stroke:red,color:white;

3. 2-3 樹

部分資料會說紅黑樹等價於 2-3 樹（3 階 B 樹），但正確來說，是「左傾紅黑樹」，屬於紅黑樹的變種，這裡不討論。

紅黑樹的新增操作

紅黑樹新增節點後，會檢查樹使否平衡（是否違反紅黑樹性質），若不平衡，會透過「旋轉」和「變色」操作來修正。

1. 保持根節點是黑色的

在 2-3-4 樹插入元素時，都是融合到節點中，因此在紅黑樹中，新增的節點一定的紅色的。

首先，我們再一個空樹中新增一個節點：

graph TB;
  A((N));
  classDef red fill:red,stroke:red,color:white;
  A:::red;

但紅黑樹的性質2：「樹的根節點為黑色」，因此需要將它修正成黑色的：

graph TB;
  A((N));
  classDef black fill:black,stroke:black,color:white;
  A:::black;

2. 2-節點

一個黑色節點無任何子節點，表示它是一個 2-節點。

那麼當我們新增節點，它會變成一個 3-節點，因此不需要做任何修正：

graph TB;

  A((P)) --- B((N)) & n1;
  AA((P)) --- n2 & BB((N));
  
  class A,AA black;
  class B,BB red;
  class n1,n2 transparent;
  
  classDef black fill:black,stroke:black,color:white;
  classDef red fill:red,stroke:red,color:white;
  classDef transparent fill:transparent,stroke:transparent,color:transparent;

3. 3-節點

當我們對一個 3-節點新增節點，它會變成 4-節點，這時紅黑樹可能會違反性質4：「每個紅色節點必須有兩個黑色的子節點（不能有兩個連續的紅色節點）」，因此必須修正它。

舉例來說，黑紅樹表示的 3-節在 2-3-4樹可能長這樣：

graph TB;
  N[30 40 _];

但如果要再插入 20，左邊沒位置。因此要將 30 變成中位數：

graph TB;
  N[_ 30 40 ];

這樣就能插入 20 了：

graph TB;
  N[20 30 40];

接下來，我們來看需要修正的情況，首先來定義節點代號，方便說明：

  • 祖父節點：G
  • 父親節點：P
  • 新增的節點：N

需要修正情況一：

graph TB;
  A((G)) --- B((P)) & n;
  B((P)) --- C((N)) & n1;
  class A black;
  class B,C red;
  class n,n1 transparent;
  
  classDef black fill:black,stroke:black,color:white;
  classDef red fill:red,stroke:red,color:white;
  classDef transparent fill:transparent,stroke:transparent,color:transparent;

需要對 G 執行右旋轉，並將 G 設為紅色、P 設為黑色：

graph TB;
  A((P)) --- B((N)) & C((G));

  class A black;
  class B,C red;
  
  classDef black fill:black,stroke:black,color:white;
  classDef red fill:red,stroke:red,color:white;

如果你對旋轉操作不熟悉的話，可以先參考我的上一篇文章：AVL-Tree。

需要修正情況二：

graph TB;
  A((G)) --- B((P)) & n;
  B((P)) --- n1 & C((N));
  
  AA((G)) --- BB((N)) & nn;
  BB((N)) --- CC((P)) & nn1;
  
  class A,AA black;
  class B,C,BB,CC red;
  class n,n1,nn,nn1 transparent;
  
  classDef black fill:black,stroke:black,color:white;
  classDef red fill:red,stroke:red,color:white;
  classDef transparent fill:transparent,stroke:transparent,color:transparent;

需要先對 P 進行左旋轉，這樣就變成情況一了，再執行相同處理。

情況三、四，基本上就是鏡像情況，先對 P 右旋轉：

graph TB;
  A((G)) --- n & B((P));
  B((P)) --- C((N)) & n1;

  A1((G)) --- n11 & B1((N));
  B1((N)) --- n111 & C1((P));
  
  class A black;
  class B,C red;
  class n,n1 transparent;
  
  class A1 black;
  class B1,C1 red;
  class n11,n111 transparent;
  
  classDef black fill:black,stroke:black,color:white;
  classDef red fill:red,stroke:red,color:white;
  classDef transparent fill:transparent,stroke:transparent,color:transparent;

再對 G 左旋轉，並將 G 設為紅色、N 設為黑色：

graph TB;
  AA((N)) --- BB((G)) & CC((P));
  
  class AA black;
  class BB,CC red;
  
  classDef black fill:black,stroke:black,color:white;
  classDef red fill:red,stroke:red,color:white;

4. 4-節點

如果對一個 4-節點新增節點，也就是會形成一個 5-節點，這時紅黑樹一樣會違反性質4。

graph TB;
  n --> A;
  A((A)) --- B((B)) & C((C));
  B((B)) --- N((N));
  
  class A black;
  class B,C red;
  class N red2;
  class n transparent;
  
  classDef black fill:black,stroke:black,color:black;
  classDef red fill:red,stroke:red,color:red;
  classDef red2 fill:red,stroke:red,color:white;
  classDef transparent fill:transparent,stroke:transparent,color:transparent;

我們會將整棵子樹執行「顏色翻轉 color flip」操作：

graph TB;
  n --> A;
  A((A)) --- B((B)) & C((C));
  B((B)) --- N((N));
  
  class A red;
  class B,C black;
  class N red2;
  class n transparent;
  
  classDef black fill:black,stroke:black,color:black;
  classDef red fill:red,stroke:red,color:red;
  classDef red2 fill:red,stroke:red,color:white;
  classDef transparent fill:transparent,stroke:transparent,color:transparent;

顏色翻轉，其實就是 2-3-4 樹中的拆分與向上融合。

當執行完顏色翻轉後，需要重新檢查黑紅樹是否違反性質。

JavaScript 實作紅黑樹新增操作

1. 本體

顏色：

1
2
3
4

const NodeColor = {
  RED: true,
  BLACK: false,
};

我們使用布林值來定義紅色與黑色。

節點：

1
2
3
4
5
6
7
8
9

class RBTNode {
  constructor(data, parent = null) {
    this.data = data;
    this.parent = parent;
    this.left = null;
    this.right = null;
    this.color = NodeColor.RED;
  }
}
  1. data：儲存資料
  2. parent：父節點
  3. left：左子節點
  4. right：右子節點
  5. color：節點顏色（新增節點一定是紅色的，所以預設紅色）

紅黑樹的節點比普通的二元搜尋樹多了顏色和紀錄父節點屬性，也就是說，它是一個雙向鏈結。

根：

1
2
3
4
5
6

class RedBlackTree {
  constructor() {
    this.root = null;
  }
  // methods
}

2. 旋轉操作

紅黑樹因為多了顏色和父節點，因此旋轉操作還需要更新顏色、父節點。

2.1 右旋轉

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

rightRotation(node) {
  const temp = node.left;
  node.left = temp.right;
  temp.right = node;

  // 更新顏色
  temp.color = node.color;
  node.color = NodeColor.RED;

  // 更新父節點
  this.replaceParent(node, temp);
  temp.parent = node.parent;
  node.parent = temp;
  if (node.left) {
    node.left.parent = node;
  }
}

2.2 左旋轉

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

leftRotation(node) {
  const temp = node.right;
  node.right = temp.left;
  temp.left = node;

  temp.color = node.color;
  node.color = NodeColor.RED;

  this.replaceParent(node, temp);
  temp.parent = node.parent;
  node.parent = temp;
  if (node.right) {
    node.right.parent = node;
  }
}

2.3 輔助方法

替換父節點的指向：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

replaceParent(curNode, newNode) {
  const { parent } = curNode;
  if (!parent) {
    this.root = newNode;
  } else if (curNode === parent.left) {
    parent.left = newNode;
  } else {
    parent.right = newNode;
  }
}
  1. 如果父節點不存在，更新樹的根節點；
  2. 如果是左子樹，更新左子樹；
  3. 若不是，則更新右子樹。

3. 新增操作

基本上與普通二元搜尋樹相同，只是多了父節點的指向與檢查是否平衡。

歸迴版本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

insert(data) {
  const insertHelper = (node) => {
    const curNode = node;
    if (data < curNode.data) {
      if (curNode.left) {
        insertHelper(curNode.left);
      } else {
        curNode.left = new RBTNode(data);
        curNode.left.parent = curNode;
        this.insertFixRBT(curNode.left);
      }
    } else if (data > curNode.data) {
      if (curNode.right) {
        insertHelper(curNode.right);
      } else {
        curNode.right = new RBTNode(data);
        curNode.right.parent = curNode;
        this.insertFixRBT(curNode.right);
      }
    }
  };
  if (!this.root) {
    this.root = new RBTNode(data);
    this.insertFixRBT(this.root);
  } else {
    insertHelper(this.root);
  }
}

迭代版本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

insert(data) {
  if (!this.root) {
    this.root = new RBTNode(data);
    this.insertFixup(this.root);
    return this.root;
  }

  let curNode = this.root;

  while (curNode) {
    if (data < curNode.data) {
      if (curNode.left) {
        curNode = curNode.left;
      } else {
        curNode.left = new RBTNode(data, curNode);
        this.insertFixup(curNode.left);
        break;
      }
    } else if (data > curNode.data) {
      if (curNode.right) {
        curNode = curNode.right;
      } else {
        curNode.right = new Node(data, curNode);
        this.insertFixup(curNode.right);
        break;
      }
    }
  }

  return this.root;
}

4. 新增操作平衡修正

新增節點後，檢查紅黑樹是否符合特性，並修正它。

節點代號，方便說明：

  • 當前節點：N
  • 父親節點：P
  • 祖父節點：G
  • 叔叔節點：U

檢查是否需要修正，修正條件「P 是紅色且 G 存在」：

  • 若 P 為 G 的左子節點：
    • 判斷 U 是否為紅色節點，若是，則執行顏色翻轉。
    • 若不存在，判斷 N 是否為 P 的右子節點：
      • 如果是右子節點，先對 P 執行左旋轉；
    • 對 G 執行右旋轉。
  • 若 P 為 G 的右子節點：
    • 判斷 U 是否為紅色節點，若是，則執行顏色翻轉。
    • 若不存在，判斷 N 是否為 P 的左子節點：
      • 如果是左子節點，先對 P 執行右旋轉；
    • 對 G 執行左旋轉。
  • 以上修正結束，將目前節點設為祖父節點，再次檢查是否需要修正。

修正結束後，記得將根結點設為黑色。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

insertFixup(node) {
  let curNode = node;
  while (this.isRed(curNode.parent) && curNode.parent.parent) {
    const { parent } = curNode;
    const grandparent = parent.parent;

    if (parent === grandparent.left) {
      if (this.isRed(grandparent.right)) {
        this.flipColor(grandparent);
      } else {
        if (curNode === parent.right) {
          this.leftRotation(parent);
        }
        this.rightRotation(grandparent);
      }
    } else {
      if (this.isRed(grandparent.left)) {
        this.flipColor(grandparent);
        curNode = grandparent;
      } else {
        if (curNode === parent.left) {
          this.rightRotation(parent);
        }
        this.leftRotation(grandparent);
      }
    }
    curNode = grandparent;
  }
  this.root.color = NodeColor.BLACK;
}

4.1 輔助方法

判斷節點顏色：

1
2
3

isRed(node) {
  return node ? node.color : false;
}

顏色翻轉：

1
2
3
4
5

flipColor(node) {
  node.color = NodeColor.RED;
  node.left.color = NodeColor.BLACK;
  node.right.color = NodeColor.BLACK;
}

總結

這是我用 Vue.js 製作的，可以很的方便觀察黑紅樹的結構變化：

下週來說明更麻煩的刪除操作。

竹白
作者
竹白
前端筆記

相關內容

文章目錄