紅黑樹和B-tree，是BST（二叉搜索樹）里運(yùn)用較多的兩種樹，

BST category

• AVL tree
• 2-3 tree
• 2-3-4 tree
• B-trees
• Red-Black tree
• skip list
• treap

前言：red-black tree（紅黑樹）由于其存在的 color flips 和 rotation 兩種操作，且case較多 ，因此不建議記住它每種case對應(yīng)的操作，一般步驟是按照 B-tree、2-3-4 tree、red-black tree的步驟講述，將 red-black tree 看成 2-3-4 tree 的等距二叉樹版本，其中的 insert 與 delete 操作就能對照來看。

Usage

• C++: std::map / std::set
• Java: TreeMap / TreeSet
• Haskell: Data.Map

BST

Balanced Search Tree

AVL tree

AVL tree is a self-balancing Binary Search Tree(BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

• AVL 樹是在普通BST的基礎(chǔ)上增加了子樹的高度限制，以保證在查找過程中，不會出現(xiàn)斜樹的情況
• 時(shí)間復(fù)雜度則為 O(logn)

B-trees

2-3-4 tree

2-3-4 tree 是B-Trees的一種，節(jié)點(diǎn)內(nèi)的keys的個(gè)數(shù)是 b-1 到 2b-1 即：1-3個(gè)，節(jié)點(diǎn)有2,3或4個(gè)孩子

Time complexity

以下分析 B Tree的 search、insert、delete complexity。

• search complexity

  
  
  search_complexity

這里解釋下 height 是 O(log_b n)，從B tree 的 max height出發(fā)考慮：1+2(b-1)+2b(b-1)+... = n 可推出。

• insert complexity

  
  
  insert_complexity

• delete complexity

  
  
  delete_complexity

從上述可以看出對于 2-3-4 tree 而言，其 time complexity 總是為：O(log n)，克服了普通 BST 因?yàn)?height 導(dǎo)致在增刪改查的時(shí)候發(fā)揮不穩(wěn)定的特點(diǎn)。

B+ Tree

B+ 樹是在B 樹基礎(chǔ)上發(fā)展的數(shù)據(jù)結(jié)構(gòu)，MySQL普遍使用B+樹實(shí)現(xiàn)其索引結(jié)構(gòu)。

• 經(jīng)典的B+樹與B 樹相比，一個(gè)m階的B+樹有k個(gè)子樹的中間節(jié)點(diǎn)包含k個(gè)元素（不同于B樹中的k-1個(gè)元素），每個(gè)元素不保存value，只用來索引，所有的(key,value)都保存在葉子節(jié)點(diǎn)中
• 在經(jīng)典的B+樹基礎(chǔ)上，對葉子節(jié)點(diǎn)本身進(jìn)行指針的順序鏈接，以加快范圍的查詢

優(yōu)點(diǎn)： 由于非葉子節(jié)點(diǎn)中不承載數(shù)據(jù)，因此非葉子節(jié)點(diǎn)的每一層可以容納更多的元素，降低了樹的高度，減少了磁盤I/O的次數(shù)。并且因?yàn)槿~子節(jié)點(diǎn)之間存在順序鏈接的指針，遍歷數(shù)據(jù)也會很簡單。

Red-Black tree

紅黑樹是在查找數(shù)據(jù)結(jié)構(gòu)里運(yùn)用較多，典型的特點(diǎn)是在BST的基礎(chǔ)上增加了樹的平衡特性，即通過保證Black-height（路徑上黑色節(jié)點(diǎn)的數(shù)目）相等，來保證樹高<=2log(n+1)

red-black tree

• 證明：h <= 2log(n+1)
  （將紅黑樹的紅色節(jié)點(diǎn)合并到父親黑色節(jié)點(diǎn)，得到2-3-4樹，利用2-3-4樹葉子節(jié)點(diǎn)與樹高的關(guān)系推出來原樹高的范圍）,這一推論由property3,4得出，也是決定R_B tree得到廣泛運(yùn)用的關(guān)鍵所在。

Insert&Delete

對R-B tree的插入與刪除，需要調(diào)整樹結(jié)構(gòu)。整體分為三大步驟：

• 找到插入位置，著色為紅色；
• 對父節(jié)點(diǎn)與祖父節(jié)點(diǎn)重新著色；
• 對子樹進(jìn)行旋轉(zhuǎn)調(diào)整；

偽代碼

pseudocode.png

3 cases

• case1

  
  
  case1.png

• case2 ---> case3

  
  
  case2.png

• case3

  
  
  case3.png

time complexity

各種時(shí)間復(fù)雜度同 2-3-4 tree 為：O(log n)

總結(jié)

summary

Refer:

• cs166_stanford
• 6.046J_mit

更多有關(guān)算法方面的內(nèi)容可參考本人博客：老香椿（https://laoxiangchun.cn/tags/Algorithm/）