---

Splay Trees – Detailed Explanation

A Splay Tree is a type of self-adjusting Binary Search Tree (BST).
Unlike AVL or Red-Black Trees, a Splay Tree does not maintain strict balance rules.
Instead, it uses a special operation called Splaying to move the most recently accessed node to the root.

This makes the tree optimized for recently used elements.

---

1. Why Splay Trees?

Splay Trees give amortized O(log n) time for operations.

✔ Excellent for applications where some elements are accessed frequently
✔ Recently or frequently accessed nodes become quicker to reach

Used in:

• Caches
• Data compression (e.g., splay-based dictionary in ZIP algorithms)
• Memory allocators
• Routers
• Implementing associative arrays

---

2. Key Operation: Splaying

Splaying = bringing the accessed node to the root by performing tree rotations.

This is done after:

• Search
• Insert
• Delete

Thus, the next access is much faster.

---

3. Types of Splay Operations

Splay operations depend on the node’s position relative to its parent (P) and grandparent (G).

There are 3 major cases:

---

A. Zig (Single Rotation)

Occurs when the node is a child of the root.

Two kinds:

1. Zig-Right (Right rotation)

When node is left child of root.

    P
   /
  X
→  Rotate right on P

2. Zig-Left (Left rotation)

When node is right child of root.

  P
   \
    X
→   Rotate left on P

---

B. Zig-Zig (Double Rotation, Same Direction)

Happens when:

• Node and parent are both left child (LL)
• OR both right child (RR)

LL Case (Zig-Zig Right)

      G
     /
    P
   /
  X
→  Right rotate G
→  Right rotate P

RR Case (Zig-Zig Left)

  G
   \
    P
     \
      X
→ Left rotate G
→ Left rotate P

---

C. Zig-Zag (Double Rotation, Opposite Directions)

Node and parent are on opposite sides.

LR Case

    G
   /
  P
   \
    X

Steps:

1. Left rotate P
2. Right rotate G

RL Case

  G
   \
    P
   /
  X

Steps:

1. Right rotate P
2. Left rotate G

---

4. Operations on Splay Tree

A. Search

1. Search node like BST.
2. If found → splay it to root.
3. If not found → splay the last accessed node.

Complexity:

• Worst case = O(n)
• Amortized = O(log n)

---

B. Insert

1. Insert node like BST.
2. Splay the new node to the root.
   (Ensures next access is fast.)

---

C. Delete

1. Search for the node → splay it to the root.
2. Remove it.
3. Merge left and right subtrees:
   • Splay the largest node of left subtree to the root.
   • Attach right subtree to its right.

---

5. Complexity of Splay Trees

Operation	Worst Case	Amortized
Search	O(n)	O(log n)
Insert	O(n)	O(log n)
Delete	O(n)	O(log n)

Amortized means:
Although some operations can be slow, the average over many operations is fast.

---

6. Advantages of Splay Trees

✔ Recently accessed nodes become easy to reach
✔ Great for locality of reference
✔ No need to store balance factor or color
✔ Simple rotations compared to AVL/RB trees
✔ Amortized O(log n) for operations

---

7. Disadvantages

✘ Worst-case performance can be O(n)
✘ Structure may oscillate and become temporarily unbalanced
✘ Not ideal for uniform access environments
✘ Height can grow without any strict balancing rules

---

8. Applications of Splay Trees

• Caches where last accessed elements are likely to be accessed again
• Garbage collectors
• String processing (splay trees in ropes)
• Memory allocators
• File systems metadata indexing
• Network routing tables

---

9. Comparison: Splay Tree vs AVL vs Red-Black

Feature	Splay Tree	AVL	Red-Black
Balancing	Not strict	Strict	Moderate
Search	Amortized O(log n)	Fastest	O(log n)
Insert/Delete	Fast amortized	Slower	Faster
Rotations	Many (during splaying)	Many	Fewer
Memory	Low	Stores height	Stores color
Best For	Frequent repeated access	Search-heavy apps	Large dynamic datasets

---

Summary

A Splay Tree is a self-adjusting BST where:

• Recently accessed nodes move to the root
• Uses Zig, Zig-Zig, Zig-Zag rotations
• Gives amortized O(log n) performance
• Excellent for applications with high locality of reference

---