Design a binary search tree, Data Structure & Algorithms

Assignment Help:

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. Specically, 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.

Related Discussions:- Design a binary search tree

Maximum degree of any vertex in a simple graph, The maximum degree of any v...

The maximum degree of any vertex in a simple graph with n vertices is (n-1) is the maximum degree of the vertex in a simple graph.

Explain critical path and chain, 1. Using the traditional method of CPM: ...

1. Using the traditional method of CPM: a. What activities are on the critical path? b. What is the expected total lead time of the project? 2. Using CCPM: a. What

ALGORITHM AND TRACING, WRITE AN ALGORITHM TO CONVERT PARENTHIZED INFIX TO P...

WRITE AN ALGORITHM TO CONVERT PARENTHIZED INFIX TO POSTFIX FORM ALSO TRACE ALG ON ((A+B)*C-(D-E)$F+G)

Advanced data structures - splay trees, This is a unit of which targeted on...

This is a unit of which targeted on the emerging data structures. Red- Black trees, Splay trees, AA-trees & Treaps are introduced. The learner must explore the possibilities of app

Array implementation of lists, In the array implementation of the lists, we...

In the array implementation of the lists, we will use the array to hold the entries and a separate counter to keep track of the number of positions are occupied. A structure will b

Four applications or implementation of the stack, Q. Write down any four ap...

Q. Write down any four applications or implementation of the stack. Ans. (i) The Conversion of infix to postfix form (ii)

Doubly linked list, code for count and display

code for count and display

Define approximating smooth surfaces with polygon nets, Approximating smoot...

Approximating smooth surfaces with Polygon nets Networks of polygons are used to represent smooth surfaces. They are, of course, only an approximation to the true surface, but

Explain about greedy technique, Explain about greedy technique The gre...

Explain about greedy technique The greedy method suggests constructing a solution to an optimization problem by a sequence of steps, every expanding a partially c

Data flow diagrams, How to construct a data flow diagram for a college assi...

How to construct a data flow diagram for a college assignment and marking systemA

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages