Splay trees - Data Structures and Problem Solving Using Java - page 867

common errors

A splay must be performed after every access, even an unsuccessful one,
or the performance bounds are not valid.

1.

The code is still tricky.

2.

Recursive private methods cannot be used safely in the SplayTree class
because the tree depth may be large, even while performance is otherwise
acceptable.

3.

on the internet

The SplayTree class is available online. The code includes versions of
findMin and findMax that are efficient in an amortized sense but not com-
pletely optimized.

SplayTree.java Contains the implementation for the SplayTree class.

exercises

IN SHORT
22.1

Show the result of inserting 3, 1, 4, 5, 2, 9, 6, and 8 into a
a. Bottom-up splay tree

b. Top-down splay tree

Show the result of deleting 3 from the splay tree shown in Exercise 22.1
for both the bottom-up and top-down versions.

22.2

IN THEORY
22.3

Prove that the amortized cost of a top-down splay is O (log N ).

Prove that if all nodes in a splay tree are accessed in sequential order,
the resulting tree consists of a chain of left children.

22.4

Suppose that, in an attempt to save time, we splay on every second
tree operation. Does the amortized cost remain logarithmic?

22.5

Nodes 1 through N = 1024 form a splay tree of left children.
a.

22.6

What is the internal path length of the tree (exactly)?

b. Calculate the internal path length after each of find(1) , find(2) ,

and find(3) when a bottom-up splay is performed.