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

Define the term - array, Define the term - Array A fixed length, ord... Define the term - Array A fixed length, ordered collection of values of same type stored in contiguous memory locations; collection may be ordered in several dimensions.

Algorithm to merge two sorted arrays with third array, Q. Write down an alg... Q. Write down an algorithm to merge the two sorted arrays into the third array. Do  not perform the sort function in the third array.                           Ans: void m

Explain arrays, Arrays :- To execute a stack we need a variable called top,... Arrays :- To execute a stack we need a variable called top, that holds the index of the top element of stack and an array to hold the part of the stack.

Quicksort and bubble sort algorithms, Task If quicksort is so quick, w... Task If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter, why are there so many sorting algorithms? Your

Program for linear search, Program for Linear Search. Program: Linear S... Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

Flowchart, create a flowchart that displays the students average score for ... create a flowchart that displays the students average score for these quizzes

Procedure of analysis of algorithm, Example 1:  Following are Simple sequen... Example 1:  Following are Simple sequence of statements Statement 1;  Statement 2; ... ... Statement k; The entire time can be found out through adding the times for

Example of binary search, Let us assume a file of 5 records that means n = ... Let us assume a file of 5 records that means n = 5 And k is a sorted array of keys of those 5 records. Let key = 55, low = 0, high = 4 Iteration 1: mid = (0+4)/2 = 2

File organization, Define File organization''s and it''s types Define File organization''s and it''s types

Determine the effect of ruby in implementation of string, Determine the eff... Determine the effect of Ruby in implementation of string Ruby has a String class whose instances are mutable sequences of Unicode characters. Symbol class instances are charact