資料結構&演算法筆記
  • Introduction
  • 1. Data Structure
  • 1.1 Stack
  • 1.1.1 Stack: Revert String
  • 1.1.2 Stack: Brackets Matching
  • 1.1.3 Stack: Reverse Polish Notation
  • 1.1.4 Stack: Calculattion for Reverse Polish Notation
  • 1.2 Queue
  • 1.2.1 Priority Queue
  • 1.3 Linked List
  • 1.3.1 Linked List - Reorder Function
  • 1.3.2 Ordered Linked List
  • 1.4 Tree
  • 1.4.1 Binary Search Tree
  • 1.4.2 Heap Tree
  • 1.4.3 Red-Black Tree
  • 1.4.3.1 RB Tree Insertion
  • 1.4.3.2 RB Tree Insertion Implementation
  • 1.4.3.3 RB Tree Delete
  • 1.4.3.4 RB Tree Delete Implementation
  • 1.4.4 B-Tree
  • 2. Algorithm
  • 2.1 Sort
  • 2.1.1 Bubble Sort
  • 2.1.2 Selection Sort
  • 2.1.3 Insertion Sort
  • 2.1.4 Merge Sort
  • 2.1.5 Quick Sort
  • 2.1.6 Merge Sort v.s. Quick Sort
  • 2.2 Search
  • 2.2.1 Binary Search
  • 2.3 Dynamic Programming
  • 2.3.1 Fibonacci Series
  • 2.3.2 Find Longest Common Suffix
  • X. Time Complexity Cheat Sheet
Powered by GitBook
On this page

Was this helpful?

1.4.3.1 RB Tree Insertion

Previous1.4.3 Red-Black TreeNext1.4.3.2 RB Tree Insertion Implementation

Last updated 5 years ago

Was this helpful?

紅黑樹的插入演算法

紅黑樹的插入, 前面的部分跟二元搜尋樹一樣, 就是從根節點向下尋找節點要插入的位置, 找到後插入節點; 插入節點後, 多了這樣的一個操作: 檢查樹是否平衡, 如果不平衡, 就要做修復, 使樹重新變得平衡.

在開始討論插入演算法之前, 先釐清節點之間的關係與簡稱:

插入新的節點, 通常會設置這個節點為紅色, 因為這樣可以降低違反紅黑規則的機率, 而插入節點後, 會有以下幾點的情境出現:

  1. 若插入的是根節點, 那麼違反規則2(根總是黑色的), 那就直接把節點改成黑色的

  2. 若插入節點的P節點是黑色的, 即符合規則, 就什麼都不做

若插入節點的P節點是紅色的, 且U節點也是紅色的, 那麼: 將G節點變紅, 而P與U節點變黑(遵守規則5), 然後設置G節點為current node, 並且重新開始調整

若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的左子節點, 而P節點是G節點的左子節點, 那麼: 把P節點變成黑色, G節點變為紅色, 然後對G節點做右旋的動作, 最後重新開始調整

若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的右子節點, 而P節點是G節點的右子節點, 那麼: 把P節點變成黑色, G節點變為紅色, 然後對G節點做左旋的動作, 最後重新開始調整

若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的右子節點, 而P節點是G節點的左子節點, 那麼: 把當前節點的P節點作為新的當前節點, 對新的當前節點進行左旋, 並且重新開始調整

若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的左子節點, 而P節點是G節點的右子節點, 那麼: 把當前節點的P節點作為新的當前節點, 對新的當前節點進行右旋, 最後重新開始調整