Page 191 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 5. You have a B-tree of order 5 in figure given below. Explain to delete C from it.

6. There are 24 = 4! possible ordered sequences of the four keys 1, 2, 3, 4, but only 14 distinct
binary trees with four nodes. Therefore, these binary trees are not equally likely to occur
as search trees. Find which one of the 14 binary search trees corresponds to each of the
24 possible ordered sequences of 1, 2, 3, 4. Thereby find the probability for building each of

the binary search trees from randomly ordered input.
7. “A node containing k keys always also contains k+1 pointers.” Discuss.

8. “The split operation transforms a full node with 2t – 1 keys into two nodes with t - 1 keys
each”. Explain
9. Explain the process of deletion of key from b-tree with the help of suitable example.

10. Binary trees are defined recursively; algorithms for manipulating binary trees are usually

best written recursively. In programming with binary trees, be aware of the problems
generally associated with recursive algorithms. Be sure that your algorithm terminates
under any condition and that it correctly treats the trivial case of an empty tree.
Answers: Self Assessment

1. (a) 2. (c)
3. analogous 4. database
5. depth 6. B-Tree-Create
7. True 8. False

9. True 10. True
8.13 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.

186 LOVELY PROFESSIONAL UNIVERSITY