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

时间:2021-02-22 20:12:24

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插入啥的或者再插入一个时间戳啥的