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

Splay Tree Search

Implementing search in splay trees by splaying the accessed node to the root.

Splay Tree Search

You'll learn how searching in a splay tree automatically moves the accessed node to the root through splaying.

The Core Idea

In a splay tree, every time you search for a node—whether the search succeeds or fails—you perform a splaying operation that restructures the tree. When you find the target node, you splay it all the way to the root using the rotation cases you've learned (Zig, Zig-Zig, and Zig-Zag). If the search fails, you splay the last node you accessed (the would-be parent) to the root.

This self-adjusting behavior means frequently accessed nodes naturally migrate toward the top of the tree, making subsequent accesses faster.

How It Works

  1. Perform standard BST search: Start at the root and navigate left or right based on key comparisons, just like in a regular BST.

  2. Found the node? Splay it to the root using the appropriate rotation sequence (Zig-Zig, Zig-Zag, or Zig depending on configuration).

  3. Node not found? Splay the last accessed node (the deepest node you reached before hitting null) to the root.

Why This Matters

Unlike static BSTs, splay trees adapt to access patterns. If you repeatedly search for the same key, it stays near the root for O(1) access. The splaying operation ensures the amortized time complexity remains O(log n) even though individual operations might be O(n) in a worst-case scenario.

Think of it like reorganizing your desk: the items you use most often end up on top, while rarely-used items sink to the bottom naturally through repeated access patterns.

Key Takeaway: Splay tree search always triggers a splay operation that moves the accessed (or last-visited) node to the root, creating a self-optimizing structure based on access frequency.