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
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].

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

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

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 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 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 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

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

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

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