# 關於紅黑樹

這篇文章是繼閱讀 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)後，想補完這篇文章的不足並嘗試用 C 來實作紅黑樹。寫完後會貢獻回原本的文章。

在 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)介紹了左傾紅黑樹，但是 Eddie Kohler 教授卻[提出](https://read.seas.harvard.edu/~kohler/notes/llrb.html)左傾紅黑樹是不好的，故在撰寫這篇文章時，會針對傳統紅黑樹和左傾紅黑樹建構測試程式，並且包含 top-down 和 bottom-up 的方式均實測，來看看效能如何。

## 紅黑樹簡介

紅黑樹是一種能自己保持平衡的二元搜尋樹。其需保持以下特性：
- 每一個節點不是紅色就是黑色
- 從根節點到每一個終端節點 (leaf) 的路徑上，所經過的黑色節點數一樣多
- 紅色節點的子點必為黑色節點

它確保搜尋、插入、刪除節點的時間複雜度均為 $O(\log n)$ ，在 Linux kernel 及各種應用程式廣範被使用。

此外紅黑樹與 2-3-4 樹有類比的關係。任一棵紅黑樹可以類比成對應的 2-3-4 樹，同樣的 2-3-4 樹也可以類比成 2-3-4 樹。


這張圖取自[維基百科](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree)，說明紅黑樹和 2-3-4 樹該如何對應。

網路上有很多說明都是直接以紅黑樹的角度來講解插入和移除的操作，但是我發現若從 2-3-4 樹來看插入和移除的操作，其實更容易理解。

## 紅黑樹操作

這裡要介紹紅黑樹新增、刪除這二種操作。這二種操作均有 top-down 和 bottom-up 方式，都會在這裡記錄。

Top-Down 操作參考資料:
- <https://azrael.digipen.edu/~mmead/www/Courses/CS280/Trees-2-3-4-delete.html>
- <https://azrael.digipen.edu/~mmead/www/Courses/CS280/Trees-Mapping2-3-4IntoRB.html>

Bottom-Up 操作參考 Linux 核心 rbtree.c

### 插入節點

#### Top-Down 作法

Top Down 在 2-3-4 樹插入節點的作法是，在往下走訪的過程中，遇到 4-節點，就分割結點，使得在最下層找到要插入節點時，不會是 4-節點，插入後就不必再往上修正。

而對應到紅黑樹中，則是往下走訪過程中，遇到黑節點有二個紅色子點時，就進行顏色調整，並適時進行旋轉，其等價於在 2-3-4 樹上分割節點。到最後頁節點要插入時，最多只需要再旋轉就好，不必再向上修正。

#### Bottom-Up 作法

直接透過一般二元搜尋樹的作法，插入新節點，讓新節點為紅節點，之後再向上修正。

### 刪除節點

#### Top-Down 作法

#### Bottom-Up 作法