红黑树和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
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 是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)
- 证明：h <= 2log(n+1)
（将红黑树的红色节点合并到父亲黑色节点，得到2-3-4树，利用2-3-4树叶子节点与树高的关系推出来原树高的范围）,这一推论由property3,4得出，也是决定R_B tree得到广泛运用的关键所在。
Insert&Delete
对R-B tree的插入与删除，需要调整树结构。整体分为三大步骤：
- 找到插入位置，着色为红色；
- 对父节点与祖父节点重新着色；
- 对子树进行旋转调整；
伪代码
3 cases
-
case1
case1.png -
case2 ---> case3
case2.png -
case3
case3.png
time complexity
各种时间复杂度同 2-3-4 tree 为：O(log n)
总结
Refer:
更多有关算法方面的内容可参考本人博客：老香椿（https://laoxiangchun.cn/tags/Algorithm/）
