Page 173 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 4. Consider the following binary search tree:

Splay this tree at each of the following keys in turn:
d b g f a d b d

Each part builds on the previous; that is, use the final tree of each solution as the starting

tree for the next part.
5. “Splay trees are binary search trees that achieve our goals by being self-adjusting in a quite
remarkable way”. Discuss
6. “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”. Explain

Answers: Self Assessment
1. (d) 2. (a)
3. True 4. True

5. time complexity 6. amortized costs O (ln (n))
7. amortized analysis 8. double

7.10 Further Readings

Books Brian W. Kernighan and Dennis M. Ritchie, The C Programming Language, Prentice
Hall, 1988.
Burkhard Monien, Data Structures and Effi cient Algorithms, Thomas Ottmann,
Springer.
Kruse, Data Structure & Program Design, Prentice Hall of India, New Delhi.
Mark Allen Weles, Data Structure & Algorithm Analysis in C, Second Ed., Addison-
Wesley Publishing.
RG Dromey, How to Solve it by Computer, Cambridge University Press.
Shi-Kuo Chang, Data Structures and Algorithms, World Scientifi c.
Shi-kuo Chang, Data Structures and Algorithms, World Scientifi c.

Sorenson and Tremblay, An Introduction to Data Structure with Algorithms.

168 LOVELY PROFESSIONAL UNIVERSITY