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 hth 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.