Design and Analysis of Algorithms
Unit 2: Advanced Data Structure
- Q1). What is Red-Black Tree? Write its advantage.
- Q2). Write different kinds of rotation in RB Tree.
- Q3). Write the property of Red-Black Tree. Show that the longest simple path from a node x in a RB-Tree to a descendants leaf has length at most twice that of the shortest simple path from node x to a descendants leaf.
- Q4). Discuss the all ceases of insert a node in RB Tree. Also write its algorithm.
- Q5). Discuss the all ceases of remove a node in RB Tree. Also write its algorithm.
- Q6). Explain B-Tree. Write its properties.
- Q7). Write the basic operations in B-Tree.
- Q8). Explain the delete operation of a node from B-Tree.
- Q9). Define a B-Tree of order m. Explain the searching operation in a B-Tree.
- Q10). What is the minimum number of keys in a B-tree of order 32 and height 5?
- Q11). Explain Bionomial Heap. Write its properties and prove it.
- Q12). Write down the procedure to unite two Binomial Heap.
- Q13). Discuss the strucutre of Fibonacci Heaps with potential function and maximum degree.
- Q14). What is a Fibonacci heap? Discuss the application of Fibonacci heaps.
- Q15). Explain interval tree in detail.
- Q16). What is augmented data structure? How to augment a data structure? Explain.