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. Let X = (X1, X2, X3,....Xn) and Y= (Y1, Y2, Y3,....Xm) be the two linked lists respectively. Write down an algorithm to merge the lists together to get the linked list Z such th

Q. Give the algorithm for the selection sort. Describe the behaviours of selection sort when the input given is already sorted.

Given are the definitions of some important terms: 1) Field: This is an elementary data item characterized by its size, length and type. For instance, Name

Hear is given a set of input representing the nodes of a binary tree, write a non recursive algorithm that must be able to give the output in three traversal orders. Write down an

how to write a function of area of a circle using python

Phong Shading Phong shading too is based on interpolation, but instead of interpolating the colour value, it is the normal vector, which is interpolated for each point and a co

Q. Write down an algorithm to sort a given list by making use of Quick sort method. Describe the behaviour of Quick sort when input given to us is already sorted.

write a COBOL program to find the biggest of two numbers

Describe Binary Search Tree (BST)? Make a BST for the given sequence of numbers. 45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48 Traverse the obtained tree in Preorder, Inord

An interesting application or implementation of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can depict the sequence of possible moves