# Features

- Blind adjusting version of AVL trees
- Amortized time for all operations is $O(\log n)$
- Worst case $O(n)$

- Runs faster than AVL tree due to the “locality” of program (程序的局部性)

# Principle

Force update the nodes in path while accessing, rather than do that when finding inbalance.

# Operations

## Splay

You’ll need to splay from the node you accessed all the way to the root.

### Cases

Node being accessed is:

- Root

Do nothing. - Child of root (gets only parent)

Rotate once:- When accessing the left son, rotate right.
- When accessing the right son, rotate left.

- Have parent and grand-parent

When accessing LR/RL grandchild, rotate**down-top twice**like AVL LR/RL (Zig-Zag)

When accessing LL/RR grandchild, rotate**top-down twice**like AVL LL/RR (Zig-**Zig**)

E.g. for node $g\rightarrow p\rightarrow n$

When accessing node $n$, first rotate $g$ and $p$, then rotate $p$ and $n$.

- All the rotation here occurs regardless of the depth(we don’t care about that)
- If you cannot remember which direction to rotate, just treat unimportant subtrees as node, and try to rotate to the more balanced direction.

## Splitting

`Split(T, x)`

Split $T$ into two non-intersect parts $L$ and $R$ ($x$ may be not in $T$), and nodes in $L$ are less than $x$, nodes in $R$ are greater than $x$.

- We can splay the requied node to the root to do a split.

## Insert

Split the tree into two parts and make $x$ as the new root and $L$ $R$ as its child.

## Delete

Splay the required node to the root and delete it (can be done using split), then join the two subtrees left.