Balanced binary search tree of height

Assignment Help Basic Computer Science

Reference no: EM13968089

1. Write a function to generate the AVL tree of height h with fewest nodes. What is the running time of your function?

2. Write a function to generate a perfectly balanced binary search tree of height h with keys 1 through 2h+1 - 1. What is the running time of your function?

3. Write a function that takes as input a binary search tree, T, and two keys, k1 and k2, which are ordered so that k1 ≤ k2, and prints all elements X in the tree such that k1 ≤ Key(X) ≤ k2. Do not assume any information about the type of keys except that they can be ordered (consistently). Your program should run in O(K + log N) average time, where K is the number of keys printed. Bound the running time of your algorithm.

Reference no: EM13968089

Questions Cloud

How do you think twitter uses a data warehouse : Do you agree that a business can use Twitter to gain business intelligence? How many companies do you think are aware of Twitter and exactly how they can use it to gain BI? How do you think Twitter uses a data warehouse?

Who do you think uses internet dating services : Internet dating services, while becoming very popular, may present some dangers for those who use their services. Who do you think uses Internet dating services? What, if anything, should dating services do to protect their clients

What employers are looking for attributes of professionalism : Fill the 7 attributes above with examples. Cross reference the 6 items what employers are looking for above with the 7 attributes of professionalism.

Find the amount of discrepancy the speaker : Find the amount of discrepancy the speaker should aim for to maximize the attitude change in the audience.

Balanced binary search tree of height : Write a function to generate a perfectly balanced binary search tree of height h with keys 1 through 2h+1 - 1. What is the running time of your function?

Design a recursive linear-time algorithm : 1. Design a recursive linear-time algorithm that tests whether a binary tree satis?es the search tree order property at every node. 2. Write a recursive function that takes a pointer to the root node of a tree T and returns a pointer to the root node..

Avl trees and unbalanced binary search trees : Write a program to perform random operations on splay trees. Count the total number of rotations performed over the sequence. How does the running time compare to AVL trees and unbalanced binary search trees?

What is a likely investment it would consider and why : Evaluate the approximate costs and benefits of the investment you identified, explaining how these would affect your spreadsheet projections and business decisions

Implement avl single and double rotations : 1. Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree. 2. Keys 1, 2, ... , 2k - 1 are inserted in order into an initially empty AVL tree. Prove that the resulting tree is perfectly balanced. 3. Write the remaining pr..

User Account

All Pages