Red-Black tree and B-tree

红黑树和B-tree，是BST（二叉搜索树）里运用较多的两种树，

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对应的操作，一般步骤是按照 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的基础上增加了子树的高度限制，以保证在查找过程中，不会出现斜树的情况
• 时间复杂度则为 O(logn)

B-trees

2-3-4 tree

2-3-4 tree 是B-Trees的一种，节点内的keys的个数是 b-1 到 2b-1 即：1-3个，节点有2,3或4个孩子

Time complexity

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

• search complexity

  
  search_complexity

这里解释下 height 是 O(log_b n)，从B tree 的 max height出发考虑：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 因为 height 导致在增删改查的时候发挥不稳定的特点。

B+ Tree

B+ 树是在B 树基础上发展的数据结构，MySQL普遍使用B+树实现其索引结构。

• 经典的B+树与B 树相比，一个m阶的B+树有k个子树的中间节点包含k个元素（不同于B树中的k-1个元素），每个元素不保存value，只用来索引，所有的(key,value)都保存在叶子节点中
• 在经典的B+树基础上，对叶子节点本身进行指针的顺序链接，以加快范围的查询

优点： 由于非叶子节点中不承载数据，因此非叶子节点的每一层可以容纳更多的元素，降低了树的高度，减少了磁盘I/O的次数。并且因为叶子节点之间存在顺序链接的指针，遍历数据也会很简单。

Red-Black tree

红黑树是在查找数据结构里运用较多，典型的特点是在BST的基础上增加了树的平衡特性，即通过保证Black-height（路径上黑色节点的数目）相等，来保证树高<=2log(n+1)

red-black tree

• 证明：h <= 2log(n+1)
  （将红黑树的红色节点合并到父亲黑色节点，得到2-3-4树，利用2-3-4树叶子节点与树高的关系推出来原树高的范围）,这一推论由property3,4得出，也是决定R_B tree得到广泛运用的关键所在。

Insert&Delete

对R-B tree的插入与删除，需要调整树结构。整体分为三大步骤：

• 找到插入位置，着色为红色；
• 对父节点与祖父节点重新着色；
• 对子树进行旋转调整；

伪代码

pseudocode.png

3 cases

• case1

  
  case1.png

• case2 ---> case3

  
  case2.png

• case3

  
  case3.png

time complexity

各种时间复杂度同 2-3-4 tree 为：O(log n)

总结

summary

Refer:

• cs166_stanford
• 6.046J_mit