Reference - "Advanced Guide to Algorithm Competition" -lyd
Table of contents
(5) Insertion operation (such as inserting k)
I. Overview
The binary search tree that satisfies the bst property is not unique. We can balance the size of the left and right subtrees by changing the shape of the binary search tree, so that the depth of the entire tree can be maintained at the logn level.
The change method is divided into "left-handed" and "right-handed". Please refer to the data structure textbook for details.
Treap is a compound word of tree and heap. If the node values are random, then the resulting tree will have an average logn level of depth.
When Treap inserts a new node, it gives the node a random weight. Then, like the insertion process of the binary heap, it is checked from the bottom up, and when a node does not satisfy the property of the large root heap, a single rotation is performed, so that the relationship between the node and its parent node is reversed.
In particular, for the deletion operation, we can directly rotate the deleted node down to a leaf node, and then delete it directly.
In short, Treap maintains the bst property through proper single rotation, and at the same time makes the additional weights randomly generated on the node satisfy the large root heap property. All operations are logN level.
2. Detailed operation
1. Common operations
2. Structure definition
int n;
struct Node{
int l,r;
int key,val;
int cnt,size;
}tr[N];
int root,idx;l, r represent the numbers of the left and right child nodes. key represents the value of the node, and val represents the random weight. cnt indicates how many times the current key appears, and size indicates how many nodes there are in the entire subtree.
Both cnt and size are established to satisfy the two operations of ranking evaluation and ranking based on value
3. Operating basic functions
(1)pushup
Calculate size based on child nodes. For 3 4 operations
void pushup(int p)
{
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}(2) Get a new node
int get_node(int key)
{
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].cnt=tr[idx].size=1;
return idx;
}(3) left-handed right-handed
note quotes
void zig(int &p)//Right-handed
{
int q=tr[p].l;
tr[p].l=tr[q].r,tr[q].r=p,p=q;
pushup(tr[p].r),pushup(p);
}
void zag(int &p)
{
int q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;
pushup(tr[p].l),pushup(p);
}(4) Establishment
Set up two sentries. Don't reverse the order of sentries.
void build()
{
get_node(-INF),get_node(INF);
root=1,tr[root].r=2;
pushup(root);
if(tr[1].val<tr[2].val) zag(root);
}(5) Insertion operation (such as inserting k)
If p is empty, create a new node.
If the current key==k, then the node cnt++
If it is greater than k, insert it in the left subtree, and rotate right as needed when backtracking
If it is less than k, insert in the right subtree, and rotate left as needed when backtracking
Finally, for each node, since the insertion changes the subtree information, the current node must be pushed up
void insert(int &p,int key)
{
if(!p) p=get_node(key);
else if(tr[p].key==key) tr[p].cnt++;
else if(tr[p].key>key)
{
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[tr[p].r].val) zig(p);
}
else
{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[tr[p].l].val) zag(p);
}
pushup(p);
}(6) Delete operation
If the node is empty, it is meaningless and return s directly
If the current node key==k:
If cnt>1, just cnt--
If not a leaf node:
If there is no right subtree, or right rotation is required: right rotation, and then recursively delete on the right subtree of p
Correspondingly, if there is no left subtree or left rotation is required: just left rotation, and then recurse the left subtree
The remaining cases are leaf nodes: just p=0 and delete
If the current node key>k recursive left subtree
else recursive right subtree
Finally, you still need to remember to pushup! ! ! !
void remove(int &p,int key)
{
if(!p) return;
if(tr[p].key==key)
{
if(tr[p].cnt>1) tr[p].cnt--;
else if(tr[p].l||tr[p].r)
{
if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r,key);
}
else
{
zag(p);
remove(tr[p].l,key);
}
}
else p=0;
}
else if(tr[p].key>key) remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}(7) Query operation
int get_rank_by_key(int p,int key)
{
if(!p) return 0;
if(tr[p].key==key) return tr[tr[p].l].size+1;
if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);
return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank)
{
if(!p) return INF;
if(tr[tr[p].l].size>=rank) return get_key_by_rank(tr[p].l,rank);
if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].key;
return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
int get_prev(int p,int key)
{
if(!p) return -INF;
if(tr[p].key>=key) return get_prev(tr[p].l,key);
return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p, int key) // Find the smallest number that is strictly greater than key
{
if (!p) return INF;
if (tr[p].key <= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}
Full code:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =1e5+10,INF=1e8;
int n;
struct Node{
int l,r;
int key,val;
int cnt,size;
}tr[N];
int root,idx;
void pushup(int p)
{
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}
int get_node(int key)
{
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].cnt=tr[idx].size=1;
return idx;
}
void zig(int &p)//Right-handed
{
int q=tr[p].l;
tr[p].l=tr[q].r,tr[q].r=p,p=q;
pushup(tr[p].r),pushup(p);
}
void zag(int &p)
{
int q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;
pushup(tr[p].l),pushup(p);
}
void build()
{
get_node(-INF),get_node(INF);
root=1,tr[root].r=2;
pushup(root);
if(tr[1].val<tr[2].val) zag(root);
}
void insert(int &p,int key)
{
if(!p) p=get_node(key);
else if(tr[p].key==key) tr[p].cnt++;
else if(tr[p].key>key)
{
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[tr[p].r].val) zig(p);
}
else
{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[tr[p].l].val) zag(p);
}
pushup(p);
}
void remove(int &p,int key)
{
if(!p) return;
if(tr[p].key==key)
{
if(tr[p].cnt>1) tr[p].cnt--;
else if(tr[p].l||tr[p].r)
{
if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r,key);
}
else
{
zag(p);
remove(tr[p].l,key);
}
}
else p=0;
}
else if(tr[p].key>key) remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}
int get_rank_by_key(int p,int key)
{
if(!p) return 0;
if(tr[p].key==key) return tr[tr[p].l].size+1;
if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);
return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank)
{
if(!p) return INF;
if(tr[tr[p].l].size>=rank) return get_key_by_rank(tr[p].l,rank);
if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].key;
return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
int get_prev(int p,int key)
{
if(!p) return -INF;
if(tr[p].key>=key) return get_prev(tr[p].l,key);
return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p, int key) // Find the smallest number that is strictly greater than key
{
if (!p) return INF;
if (tr[p].key <= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}
int main()
{
build();
cin>>n;
while(n--)
{
int op,x;
cin>>op>>x;
if(op==1) insert(root,x);
else if(op==2) remove(root,x);
else if(op==3) cout<<get_rank_by_key(root,x)-1<<endl;
else if(op==4) cout<<get_key_by_rank(root,x+1)<<endl;
else if(op==5) cout<<get_prev(root,x)<<endl;
else
{
cout<<get_next(root,x)<<endl;
}
}
return 0;
}practical application
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N =33010,INF=1e8;
typedef long long LL;
int n;
struct Node{
int l,r;
int key,val;
}tr[N];
int root,idx;
int get_node(int key)
{
tr[++idx].key=key;
tr[idx].val=rand();
return idx;
}
void zig(int &p)
{
int q=tr[p].l;
tr[p].l=tr[q].r,tr[q].r=p,p=q;
}
void zag(int &p)
{
int q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;
}
void build()
{
get_node(-INF),get_node(INF);
root=1,tr[root].r=2;
//if(tr[root].val<tr[tr[root].r].val) zag(root);
}
void insert(int &p,int key)
{
if(!p) p=get_node(key);
else if(tr[p].key==key) return;
else if(tr[p].key>key)
{
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[p].val) zig(p);
}
else
{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[p].val) zag(p);
}
}
int get_prev(int p,int key)
{
if(!p) return -INF;
if(tr[p].key>key) return get_prev(tr[p].l,key);
return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p,int key)
{
if(!p) return INF;
if(tr[p].key<key) return get_next(tr[p].r,key);
return min(tr[p].key,get_next(tr[p].l,key));
}
int main()
{
build();
cin>>n;
LL res=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(i==1) res+=x;
else res+= min(x - get_prev(root,x),get_next(root,x)-x);
insert(root,x);
}
cout<<res;
return 0;
}
author: yankai
Link: https://www.acwing.com/activity/content/code/content/5279849/
source: AcWing
Copyright belongs to the author. For commercial reprint, please contact the author for authorization, for non-commercial reprint, please indicate the source.