Modify the binary search tree to support

Assignment Help Basic Computer Science

Reference no: EM13968101

1. a. Show that via AVL single rotations, any binary search tree T1 can be transformed into another search tree T2 (with the same items).

b. Give an algorithm to perform this transformation using O(N log N) rotations on average.

c. Show that this transformation can be done with O(N) rotations, worst-case.

2. Suppose we want to add the operation findKth to our repertoire. The opera- tion findKth(k) returns the kth smallest item in the tree. Assume all items are distinct. Explain how to modify the binary search tree to support this opera- tion in O(log N) average time, without sacri?cing the time bounds of any other operation.

Reference no: EM13968101

Questions Cloud

Identify a recent entrepreneur who demonstrated a successful : Identify a recent entrepreneur who demonstrated a successful harvest strategy or an unsuccessful harvest strategy and explain the factors contributing to failure (if unsuccessful) using the Capital Cow. (need another example besides Martha Stewar..

Separate chaining hash tables : Reimplement separate chaining hash tables using a vector of singly linked lists instead of vectors. The isEmpty routine for quadratic probing has not been written. Can you implement it by returning the expression currentSize==0?

Write a memo to me that describes your career aspirations : Write a memo to me that describes your career aspirations.

Explain why you are requesting a substitution of the gmat : Explain why you are requesting a substitution of the GMAT. Indicate any previous graduate academic experience (B.A in Business Administration)

Modify the binary search tree to support : Suppose we want to add the operation findKth to our repertoire. The opera- tion findKth(k) returns the kth smallest item in the tree. Assume all items are distinct. Explain how to modify the binary search tree to support this opera- tion in O(log ..

How does each sort of capital assist in start up : What sorts of asset or capital availability for a new business owner-small start up. How does each sort of capital assist in start up and continuing business operation over the first few years.

Describe a method to perform insertion : A B∗-tree of order M is a B-tree in which each interior node has between 2M/3 and M children. Describe a method to perform insertion into a B∗-tree.

What is the distance between the observer : What is the distance between the observer and Q? 2) how much elevation did the plane gain between P and Q?

Nodes of a binary tree in level-order : 1. Write a routine to list out the nodes of a binary tree in level-order. List the root, then nodes at depth 1, followed by nodes at depth 2, and so on. You must do this in linear time. Prove your time bound.

User Account

All Pages