Splay Trees (10)
Michael L. Littman
October 8th, 1998
SPLAY TREES
Review
Basic Idea
Splaying a Node
Splay Example Step 1
Splay Example Step 2
Splay Example Step 3
Splay Example Step 4
Splay Example Step 5
Splay Properties
Operations Using Splays
Splay Sort
AMORTIZED ANALYSIS
Idea of Amortized Analysis
Classic Example
Increment Code
Counting Flips
Sequence of Flips
Potential Function
It Works!
ANALYSIS OF SPLAY TREES
Splay Operations
Analysis Setup
Case Setup
Zig Case
Zig-Zig Case
Entire Splay
Next:
SPLAY TREES
