[ basic operation of naive order statistic tree ] 樸素二元搜尋樹 名次樹的基本操作

一般的名次樹支援以下幾種操作:

1.插入
2.刪除
3.查找
4.求節點大小
5.求元素名次
6.求第k大
7.求前驅
8.求後繼

之前寫的模板已經有了前六種操作，因此我會在本模板中附上求前驅跟後繼的操作
前驅與後繼並不是名次樹才有的操作，在不記錄節點大小的情形下也能求得
關於求前驅跟後繼操作的說明可以參考 随机平衡二叉查找树Treap的分析与应用 這篇文章

以下提供模板:

	#ifndef NAIVE_BINARY_SEARCH_TREE
	#define NAIVE_BINARY_SEARCH_TREE
	template<typename T>
	class bs_tree{
	private:
	struct node{
	node *ch[2];
	int s;
	T data;
	node(const T&d):s(1),data(d){ch[0]=ch[1]=0;}
	}*root;
	inline int size(node *o){return o?o->s:0;}
	void insert(node *&o,const T&data){
	if(!o)o=new node(data);
	else o->s++,insert(o->ch[o->data<data],data);
	}
	inline void success_erase(node *&o){
	node *t=o;
	o=o->ch[0]?o->ch[0]:o->ch[1];
	delete t;
	}
	bool erase(node *&o,const T &data){
	if(!o)return 0;
	if(o->data==data){
	if(!o->ch[0]||!o->ch[1])success_erase(o);
	else{
	o->s--;
	node **t=&o->ch[1];
	for(;(*t)->ch[0];t=&(*t)->ch[0])(*t)->s--;
	o->data=(*t)->data;
	success_erase(*t);
	}return 1;
	}else if(erase(o->ch[o->data<data],data)){
	o->s--;return 1;
	}return 0;
	}
	node *preorder(node *&x,node *y,const T&data){
	if(!x)return y;
	if(x->data<data)return preorder(x->ch[1],x,data);
	else return preorder(x->ch[0],y,data);
	}
	node *successor(node *&x,node *y,const T&data){
	if(!x)return y;
	if(data<x->data)return successor(x->ch[0],x,data);
	else return successor(x->ch[1],y,data);
	}
	void clear(node *&p){
	if(p)clear(p->ch[0]),clear(p->ch[1]),delete p;
	}
	public:
	bs_tree():root(0){}
	~bs_tree(){clear(root);}
	inline void clear(){clear(root),root=0;}
	inline void insert(const T &data){
	insert(root,data);
	}
	inline bool erase(const T &data){
	return erase(root,data);
	}
	inline bool find(const T &data){
	for(node *o=root;o;)
	if(o->data==data)return 1;
	else o=o->ch[o->data<data];
	return 0;
	}
	inline const T&preorder(const T&data){
	node *o=preorder(root,0,data);
	if(o)return o->data;
	return data;
	}
	inline const T&successor(const T&data){
	node *o=successor(root,0,data);
	if(o)return o->data;
	return data;
	}
	inline int size(){return size(root);}
	inline int rank(const T &data){
	int cnt=0;
	for(node *o=root;o;)
	if(o->data<data)cnt+=size(o->ch[0])+1,o=o->ch[1];
	else o=o->ch[0];
	return cnt;
	}
	inline const T &kth(int k){
	for(node *o=root;;)
	if(k<=size(o->ch[0]))o=o->ch[0];
	else if(k==size(o->ch[0])+1)return o->data;
	else k-=size(o->ch[0])+1,o=o->ch[1];
	}
	inline const T &operator[](int k){
	return kth(k);
	}
	};
	#endif

view raw bst.cpp hosted with ❤ by GitHub