Page 172 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 7: Splay Trees

7.7 Keywords Notes

Access Time: The time required to access and retrieve a word from high-speed memory is a few
microseconds at most.
Splay Trees: Splay trees are binary search trees which are self adjusting.

7.8 Self Assessment

Choose the appropriate answer:

1. Splay Trees were invented by
(a) Sleator
(b) Tarjan
(c) Newton

(d) Both (a) and (b)
2. The run time for each operation is essentially the same as for a ...................................
(a) Splay operation.
(b) Zero operation
(c) Play operation
(d) None of the above

State whether the following statements are True or False:
3. The time complexity of maintaining a splay tree is analyzed using an Amortized
Analysis.

4. Each node does not contain a character.
Fill in the blanks:
5. The ............................ of maintaining a splay tree is analyzed using an Amortized Analysis.
6. The trick of the analysis is to define a potential function and to show that each splay

operation has ...............................
7. The key to ................................ is to define the right potential function.

8. There are two kinds of .......................... rotations and one single rotation.

7.9 Review Questions

1. Explain splay operation in splay trees.

2. “The time complexity of maintaining a splay tree is analyzed using an Amortized Analysis.”
Explain
3. “A splay tree does not keep track of heights and does not use any balance factors like an
AVL tree”. Explain

LOVELY PROFESSIONAL UNIVERSITY 167