Design a binary search tree, Data Structure & Algorithms

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 106.)
  • 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 106.)
  • 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







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
Related Questions
#questionalgorithm for implementing multiple\e queues in a single dimensional array

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

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

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

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 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 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 Carrier set of the Integer ADT is the set {..., -2, -1, 0, 1, 2, ...}, and  operations on these values are addition, multiplication, subtrac

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

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