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
Program: Creation of a linked list In the next example, wewill look to the process of addition of new nodes to the list with the function create_list(). #include #includ

1. Use the Weierstrass condition, find the (Strongly) minimizing curve and the value of J min for the cases where x(1) = 0, x(2) = 3. 2. The system = x 1 + 2u; where

need an expert to help me with the assignment

A common person's faith is that a computer can do anything. It is far from truth. In realism computer can carry out only definite predefined instructions. The formal illustration o

What do you mean by hash clash? Hashing is not perfect. Occasionally, a collision occurs when two different keys hash into the same hash value and are assigned to the same arra

1. Apply the variant Breadth-First Search algorithm as shown in Figure 2 to the attached graph. This variant is used for computing the shortest distance to each vertex from the sta

Following are some of the drawback of sequential file organisation: Updates are not simply accommodated. By definition, random access is impossible. All records should be

Ruby implements Range of T Abstract data type Ruby implements Range of T ADT in its Range class. Elements of carrier set are represented in Range instances by recording interna

Q1. Define the following terms: (i) Abstract data type. (ii) Column major ordering for arrays. (iii)  Row major ordering for arrays. Q2. Explain the following: (i) A

We would like to implement a 2-4Tree containing distinct integer keys. This 2-4Tree is defined by the ArrayList Nodes of all the 2-4Nodes in the tree and the special 2-4Node Root w