[tree] common balanced tree

Problem surface

Title Description

You need to write a data structure to maintain some numbers, which needs to provide the following operations:

  1. insert x \text{x} x number
  2. delete x \text{x} Number of x (if there are multiple identical numbers, only one will be deleted)
  3. query x \text{x} Ranking of x number (ranking is defined as the number of numbers smaller than the current number) +1 \text{+1} +1 )
  4. Query ranking is x \text{x} Number of x
  5. seek x \text{x} Precursor of x (defined as less than x \text{x} x. And the maximum number)
  6. seek x \text{x} Successor of x (successor defined as greater than) x \text{x} x. And the smallest number)

Input format

First behavior n \text{n} n. Indicates the number of operations, as shown below n \text{n} n lines, each line has two numbers opt \text{opt} opt and x x x, opt \text{opt} opt indicates the sequence number of the operation ( 1 ≤ opt ≤ 6 ) ( 1 \leq \text{opt} \leq 6) (1≤opt≤6)

Output format

For operation 3,4,5,6 \text{3,4,5,6} 3, 4, 5 and 6 output a number for each line, indicating the corresponding answer

Sample data

input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

output

106465
84185
492737

Data range

about 100 % \text{100}\% 100% data, 1 ≤ n ≤ 1 0 5 1\le n \le 10^5 1≤n≤105, ∣ x ∣ ≤ 1 0 7 |x| \le 10^7 ∣x∣≤107

Algorithm analysis

concept

Treap

Tree pile \text {tree heap} Tree heap, also known as tree heap in data structure Treap \text{Treap} A heap is a random additional field that satisfies the nature of the heap Binary search tree [ 1 ] \text {binary search tree} ^ {[1]} Binary search tree [1], whose structure is equivalent to a binary search tree inserted with random data. The expected time complexity of its basic operation is O ( log ⁡ 2 n ) O(\log_{2}{n}) O(log2​n). Compared with other balanced binary search trees, Treap \text{Treap} The characteristics of Treap are Simple implementation \text{easy implementation} The implementation is simple and can basically Achieve random balance \text {achieve random balance} Structure to achieve random balance.
Treap \text{Treap} A tree is a tree Binary sort tree [ 1 ] \text {binary sort tree} ^ {[1]} Binary sort tree [1], its left subtree and right subtree are one respectively Treap \text{Treap} Different from the general binary sort tree, Treap \text{Treap} Treap records an additional data, which is priority \text {priority} Priority. Treap \text{Treap} While forming a binary sort tree with key codes, Treap also meets heap \text {heap} The nature of the heap (here we assume that the priority of a node is greater than that of its children).

Binary search tree / binary sort tree

two fork search Rope tree / two fork Row order tree [ 1 ] {binary search tree / binary sort tree} ^ {[1]} Binary search tree / binary sort tree [1]
two fork check look for tree Binary lookup tree Binary lookup tree( B i n a r y S e a r c h T r e e Binary Search Tree BinarySearchTree two fork search Rope tree Binary search tree Binary search tree, two fork Row order tree Binary sort tree Binary sort tree)
It is either an empty tree or a binary tree with the following properties:

  1. If its left subtree is not empty, the values of all nodes on the left subtree are less than the values of its root node;
  2. If its right subtree is not empty, the value of all nodes on the right subtree is greater than that of its root node;
  3. Its left and right subtrees are also binary sort trees.

application

Operation 1

To solve this problem, we can first process and model the data:
For example, this set of data
12 5 18 2 9 15 19 17 16
You can create a tree as shown in the figure

To do this, we only need to use the nature of binary search tree (mentioned above)
Recursively find the position where the node should be

#include<bits/stdc++.h>
#define INF 0x3fffffff
using namespace std;
int K,N,M,op,q,root,last,ans=0;
struct Node{//Define node
	int val,l,r,cnt,size,f;
	//val is the value, l and r are the left and right sons, and cnt is the number of current values,
	//size is the number of current nodes and words, and f is a random number
}node[10000039];
void pushup(int p){
	node[p].size=node[node[p].l].size+node[node[p].r].size+node[p].cnt;
	//The number of all nodes is the number of nodes of the left son plus the number of nodes of the right son plus the number of current nodes
}
int newnode(int x){//New node (k is the number of nodes)
	node[++K].val=x,node[K].cnt=node[K].size=1;//The value is x, cnt is 1, and the total number of subtrees and current nodes is 1
	node[K].f=rand();//f is a random number
	return K;
}
void insert(int &p,int x){//Insert operation (operation 1)
	if(!p)p=newnode(x);//Create a new node when you find an empty location
	else if(x==node[p].val){node[p].cnt++,node[p].size++;}
	//If this node already exists, use cnt + + and size at the same time++
	else if(x<node[p].val){insert(node[p].l,x);if(node[node[p].l].f<node[p].f)zag(p);}
	//If x is smaller than the current value, go to the left
	else if(x>node[p].val){insert(node[p].r,x);if(node[node[p].r].f<node[p].f)zig(p);}
	//If x is greater than the current value, go to the right
	pushup(p);
}

0 x 3 f f f f f f f = 1073741823 0x3fffffff=1073741823 0x3fffffff=1073741823
0 x f f f f f f f f = 4294967295 = ? 0xffffffff=4294967295=? 0xffffffff=4294967295=?
What are these two sentences for

Operation 2

zag and zig are right-handed and left-handed

void zag(int &p){
	int k=node[p].l;
	node[p].l=node[k].r,node[k].r=p,p=k;
	pushup(node[p].r),pushup(p);
}
void zig(int &p){
	int k=node[p].r;
	node[p].r=node[k].l,node[k].l=p,p=k;
	pushup(node[p].l),pushup(p);
}
void erase(int &p,int x){
	if(node[p].val==x){//If the current point is the same as x
		if(node[p].cnt>1)node[p].cnt--;//If the number is greater than 1, cnt will be used directly--
		else if(!node[p].l)p=node[p].r;//If there is no left son, go right
		else if(!node[p].r)p=node[p].l;//If there is no right son, turn left
		//If you have them all, it depends on whose f is small and which way to turn
		else if(node[node[p].l].f<node[node[p].r].f)zag(p),erase(node[p].r,x);
		else if(node[node[p].l].f>node[node[p].r].f)zig(p),erase(node[p].l,x);
	}
	else if(node[p].val>x)erase(node[p].l,x);
	else if(node[p].val<x)erase(node[p].r,x);
	//Also left or right
	pushup(p);
}

Operation 3 and 4

int getrank(int p,int x){
	if(!p)return 0;
	else if(node[p].val>x)return getrank(node[p].l,x);
	else if(node[p].val<x)return getrank(node[p].r,x)+node[node[p].l].size+node[p].cnt;
	else if(node[p].val==x)return node[node[p].l].size+1;
}
int getval(int p,int x){
	if(x<=node[node[p].l].size+node[p].cnt&&x>node[node[p].l].size)return node[p].val;
	else if(x<=node[node[p].l].size)return getval(node[p].l,x);
	else return getval(node[p].r,x-node[node[p].l].size-node[p].cnt);
}//Understand for yourself

Operation 5 and 6

int get_pre(int p,int x){
	if(!p)return -INF;
	else if(x>node[p].val)return comp(node[p].val,get_pre(node[p].r,x),1);
	else return get_pre(node[p].l,x);
}
int get_nex(int p,int x){
	if(!p)return INF;
	else if(x<node[p].val)return comp(node[p].val,get_nex(node[p].l,x),0);
	else return get_nex(node[p].r,x);
}

main program

int main(){
	srand((unsigned int)time(0));
	newnode(-INF),newnode(INF);
	root=1,node[1].r=2;pushup(1);
	scanf("%d",&N);
	while(N--){
		scanf("%d%d",&op,&q);
		if(op==1){insert(root,q);}
		if(op==2){erase(root,q);}
		if(op==3){printf("%d\n",getrank(root,q)-1);}
		if(op==4){printf("%d\n",getval(root,q+1));}
		if(op==5){printf("%d\n",get_pre(root,q));}
		if(op==6){printf("%d\n",get_nex(root,q));}
	}
	return 0;
}

Complete code

Do not copy directly

#include<bits/stdc++.h>
#define INF 0xffffffff
using namespace std;
int K,N,op,q,root;
struct Node{int val,l,r,cnt,size,f;}node[100039];
int comp(int a,int b,bool x){return x?(a>b?a:b):(a>b?b:a);}
int newnode(int x){node[++K].val=x,node[K].cnt=node[K].size=1;node[K].f=rand();return K;}
void pushup(int p){node[p].size=node[node[p].l].size+node[node[p].r].size+node[p].cnt;}
void zag(int &p){
	int k=node[p].l;
	node[p].l=node[k].r,node[k].r=p,p=k;
	pushup(node[p].r),pushup(p);
}
void zig(int &p){
	int k=node[p].r;
	node[p].r=node[k].l,node[k].l=p,p=k;
	pushup(node[p].l),pushup(p);
}
void insert(int &p,int x){
	if(!p)p=newnode(x);
	else if(x==node[p].val){node[p].cnt++,node[p].size++;}
	else if(x<node[p].val){insert(node[p].l,x);if(node[node[p].l].f<node[p].f)zag(p);}
	else if(x>node[p].val){insert(node[p].r,x);if(node[node[p].r].f<node[p].f)zig(p);}
	pushup(p);
}
void erase(int &p,int x){
	if(node[p].val==x){
		if(node[p].cnt>1)node[p].cnt--;
		else if(!node[p].l)p=node[p].r;
		else if(!node[p].r)p=node[p].l;
		else if(node[node[p].l].f<node[node[p].r].f)zag(p),erase(node[p].r,x);
		else if(node[node[p].l].f>node[node[p].r].f)zig(p),erase(node[p].l,x);
	}
	else if(node[p].val>x)erase(node[p].l,x);
	else if(node[p].val<x)erase(node[p].r,x);
	pushup(p);
}
int getrank(int p,int x){
	if(!p)return 0;
	else if(node[p].val>x)return getrank(node[p].l,x);
	else if(node[p].val<x)return getrank(node[p].r,x)+node[node[p].l].size+node[p].cnt;
	else if(node[p].val==x)return node[node[p].l].size+1;
}
int getval(int p,int x){
	if(x<=node[node[p].l].size+node[p].cnt&&x>node[node[p].l].size)return node[p].val;
	else if(x<=node[node[p].l].size)return getval(node[p].l,x);
	else return getval(node[p].r,x-node[node[p].l].size-node[p].cnt);
}
int get_pre(int p,int x){
	if(!p)return -INF;
	else if(x>node[p].val)return comp(node[p].val,get_pre(node[p].r,x),1);
	else return get_pre(node[p].l,x);
}
int get_nex(int p,int x){
	if(!p)return INF;
	else if(x<node[p].val)return comp(node[p].val,get_nex(node[p].l,x),0);
	else return get_nex(node[p].r,x);
}
int main(){
	srand((unsigned int)time(0));
	newnode(-INF),newnode(INF);
	root=1,node[1].r=2;pushup(1);
	scanf("%d",&N);
	while(N--){
		scanf("%d%d",&op,&q);
		if(op==1){insert(root,q);}
		if(op==2){erase(root,q);}
		if(op==3){printf("%d\n",getrank(root,q)-1);}
		if(op==4){printf("%d\n",getval(root,q+1));}
		if(op==5){printf("%d\n",get_pre(root,q));}
		if(op==6){printf("%d\n",get_nex(root,q));}
	}
	return 0;
}

Tags: C++ Algorithm

Posted by pocobueno1388 on Fri, 15 Apr 2022 09:31:41 +0930