Handbook of Data Structures and Applications, 2nd Edition

13

Splay Trees

Sanjeev Saxena

Indian Institute of Technology at Kanpur

13.1Introduction

13.2Splay Trees

13.3Analysis

Access and Update Operations

13.4Optimality of Splay Trees

Static Optimality•Static Finger Theorem•Working Set Theorem•Other Properties and Conjectures

13.5Linking and Cutting Trees

Data Structure•Solid Trees•Rotation•Splicing•Splay in Virtual Tree•Analysis of Splay in Virtual Tree•Implementation of Primitives for Linking and Cutting Trees

13.6Case Study: Application to Network Flows

13.7Implementation without Linking and Cutting Trees

13.8FIFO Dynamic Tree Implementation

13.9Variants of Splay Trees and Top-Down Splaying

Acknowledgments

References

13.1Introduction

In this chapter, we discuss the following topics:

1.Introduction ...