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

Multiple queue, #questionalgorithm for implementing multiple\e queues in a ... #questionalgorithm for implementing multiple\e queues in a single dimensional array

Total impedent of the circuit, an electrical student designed a circuit in... an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Direct file organisation, It offers an effective way to organize data while... It offers an effective way to organize data while there is a requirement to access individual records directly. To access a record directly (or random access) a relationship is

Trees, What is AVL Tree? Describe the method of Deletion of a node from and... What is AVL Tree? Describe the method of Deletion of a node from and AVL Tree ?

Recursive implementation of binary tree traversals, There are three typical... There are three typical ways of recursively traversing a binary tree. In each of these, the left sub-trees & right sub-trees are visited recursively and the distinguishing feature

Enumerate the types in ruby, Enumerate the Types in Ruby Ruby is a pure... Enumerate the Types in Ruby Ruby is a pure object-oriented language, meaning that all types in Ruby are classes, and each value in a Ruby program is an instance of a class. Thi

Explain th term input and output- pseudocode, Explain th term input and ou... Explain th term input and output-  Pseudocode Input and output indicated by the use of terms input number, print total, output total, print "result is" x and so on.

State in detail about the integer, State in detail about the Integer ... State in detail about the Integer Carrier set of the Integer ADT is the set {..., -2, -1, 0, 1, 2, ...}, and  operations on these values are addition, multiplication, subtrac

Draw a b-tree., Q. Draw a B-tree of order 3 for the sequence of keys writte... Q. Draw a B-tree of order 3 for the sequence of keys written below: 2, 4, 9, 8, 7, 6, 3, 1, 5, 10

Insertion of a node into an avl tree, Initially Nodes are inserted in an AV... Initially Nodes are inserted in an AVL tree in the same manner as an ordinary binary search tree. Though, the insertion algorithm for any AVL tree travels back along with the pa