Binary Search Tree usage:

Write a program to compare the time taken for a search in a skewed tree, a balanced tree, and a random tree. Specically, your program should do the following.

• Input an integer x. (Should work with big numbers, such as 10⁶.)
• Create a completely-skewed binary search tree S containing 1; 2; : : : ; x.
• Create a completely-balanced binary search tree B containing the same numbers. (You can use the same idea of the level-order method to insert the numbers in the order needed to obtain the tree balanced.)
• Create a binary search tree R containing x integers generated at random. (To minimize the risk of repetitions, you can multiply the value returned by random() by 10⁶.)
• Search for a leaf in S and B, and for a new random number in R, and show the time taken for each search in the screen.

 

Posted Date: 2/12/2013 4:29:09 AM | Location : United States

Ask an Expert

Related Discussions:- Design a binary search tree, Assignment Help, Ask Question on Design a binary search tree, Get Answer, Expert's Help, Design a binary search tree Discussions

Write discussion on Design a binary search tree
Your posts are moderated

Write your message here..

Related Questions

Linear array - numerical, Q. A linear array A is given with lower bound as ... Q. A linear array A is given with lower bound as 1. If address of A[25] is 375 and A[30] is 390, then find address of A[16].

Various passes of bubble sort, Q. Show the various passes of bubble sort on... Q. Show the various passes of bubble sort on the unsorted given list 11, 15, 2, 13, 6           Ans: The given data is as follows:- Pass 1:-     11   15   2     13

Insertion into a red-black tree, The insertion procedure in a red-black tre... The insertion procedure in a red-black tree is similar to a binary search tree i.e., the insertion proceeds in a similar manner but after insertion of nodes x into the tree T, we c

Java, Ask consider the file name cars.text each line in the file contains i... Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

Difference between prism''s and kruskal''s algorithm, Difference among Pris... Difference among Prism's and Kruskal's Algorithm In Kruskal's algorithm, the set A is a forest. The safe edge added to A is always a least-weight edge in the paragraph that lin

Explain division method, Explain Division Method Division Method: - In... Explain Division Method Division Method: - In this method, key K to be mapped into single of the m states in the hash table is divided by m and the remainder of this division

What is an algorithm, What is an algorithm?  What are the characteristics o... What is an algorithm?  What are the characteristics of a good algorithm? An algorithm is "a step-by-step process for accomplishing some task'' An algorithm can be given in many

Train reorganising, A freight train from Melbourne is approaching Sydney, c... A freight train from Melbourne is approaching Sydney, carrying n cars of cargos. The cargos are to be delivered to n different cities in the metropolitan area of Sydney - one car f

An algorithm to insert a node in beginning of linked list, Q. Write down an... Q. Write down an algorithm to insert a node in the beginning of the linked list.                         Ans: /* structure containing a link part and link part

Threads in main method, Create main method or a test class that creates 2 E... Create main method or a test class that creates 2 Element objects that are neighbours of each other, the first element temperature set at 100, the 2nd at 0 and use an appropriate h