c++ pb_ds库，实现 红黑树，Splay

C++ pb_ds库

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

定义一颗红黑树

tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>t;

int 关键字类型

null_type无映射(低版本g++为null_mapped_type)

less<int>从小到大排序

rb_tree_tag 红黑树（splay_tree_tag）

tree_order_statistics_node_update结点更新

插入t.insert();

删除t.erase();

Rank:t.order_of_key();

第K值:t.find_by_order();

前驱:t.lower_bound();

后继t.upper_bound();

其他的注意一些细节问题就行，

比如说不支持相同关键字的插入可以用double代替int插入啥的或者再插入一个时间戳啥的

c++ pb_ds库，实现 红黑树，Splay

原文：http://www.cnblogs.com/henserlinda/p/5740058.html