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
explain collision resloving techniques in hasing

Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

: Write an algorithm to evaluate a postfix expression. Execute your algorithm using the following postfix expression as your input: a b + c d +*f ­ .

Q. Explain the basic concept of the primitive data structures.                                             Ans. The concept of P r i m i t i ve Data

Explain in brief about the Container An entity which holds finitely many other entities. Just as containers such as boxes, baskets, bags, pails, cans, drawers, and so for

Algo rithm to Insert a Node p at the End of a Linked List is explained below Step1:   [check for space] If new1= NULL output "OVERFLOW" And exit Step2:   [Allocate fr

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 mission (sho

The objective analysis of an algorithm is to determine its efficiency. Efficiency is based on the resources which are used by the algorithm. For instance, CPU utilization (Ti

Programming for hash table?

Implementation of queue using a singly linked list: While implementing a queue as a single liked list, a queue q consists of a list and two pointers, q.front and q.rear.