- Blind adjusting version of AVL trees
- Amortized time for all operations is
- Worst case
- Runs faster than AVL tree due to the “locality” of program (程序的局部性)
Force update the nodes in path while accessing, rather than do that when finding inbalance.
You’ll need to splay from the node you accessed all the way to the root.
Node being accessed is:
- Child of root (gets only parent)
- 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
When accessing node , first rotate and , then rotate and .
- 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.
Split(T, x) Split into two non-intersect parts and ( may be not in ), and nodes in are less than , nodes in are greater than .
- We can splay the requied node to the root to do a split.
Split the tree into two parts and make as the new root and as its child.
Splay the required node to the root and delete it (can be done using split), then join the two subtrees left.