CS130 #

DATA STRUCTURES

Work Sheet 5

- Similar to heaps, Treaps are priority queues defined on completely balanced ternary tress where each node has three chidren. Design and analyze algorithms for inserting and extracting the minimum from a treap.
- Show that nh, the minimum number of nodes in an AVL tree
satisfies
*n*_{h}=*F*_{h+2}-1 where*F*_{h}is the*h*th Fibonacci number. - Show how to efficiently merge and split two AVL trees, T1 and T2 where all elements in T1 are less than those in T2.
- Write a procedure for deleting an element from an AVL tree. Show a bound on number of rotations when an element is deleted. Is it same or different from insertion?
- Design a storage scheme for a set of numbers that allows one to
search, insert and delete an identifier in
*O*(1) time. Assume that the numbers are between 1 and m, and n insertions are made.*O*(*m*+*n*) space is available. - Consider searching a linked list having records. Each record has a key consisting of a long string (compared character by character) and a small hash value. What advantage can be taken of the hash value?
- What is the cardinality of the set (
*x*,*y*)|*h*(*x*)=*h*(*y*) (number of collisions), where*h*is a random hash function (Simple uniform hashing)? Number of elements is*n*and table has*m*slots. - Suggest an efficient way to merge two 2-3 Trees
*A*and*B*where all elements in*B*are greater than all elements in*A*.