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

Splay Tree Insertion

Inserting elements into splay trees and splaying the new node to maintain structure.

Splay Tree Insertion

What you'll learn: How to insert new elements into a splay tree and automatically splay them to the root to maintain the self-adjusting structure.

The Core Idea

Inserting into a splay tree follows a two-step process. First, you perform a standard BST insertion—finding the correct position based on the key and adding a new leaf node. Second, you immediately splay that newly inserted node all the way to the root using the rotations you've already learned (zig, zig-zig, zig-zag).

This ensures recently inserted elements become easily accessible at the top of the tree, embodying splay trees' philosophy: frequently accessed items (including new ones) should be near the root.

How It Works

  1. BST Insert: Start at the root and traverse down comparing keys, just like ordinary BST insertion, until you find the appropriate spot for the new node
  2. Splay to Root: Once inserted as a leaf, apply the splaying operation to move this new node to the root position using the appropriate rotation cases (zig-zig, zig-zag, or zig)

Think of it like adding a new book to a shelf and then immediately moving it to the front desk—you assume someone will want to access it soon.

Why Splay After Insertion?

The splay operation restructures the tree along the path from the new node to the root. This accomplishes two things: it brings the new element to the top (O(1) access if needed again soon), and it partially balances the tree by shortening deep paths.

Key Takeaway: Splay tree insertion combines standard BST insertion with an immediate splay operation that moves the new node to the root, ensuring recently inserted items are quickly accessible and helping maintain reasonable tree balance over time.