Page 164 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 7: Splay Trees
Mandeep Kaur, Lovely Professional University

Unit 7: Splay Trees Notes

CONTENTS

Objectives
Introduction
7.1 Splay Trees
7.2 Operations
7.3 Splay Operation

7.4 Rotations
7.5 Splay Tree Application
7.6 Summary
7.7 Keywords

7.8 Self Assessment
7.9 Review Questions
7.10 Further Readings

Objectives

After studying this unit, you will be able to:
Describe splay trees

Explain splay tree operation

Introduction

Splay trees are binary search trees that achieve our goals by being self-adjusting in a quite
remarkable way: Every time we access a node of the tree, whether for insertion or retrieval, we
perform radical surgery on the tree, lifting the newly accessed node all the way up, so that it
becomes the root of the modified tree. Other nodes are pushed out of the way as necessary to

make room for this new root. Nodes that are frequently accessed will frequently be lifted up to
become the root, and they will never drift too far from the top position. Inactive nodes, on the
other hand, will slowly be pushed farther and farther from the root.
It is possible that splay trees can become highly unbalanced, so that a single access to a node of
the tree can be quite expensive. Later in this section, however, we shall prove that, over a long
sequence of accesses, splay trees are not at all expensive and are guaranteed to require not many
more operations even than AVL trees. The analytical tool used is called amortized algorithm
analysis, since, like insurance calculations, the few expensive cases are averaged in with many
less expensive cases to obtain excellent performance over a long sequence of operations.

7.1 Splay Trees

Splay Trees were invented by Sleator and Tarjan. This data structure is essentially a binary tree
with special update and access rules. It has the property to adapt optimally to a sequence of tree
operations. More precisely, a sequence of m operations on a tree with initially n nodes takes time
O (n ln (n) + m ln (n)).

LOVELY PROFESSIONAL UNIVERSITY 159