Red-black tree

1.Insert into a 2-3 tree

2.2-3tree和rbtree的等价关系及转换

3.rbtree的性质

1. Each node is either red or black.
2. The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
3. All leaves (NIL) are black.
4. If a node is red, then both its children are black.
5. Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

4. rbtree的基本操作

插入一个新节点的逻辑链如下图，有红，绿，蓝三条主线，在代码中分别写成三个if语句判断

// left rotate 右边节点红色，左边节点黑色
if (isRed(node.right) && !isRed(node.left)) {
    node = leftRotate(node);
}

// right rotate
if (isRed(node.left) && isRed(node.left.left)) {
    node = rightRotate(node);
}

// flip color
if (isRed(node.left) && isRed(node.right)) {
    flipColors(node);
}

5.可视化

手绘简单测试数据：

蓝线逻辑：6,2,8
红线逻辑：6,2,3
绿线逻辑：6,3,2

• https://www.cs.usfca.edu/~galles/visualization/RedBlack.html进行可视化，但是这个树是右倾红黑(?也许。没看源码)，所以有些结果可能不一样，如8，6

• http://inst.eecs.berkeley.edu/~cs61b/fa17/materials/demos/ll-red-black-demo.html，左倾红黑，但中间变化过程不明显，而且可以加入相等节点而不是更新

6.性能比较

bst: 适用于完全随机的数据

rbtree: 增删占优势，统计性能(crud)占优势，牺牲平衡性，有可能退化成链表

avltree: 查询占优势

code

https://github.com/nyannko/leetcode-java/blob/master/src/ds/rbtree/RBTree.java