What is the Difference between Bottom-up and Top down methods in splay tree?

I have read about Splay tree and I found,there are two methods for constructing the splay tree. They are

1. Bottom-up
2. Top-down

So I need to know What is the difference between the two methods and their working ?

2 Answers

The methods define how you use splaying when searching:

Bottom-up: you search the tree and rotate at the same iteration

Top-down: you first search and at another iteration you rotate

you can read Splay tree

This ideas hold to the creation also, when using the top down you insert the key as if it was a binary serach tree and than move it to the head in another iteration.

A top-down splay tree: performs rotations on the initial access path. Thus a top-down splay tree node does not need a parent link. The splay operation finishes as soon as the search does. That means the overhead for operations of a top-down splay tree is of a relatively small amount.

Bottom-up splay tree: requires a traversal from the root down the tree and then a bottom-up traversal to implement the splaying step, so a bottom-up splay tree implementation looks similar to that of an AVL tree. Besides, it needs a parent link or a stack to store the search path.

An implementation of a top-down splay tree can be found in the data structure book (Chapter 12) written by Weiss.