About Splay Tree

Front Cheese

$\LARGE {a big list of sub-definitions of binary search tree and balanced tree boring}$$

Binary Search Tree (BST Tree)

define

A binary search tree is a tree data structure of binary trees defined as follows:

The empty tree is a binary search tree.
If the left subtree of a binary search tree is not empty, the additional weights of all points in its left subtree are less than the value of its root node.
If the right subtree of a binary search tree is not empty, all points in its right subtree have additional weights greater than the value of its root node.
The left and right subtrees of a binary search tree are both binary search trees.

complexity theory

The time spent on basic operations on a binary search tree is proportional to the height of the tree.$\color{#40c0bb}{positive ratio}$. For an organization that has$n$ The optimal time complexity of these operations in a binary search tree of nodes is$O(\log n)$The worst is$O(n)$. Randomly constructing such a binary search tree of$\color{#40c0bb}{expected height}$because of$O(\log n)$。

characteristic

It's really just a matter of defining

found$x$ is a node in a binary search tree.

in the event that$y$ be$x$ a node in the left subtree, then$≤$。

in the event that$y$ be$x$ a node in the right subtree, then$≥$。

in a binary search tree:

If the left subtree of any node is not empty, then no node in the left subtree has a value greater than the value of its root node.
If the right subtree of any node is not empty, then the value of all nodes in the right subtree is not less than the value of its root node.
The left and right subtrees of any node are also binary search trees, respectively.

use

A binary search tree usually accomplishes the following operations efficiently:

Find Min/Max
Search Elements
Insert an element
Delete an element
Find the ranking of the elements
Find the element with rank k

balance tree

define

From the complexity analysis of a binary search tree, it is clear that the complexity of the operation is related to the height of the tree$h$ Related.

Then we can reduce the complexity of the operation by maintaining the height of the tree (balancing) by certain operations, which are$\color{#40c0bb}{Balanced Tree}$。

$\color{#40c0bb} \large \textbf{balance}$
It usually means that the absolute value of the difference between the heights of the left and right subtrees of each node (the balance factor) is at most$1$。

Balanced adjustment process - tree rotation

define

Tree rotation is a subtree adjustment operation in a binary tree, where every rotation and$\color{#40c0bb}{no effect}$Perform the binary tree on the$\color{#40c0bb}{Middle order traversal}$The results of the
Tree rotation is usually applied when there is a need to adjust the local balance of a tree. Tree rotation consists of two different approaches, namely$\color{#40c0bb}{Left Rotate or zag)}$cap (a poem)$\color{#40c0bb}{Right Rotate or zig)}$. The two rotations are mirror images and operate inversely to each other.

concrete operation

right-hand side

For the node$A$ The right-handed operation of$A$ the left child$B$ Rotate up to the right instead of$A$ becomes the root node and will$A$ The node is rotated down to the right to become$B$ the root node of the right subtree of$B$ The original right subtree of$A$ of the left subtree.

levitra

Exactly the same.

the concrete situation

In fact, you only need to know a few basic properties of binary search trees:

Each node satisfies the values of the nodes of the left subtree areless thanown values, the values of the nodes in the right subtree are allmore thantheir own values.Left and right subtrees are also binary search trees。
A mid-order traversal of a binary search tree yields an ordered sequence of the values of all the nodes of this tree. (i.e., all the values sorted)

main part of a movie

contexts

It's easy to see.$BST Tree$An extreme case of the$\color{#40c0bb}{degradation}$

this kind of~~malignant tumor~~The data allows the time complexity to increase from$O(log(n))$Degraded to the horror of$O(n)$

So there were all sorts of scientists who started thinking about life and deranged themselves to create all sorts of ways to optimize the BST...

Splay

define

what is$Splay$？
She is actually a kind of balance tree that can be rotated.
She can do this bySplay/stretch operationContinuously rotating a node to the root node so that the whole tree still satisfies the properties of a binary lookup tree can be used in equalizing the$O(\log N)$ Insert, Find and Delete operations are completed in time and are balanced without degenerating into chains.

Principle & Realization

Node Maintenance Information

rt	tot	fa[N]	ch[N][2]	val[N]	cnt[N]	sz[N]
radical (chemistry)	Node number	parent node	Child node Left 0 Right 1	weight	Node size	Subtree size

basic operation

The first thing you need to know is some basic operations:

$maintain(x)$: After changing the position of a node, the node$x$ (used form a nominal expression)$\text{size}$ Updated.
$get(x)$: Judgment Node$x$ Is it the left or right son of the father node.
$clear(x)$: Empty nodes$x$。


void maintain(int x){
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
	
bool get(int x){
	return x==ch[fa[x]][1];
}
	
void clear(int x){
	ch[x][0]=ch[x][1]=fa[x]=val[x]=sz[x]=cnt[x]=0;
}

It's easy, right?

The next one can be on the hard side.

The rotate operation.

From the definition, we know that we want to rotate a node to the root node.

And to figure out how to rotate a node to the root node, first consider how to rotate her to the father node.

When the node is a left son

As in the figure, boxes represent subtrees and rounded boxes represent nodes

Now, we're going to put$x$ The node climbs one level up to his parent node$y$ , to ensure that we don't change the middle-order traversal order, we can let the$y$ constitute$x$ The right son.

But the original$x$ The node is there right son$B$ The, obviously we're going to put$B$ It takes a change of position to get there.

We know:$x$ The right subtree of a node is necessarily larger than$x$ Node's;$y$ The nodes are necessarily larger than$x$ The right subtree of the node and the$x$ of the node itself (because$x$ node and its right subtree are the original$y$ of the left subtree, which is certainly better than the$y$ Small (based on binary search tree properties))

So we can put$x$ The node's original right subtree is placed in$y$ of the left son's position to reach the goal.

In fact, that's what$\color{#40c0bb}\textbf{right}$The principle of the

When the node is a right son

The principle is the same.

revolve

understand

If the node$x$ because of$y$ Location of nodes$z$($z=0$ is the left node.$z=1$ is the right node )

commander-in-chief (military)$y$ node into the$x$ nodal$z \oplus 1$ The position of the (i.e., the$x$ The nodes are$y$ the right subtree of the node, then$y$ nodes are placed in the left subtree.$x$ The nodes are$y$ node left subtree, then$y$ node is then placed in the right subtree position)
if$x$ nodal$z \oplus 1$ position, there is already a node, or a subtree, so we will replace the original$x$ nodal$z \oplus 1$ position of the subtree, and put it into the$y$ Location of nodes$z$ Above.

Here's a little mnemonic: "Left-hand carry right-left and hang right, right-hand carry left-right and hang left.”

Once you read the text, you can try to understand the code.

realization

void rotate(int x){
int y=fa[x],z=fa[y],chk=get(x);
    //y is the father of x, z is the grandfather of x, chk determines if x is the left or right son

ch[y][chk]=ch[x][chk^1];
if(ch[x][chk^1]) fa[ch[x][chk^1]]=y;
ch[x][chk^1]=y;
fa[y]=x;
fa[x]=z.
if(z) ch[z][y==ch[z][1]]=x;
maintain(y),maintain(x).
}

Splay Operation

Splay(x,to) It's about putting$x$ The node rotates to$to$ Nodes.

one-way traffic

A very violent approach for$x$ nodes, with each upward rotation to$fa[x]$ Until$to$ Nodes.

But if you do write it that way it might~~T into SB~~Stuck with some toxic data $n^2$

So don't look at the single spin as simple and easy to write, the double spin is more recommended here.

double helix

The optimization of the double spin lies in:

If you are currently in a co-linear state then first rotate the$y$ And then rotate.$x$ . This will force them not to be in a co-linear state and then balance the tree .
If the current state is not co-linear, then just rotate the$x$ Ready to go.

void splay(int x,int goal=0){
	if(goal==0) rt=x;
	while(fa[x]!=goal){
		int f=fa[x];
		if(fa[fa[x]]!=goal){
			rotate(get(x)==get(f)?f:x);
		}
		rotate(x);
	}
}

search operation

Of course you can leave it out.

The lookup operation is performed because the lookup$k$ The precursor and successor to the precursor and successor to the successor need to be$k$ Spin to the location of the root node.

You can actually justsplay(k,0) Or insert first$k$ Query it and then delete it.

Splay is also a binary search tree and thus satisfies that the left side are all smaller than him and the right side are all larger than him.

So just recurse to the left/right accordingly.

void find(int x){
    int u=root;
    if(!u)return;//vacant
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)
        u=t[u].ch[x>t[u].val];
    splay(u,0);
}

insertion operation

If the tree is empty, insert the root directly and exit.
If the weight of the current node is equal to$k$ Then increase the size of the current node and update the information of the node and the father, and put the current node into Splay operation.
Otherwise, according to the nature of the binary search tree (the left side are all smaller than him, the right side are all bigger than him) to find down, find the empty node to insert can be.

void ins(int k){//insert
	if(!rt){
		val[++tot]=k;
		cnt[tot]++;
		rt=tot;
		maintain(rt);
		return;
	}
	int cur=rt,f=0;
	while(1){
		if(val[cur]==k){
			cnt[cur]++;
			maintain(cur);
			maintain(f);
			splay(cur);
			break;
		}
		f=cur;
		cur=ch[cur][val[cur]<k];
		if(!cur){
			val[++tot]=k;
			cnt[tot]++;
			fa[tot]=f;
			ch[f][val[f]<k]=tot;
			maintain(tot);
			maintain(f);
			splay(tot);
			break;
		}
	}
}

consult (a document etc)$x$ ranking

in the event that$x$ less than the weight of the current node, lookup to its left subtree.
in the event that$x$ than the weight of the current node, add the answer to the left subtree ($size$) and the current node ($cnt$) size, lookup to its right subtree.
in the event that$x$ Same weight as current node (already exists), add answer to$1$ and return.

int rk(int k){//the rank of "k"
	int res=0,cur=rt;
	while(1){
		if(k<val[cur]){
			cur=ch[cur][0];
		}else{
			res+=sz[ch[cur][0]];
			if(!cur) return res+1;
			if(k==val[cur]){
				splay(cur);
				return res+1;
			}
			res+=cnt[cur];
			cur=ch[cur][1];
		}
	}
}

Check Ranking$x$ numbers of

If the left subtree is non-empty and the remaining rank$k$ Not larger than the size of the left subtree$size$, then lookup to the left subtree.
failing which$k$ Subtract the size of the left subtree's and the root. If at this point$k$ is less than or equal to the value of$0$, then return the weights of the root node, otherwise continue the search to the right subtree.

int kth(int k){//the number whose rank is "k"
	int cur=rt;
	while(1){
		if(ch[cur][0] && k<=sz[ch[cur][0]]){
			cur=ch[cur][0];
		}else{
			k-=cnt[cur]+sz[ch[cur][0]];
			if(k<=0){
				splay(cur);
				return val[cur];
			}
			cur=ch[cur][1];
		}
	}
}

Query predecessor & successor

Front-drive is$x$ is the rightmost node in the left subtree of

successor is$x$ The leftmost node in the right subtree of

front drive

int pre(){//precursor
	int cur=ch[rt][0];
	if(!cur) return cur;
	while(ch[cur][1]) cur=ch[cur][1];
	splay(cur);
	return cur;
}

successor

Actually, it's the opposite of checking the front drive

int nxt(){//next or successor
	int cur=ch[rt][1];
	if(!cur) return cur;
	while(ch[cur][0]) cur=ch[cur][0];
	splay(cur);
	return cur;
}

There are many ways to write a pre-decessor and successor, so if you want to be lazy and just write it once, you can do so.

int prenxt(int x,int k){//0 pre 1 nxt
	find(x);
	int cur=rt;
	if(!k && val[cur]<x) return cur;
	if(k && val[cur]>x) return cur;
	cur=ch[cur][k];
	while(ch[cur][!k]){
		cur=ch[cur][!k];
	}
	return cur;
}

Delete operation

firstly$x$ Rotate to the root position.

in the event that$cnt[x]>1$(There's more than one)$x$), then it will be$cnt[x] - 1$ And quit.
Otherwise, just merge its left and right subtrees.

void del(int k){//delete
	rk(k);
	if(cnt[rt]>1){
		cnt[rt]--;
		maintain(rt);
		return;
	}
	if(!ch[rt][0] && !ch[rt][1]){//vacant
		clear(rt);
		rt=0;
		return;
	}
	if(!ch[rt][0]){
		int cur=rt;
		rt=ch[rt][1];
		fa[rt]=0;
		clear(cur);
		return;
	}
	if(!ch[rt][1]){
		int cur=rt;
		rt=ch[rt][0];
		fa[rt]=0;
		clear(cur);
		return;
	}
	int cur=rt,x=pre();
	fa[ch[cur][1]]=x;
	ch[x][1]=ch[cur][1];
	clear(cur);
	maintain(rt);
}

Then congratulations, you've learned the basics of Splay.

As for zone flipping and all that...

~~Next time.~~

Code

Elaina's Code

struct Slpay{
	int rt;//radical (chemistry)
	int tot;//Node number
	int fa[N];//parent node
	int ch[N][2];//child node unorthodox0right (-hand)1
	int val[N];//weighting
	int cnt[N];//Node size
	int sz[N];//Subtree size
	
	void maintain(int x){
		sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
	}
	
	bool get(int x){
		return x==ch[fa[x]][1];
	}
	
	void clear(int x){
		ch[x][0]=ch[x][1]=fa[x]=val[x]=sz[x]=cnt[x]=0;
	}
	
	
	void rotate(int x){
		int y=fa[x],z=fa[y],chk=get(x);
		ch[y][chk]=ch[x][chk^1];
		if(ch[x][chk^1]) fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y;
		fa[y]=x;
		fa[x]=z;
		if(z) ch[z][y==ch[z][1]]=x;
		maintain(y);
		maintain(x);
	}
	
	void splay(int x,int goal=0){
		if(goal==0) rt=x;
		while(fa[x]!=goal){
			int f=fa[x];
			if(fa[fa[x]]!=goal){
				rotate(get(x)==get(f)?f:x);
			}
			rotate(x);
		}
	}
	
	void ins(int k){//insert
		if(!rt){
			val[++tot]=k;
			cnt[tot]++;
			rt=tot;
			maintain(rt);
			return;
		}
		int cur=rt,f=0;
		while(1){
			if(val[cur]==k){
				cnt[cur]++;
				maintain(cur);
				maintain(f);
				splay(cur);
				break;
			}
			f=cur;
			cur=ch[cur][val[cur]<k];
			if(!cur){
				val[++tot]=k;
				cnt[tot]++;
				fa[tot]=f;
				ch[f][val[f]<k]=tot;
				maintain(tot);
				maintain(f);
				splay(tot);
				break;
			}
		}
	}
	
	int rk(int k){//the rank of "k"
		int res=0,cur=rt;
		while(1){
			if(k<val[cur]){
				cur=ch[cur][0];
			}else{
				res+=sz[ch[cur][0]];
				if(!cur) return res+1;
				if(k==val[cur]){
					splay(cur);
					return res+1;
				}
				res+=cnt[cur];
				cur=ch[cur][1];
			}
		}
	}
	
	int kth(int k){//the number whose rank is "k"
		int cur=rt;
		while(1){
			if(ch[cur][0] && k<=sz[ch[cur][0]]){
				cur=ch[cur][0];
			}else{
				k-=cnt[cur]+sz[ch[cur][0]];
				if(k<=0){
					splay(cur);
					return val[cur];
				}
				cur=ch[cur][1];
			}
		}
	}
	
	int pre(){//precursor
		int cur=ch[rt][0];
		if(!cur) return cur;
		while(ch[cur][1]) cur=ch[cur][1];
		splay(cur);
		return cur;
	}
	
	int nxt(){//next or successor
		int cur=ch[rt][1];
		if(!cur) return cur;
		while(ch[cur][0]) cur=ch[cur][0];
		splay(cur);
		return cur;
	}
	
	void del(int k){//delete
		rk(k);
		if(cnt[rt]>1){
			cnt[rt]--;
			maintain(rt);
			return;
		}
		if(!ch[rt][0] && !ch[rt][1]){
			clear(rt);
			rt=0;
			return;
		}
		if(!ch[rt][0]){
			int cur=rt;
			rt=ch[rt][1];
			fa[rt]=0;
			clear(cur);
			return;
		}
		if(!ch[rt][1]){
			int cur=rt;
			rt=ch[rt][0];
			fa[rt]=0;
			clear(cur);
			return;
		}
		int cur=rt,x=pre();
		fa[ch[cur][1]]=x;
		ch[x][1]=ch[cur][1];
		clear(cur);
		maintain(rt);
	}


    void find(int x){
		int cur=rt;
		if(!cur) return;
		while(ch[cur][x>val[cur]]&&x!=val[cur]){
			cur=ch[cur][x>val[cur]];
		}
		splay(cur,0);
	}
	
	int get_pre(int x){
		find(x);
		int cur=rt;
		if(val[cur]<x) return cur;
		cur=ch[cur][0];
		while(ch[cur][1]){
			cur=ch[cur][1];
		}
		return cur;
	}
	
	int get_nxt(int x){
		find(x);
		int cur=rt;
		if(val[cur]>x) return cur;
		cur=ch[cur][1];
		while(ch[cur][0]){
			cur=ch[cur][0];
		}
		return cur;
	}

    int prenxt(int x,int k){//0 pre 1 nxt
		find(x);
		int cur=rt;
		if(!k && val[cur]<x) return cur;
		if(k && val[cur]>x) return cur;
		cur=ch[cur][k];
		while(ch[cur][!k]){
			cur=ch[cur][!k];
		}
		return cur;
	}
}tr;

signed main(){
	int m=rd;
	while(m--){
		int opt=rd,x=rd;
		if(opt==1){
			(x);
		}else if(opt==2){
			(x);
		}else if(opt==3){
			printf("%lld\n",(x));
		}else if(opt==4){
			printf("%lld\n",(x));
		}else if(opt==5){
			(x),printf("%lld\n",[()]),(x);
		}else{
			(x),printf("%lld\n",[()]),(x);
		}
	}
	return Elaina;
}

I'll reward you with a picture for learning so much.

~~I don't want to see it.~~

About Splay Tree

define

complexity theory

characteristic

use

define

Balanced adjustment process - tree rotation

define

concrete operation

right-hand side

levitra

define

Principle & Realization

Node Maintenance Information

basic operation

The rotate operation.

When the node is a left son

When the node is a right son

understand

realization

Splay Operation

one-way traffic

double helix

search operation

insertion operation

consult (a document etc)\(x\) ranking

Check Ranking\(x\) numbers of

Query predecessor & successor

front drive

successor

Delete operation

Code

I'll reward you with a picture for learning so much.