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.