Splay Tree

Explanation

- A **Splay Tree** is a self-adjusting binary search tree that automatically moves the accessed element to the root via **splaying**.
-
- The **splaying** operation brings the accessed node to the root by performing rotations.

-

• Steps:

  • Insertion: Insert as in a regular binary search tree, then perform a splay operation to bring the newly inserted node to the root.
  • Splaying: The splay operation involves a series of tree rotations that move the accessed node to the root.

• Time Complexity:

  • Insertion: O(log n) amortized
  • Search: O(log n) amortized