圖檔來自 Pexels
二叉樹
滿足以下兩個條件的樹就是二叉樹：
- 本身是有序樹（若将樹中每個結點的各子樹看成是從左到右有次序的(即不能互換），則稱該樹為有序樹(Ordered Tree)）。
- 樹中包含的各個節點的度不能超過 2，即隻能是 0、1 或者 2。
簡單地了解，二叉樹（Binary tree）是每個節點最多隻有兩個分支（即不存在分支度大于 2 的節點）的樹結構。通常分支被稱作“左子樹”或“右子樹”。
二叉查找樹
要了解紅黑樹之前，免不了先看下二叉查找樹是什麼。
維基百科上的定義：二叉查找樹（英語：Binary Search Tree），也稱為二叉搜尋樹、有序二叉樹（ordered binary tree）或排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹。
若任意節點的左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；若任意節點的右子樹不空，則右子樹上所有節點的值均大于或等于它的根節點的值；任意節點的左、右子樹也分别為二叉查找樹。
圖示了解：
上圖為查找值為29的節點，有以下步驟：
- 檢視根節點 41。
- 因為 41>29，是以檢視 41 的左孩子 20。
- 因為 20<29，是以檢視 20 的右孩子 29，發現其正好是要檢視的節點。
退化
二叉查找樹有個非常嚴重的問題，如果資料的插入是從大到小插入的，或者是從小到大插入的話，會導緻二叉查找樹退化成單連結清單的形式，俗稱
瘸子
。
**左瘸子：**例如，插入資料依次為 {5,4,3,2,1}（從大到小），則如下圖所示：
**右瘸子：**例如，插入資料依次為{1,2,3,4,5}（從小到大），則如下圖所示：
為了解決該問題，出現了一些解決方法，即平衡，能夠使得樹趨向平衡，這種自平衡的樹叫做平衡樹。
平衡樹
平衡樹（Balance Tree，BT）指的是，任意節點的子樹的高度差都小于等于 1。
常見的符合平衡樹的有 AVL 樹（二叉平衡搜尋樹），B 樹（多路平衡搜尋樹，2-3 樹，2-3-4 樹中的一種），紅黑樹等。
AVL 樹
AVL 樹（由發明者 Adelson-Velsky 和 Landis 的首字母縮寫命名），是指任意節點的兩個子樹的高度差不超過 1 的平衡樹。又稱自平衡二叉搜尋樹。
AVL 樹能解決上文二叉查找樹中的右瘸子問題，例如，插入資料依次為 {1,2,3,4,5}（從小到大），則如下圖所示：
AVL 樹會對不符合高度差的結構進行調整，進而使得二叉樹趨向平衡
2-3 樹
2-3 樹，是指每個具有子節點的節點（内部節點，internal node）要麼有兩個子節點和一個資料元素，要麼有三個子節點和兩個資料元素的自平衡的樹，它的所有葉子節點都具有相同的高度。
簡單點講，2-3 樹的非葉子節點都具有兩個分叉或者三個分叉，是以，稱作 2 叉-3 叉樹更容易了解。
另外一種說法，具有兩個子節點和一個資料元素的節點又稱作 2 節點，具有三個子節點和兩個資料元素的節點又稱作 3 節點，是以，整顆樹叫做 2-3 樹。
所有葉子點都在樹的同一層，一樣高：
- 性質 1：滿足二叉搜尋樹的性質。
- 性質 2：節點可以存放一個或兩個元素。
- 性質 3：每個節點有兩個或三個子節點。
建立 2-3 樹的規則
插入操作如下：
向 2-節點中插入元素：
向一顆隻含有一個 3-節點的樹中插入元素：
2-3-4 樹
含義如下：
- **2 節點：**包含兩個子節點和一個資料元素。
- **3 節點：**包含三個子節點和一個資料元素。
- **4 節點：**包含四個子節點和一個資料元素。
2-3-4 樹，它的每個非葉子節點，要麼是 2 節點，要麼是 3 節點，要麼是 4 節點，且可以自平衡，是以稱作 2-3-4 樹。
規則如下：
- **規則 1：**加入新節點時，不會往空的位置添加節點，而是添加到最後一個葉子節點上。
- **規則 2：**四節點可以被分解三個 2-節點組成的樹，并且分解後新樹的根節點需要向上和父節點融合。
插入操作
原本的 2-3-4 樹，如下圖：
對于上圖的 2-3-4 樹，插入一個節點 17，由于規則 1，節點 17 不會加入節點 [16,18,20] 的子樹，而是與該節點融合。
由于規則 2，節點 [16,17,18,20] 是一個 4 節點，将該節點進行拆解成新的樹，将 18 作為子樹的根節點進行拆分。
此時樹暫時失去了平衡，我們需要将拆分後的子樹的根節點向上進行融合。
同理可得，由于規則 2，節點 [6,10,14,18] 是一個 4 節點，将該節點進行拆解成新的樹，将 14 作為子樹的根節點進行拆分，完成了 2-3-4 樹的建構。
總結了下遊戲賬号買賣地圖插入節點的過程，無非也就為了符合兩條規則，那麼，2-3 樹，2-3-4 樹都有了，那是不是也有 2-3-4-5 樹，2-3-4-5--...-n 樹的存在呢？
事實上是有的，世人把這一類樹稱為一個名字：B 樹。
B 樹
B 樹，表示的是一類樹，它允許一個節點可以有多于兩個子節點，同時，也是自平衡的，葉子節點的高度都是相同的。
是以，為了更好地區分一顆 B 樹到底屬于哪一類樹，我們給它一個新的屬性：度（Degree）：一個節點能有多少箭頭指向其他節點。
具有度為 3 的 B 樹，表示一個節點最多有三個子節點，也就是 2-3 樹的定義。具有度為 4 的 B 樹，表示一個節點最多有四個子節點，也就是 2-3-4 樹的定義。
圖為 4 的 B 樹的示例圖：
紅黑樹
R-B Tree，全稱是 Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。
紅黑樹的每個節點上都有存儲位表示節點的顔色，可以是紅（Red）或黑（Black）。
如何了解紅黑樹
一個經典的紅黑樹，如下圖所示（省略了葉子節點都是黑色的 NIL 節點）：
如第二張圖所示，将該紅黑樹與上文講到的 2-3-4 樹對比，是否發現，紅黑樹就是一個 2-3-4 樹：
- 每個節點或者是黑色，或者是紅色。
- 根節點是黑色。
- 每個葉子節點（NIL）是黑色。注意：這裡葉子節點，是指為空（NIL 或NULL）的葉子節點！
-
如果一個節點是紅色的，則它的子節點必須是黑色的。由于紅黑樹的每個節點都是由 2-3-4 樹轉化而來的，進而紅色節點不能連續兩個出現，不然會出現 4 節點的情況，導緻違反了規則 2。
而且紅黑樹的每一個黑節點都是 3 節點中的最中間的那個值，或者是 2 節點中其中一個值。
- 從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。
**原因：**紅黑樹這些黑色節點在 2-3-4 樹中代表的是由 1 節點的一個 2-3-4 樹，而 2-3-4 樹是同一個子樹的深度是相同的，平衡的，是以從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。
如下圖所示，藍色代表是黑色節點：
注意如下幾點：
- 特性（3）中的葉子節點，是隻為空（NIL 或 null）的節點。
- 特性（5），確定沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。
- 紅黑樹雖然本質上是一棵二叉查找樹，但它在二叉查找樹的基礎上增加了着色和相關的性質使得紅黑樹相對平衡，進而保證了紅黑樹的查找、插入、删除的時間複雜度最壞為 O(log n)。
由上面的例子所示，我們隻要把紅黑樹當做是 2-3-4 樹來處理，并且對應的顔色進行改變或者進行左旋右旋的操作，即可達到使得紅黑樹平衡的目标。
如何保持紅黑樹的結構
當我們插入一個新的節點的時候，如何保證紅黑樹的結構依然能夠符合上面的五個特性呢？
樹的旋轉分為左旋和右旋，下面借助圖來介紹一下左旋和右旋這兩種操作。
①左旋
原本的狀态：
過程圖：
結束圖：
如上圖所示，當在某個目标結點 E 上，做左旋操作時，我們假設它的右孩子 S 不是 NIL。
左旋以 S 到 E 之間的鍊為“支軸”進行，它使 S 成為該子樹的新根，而 S 的左孩子則成為 E 的右孩子。
②右旋
原先狀态圖：
同左旋類似，當在某個目标結點 S 上，做右旋操作時，我們假設它的右孩子 S 不是 NIL。