Course contentsShow
← Computer Science
Lesson 574 of 2,87213. Balanced TreesFree lesson

Amortized Analysis of Splay Trees

Understanding why splay tree operations achieve O(log n) amortized time complexity.

Amortized Analysis of Splay Trees

What You'll Learn

You'll understand why splay tree operations achieve O(log n) amortized time complexity despite potentially taking O(n) time for individual operations.

The Core Idea

While a single splay operation can take O(n) time in the worst case (imagine splaying a node in a completely skewed tree), the amortized cost averages to O(log n) per operation over any sequence of operations. This is the magic of self-adjustment!

Think of it like a toll road: sometimes you pay a hefty fee (expensive splay), but that payment improves the road for future travelers (restructures the tree). Over many trips, the average cost per journey is reasonable.

Why Amortized Analysis Works Here

The accounting method is commonly used to analyze splay trees:

  1. Assign potential to each node based on its subtree size
  2. When you perform an expensive splay (many rotations), you're actually restructuring deep nodes closer to the root
  3. This restructuring pays forward by making future accesses cheaper
  4. Frequently accessed nodes migrate toward the root automatically

The key insight: Zig-zig rotations (the most common case) reduce tree depth dramatically. Each zig-zig takes a node two levels closer to the root while flattening the tree structure.

The Mathematical Guarantee

For any sequence of m operations on a splay tree containing n nodes, the total time is O(m log n). Therefore, each operation costs O(log n) amortized.

Unlike AVL or Red-Black trees that maintain strict balance, splay trees achieve good performance through adaptive rebalancing — they optimize themselves based on access patterns.

Key Takeaway: Splay trees guarantee O(log n) amortized time per operation because expensive splays restructure the tree to make subsequent operations cheaper, averaging out the cost over time.