近来闲来无事。。。难题不会做，简单题不想做。。。
又不能颓废，于是就去学各种各样的平衡树
故在此对各种平衡树做一些比较(不太常见的， Treap这样烂大街的就不比了)
二次联通门 : 数组splay ------ luogu P3369 【模板】普通平衡树（Treap/SBT）
二次联通门 : 替罪羊树 ------ luogu P3369 【模板】普通平衡树（Treap/SBT）
二次联通门 : 红黑树 ------ luogu P3369 【模板】普通平衡树（Treap/SBT）
评测地址为洛谷大牛分站， 手动函数O2优化，代码均为自己手写，且按我平时代码风格
时间：
红黑树:
数组splay
替罪羊树
α=0.63
α=0.75
α=0.55
可以明显发现红黑树比其他的平衡树都要快， 而且快不少 (开了O2优化的情况下)
代码长度的话，可能是写法问题，我的红黑树竟然比数组的splay要短。。。。再加上我个人的代码风格喜欢把代码写得很长。。
那么红黑树其实也不一定就是不可写的
原文：http://www.cnblogs.com/ZlycerQan/p/7223003.html