red-black Tree

Red-Black trees provide a slightly relaxed balancing condition, so the tree can be a little more imbalanced than AVL trees.  The benefit is that the insertion and removal algorithms are faster.  The drawback is that look-up(i.e., a find())  is a little slower.   However, since a look-up is O(logN)in both cases, the slight constant increase in this operation is usually unnoticeable, while the insert() and remove() speed improvements are clear.

红黑树是一种稍微没有那么balanced的balanced Tree， 查询速度稍稍慢了一点点，但是插入和删除都超级快。

资料：https://www.cnblogs.com/CarpenterLee/p/5503882.html

https://www.cnblogs.com/skywang12345/p/3245399.html

插播AVL TREE:

                                             1

AVL delete 需要使用rotation

Insertion:

AVL Tree 比 red-black tree更balanced，但是需要更多的rotations during insertion & deletion, 所以如果需要经常删除，添加  还是Red-black tree比较好。

Root and Leafs 都是blacks.