Show Bid Request
Binary Search Tree Exploration
Bid Request Id: 26982
|
|
|
|
Posted by: |
seatiger74 (25 ratings)
(Software buyer rating 10 )
|
|
Non-action Ratio: |
Very Good - 3%
|
|
Posted: |
Sep 10, 2002
12:04:54 AM EDT
|
|
Bidding Closes: |
Sep 14, 2002
12:15:54 AM EDT
|
|
Viewed (by coders): |
293 times
|
|
Deadline: |
9/15/2002
TIME EXPIRED
|
|
|
|
|
Description:
Implement code to do basic binary search tree manipulations,including insert, traverse, delete, and so on. You may use what the author (Weiss) has in Chapter 4; in fact, be sure to adapt what Weiss has (as closely as you can) for Remove on page
138.
Now, Weiss mentions that the code for Remove is inefficient,in that when removing a node with 2 children, it first finds the minimum node in the subtree to the right, then uses Remove to
delete that node (which first 'finds' it again). Replace that section with a call to RemoveMin (which you must write) that does the job with just one trip down the tree.
Part I:
To test your code (on a tree of integers), first insert the values
42 10 74 5 16 100 12 14 15 30 32
in that order.
After that, do the following pseudo-code:
while the tree is not empty
{
remove next node (that is, keep a list of the nodes that are left, and delete them one by one)
traverse the tree
print a line of **************** (so we can keep things separate)
}
However, make sure that the FIRST node you remove is 10. This is a node with 2 children, which forces RemoveMin to get called.All of this is to show that your code actually works!
Part II:
Add a height function, that computes the height of a BST. Now, as we know a binary search tree can behave badly in terms of height; in the worst case it can have height = number of nodes and be just a linked list! Here, we want to explore what is the average height of a randomly generated BST. To this
end, generate 100 BST's with 4,096 randomly generated integer values each and print the average height of all 100 trees. Note the following: the usual recursive tree height function will take a LONG time to compute the height of these trees. You should consider an alternative approach for computing the height that will be much faster.
Part III:
If we insert an array of integers into a BST and then traverse the tree in order, we will have sorted the array. Setup a randomly generated array of
262,144 integers and insert them into a previously empty BST. CPU time this process (see how below). Also sort the array using qsort and time that as
well. Print out both elapsed times and label the output. You need not print the sorted array or traverse the tree (but you might do so for yourself prior to turning it in). Note: qsort can be tricky to use correctly if you haven't done it before;(continue on next avaiable window)......
Deliverables:
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.
2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request.
3) Complete ownership and distribution copyrights to all work purchased.
Platform:
(continue from DESCRIPTION page)look it up and test it out on a small array to make sure you
understand it. Note: if you are working under Windows, and you want yourbarray of size 262144 to be local rather than global, you will need to set
up a pointer to it and allocate it on the heap; otherwise just put int u[262144];
as global. The problem is that Win32 sets up a default stack of 1 megabyte. So a local declaration of int u[262144] in main() overflows the
stack immediately and your program crashes. Another superiority of
Linux :-)
CPU Timing (for C and C++):
You will need to include stdlib.h and time.h to use this.
(That's cstdlib and ctime in newer C++ compilers)
...
double start, elap;
start = clock();
(task to be timed goes here)
elap = (clock() - start) / CLOCKS_PER_SEC;
Now, elap will be the elapsed time (in seconds) -- I would normally print this out to 2 decimal places.
Note: PLEASE WRITE THIS PROGRAM IN C++ . I use the Visual C++ 6.0 to run it
Must be 100% finished and received by buyer on:
Sep 15, 2002 EDT
Deadline legal notes: All times are expressed in the time zone of the site EDT (UT - 5). If the buyer omitted a time, then the deadline is 11:59:59 PM EDT on the indicated date.
Special Conditions / Other:
please send the codes ontime
Remember that contacting the other party outside of the site (by email, phone, etc.) on all business projects < $500 (before the buyer's money is escrowed) is a violation of both the software buyer and seller agreements.
We monitor all site activity for such violations and can instantly expel transgressers on the spot, so we thank you in advance for your cooperation.
If you notice a violation please help out the site and report it. Thanks for your help.
|
|
|
Bidding/Comments:
|
All monetary amounts on the site are in United States dollars.
Rent a Coder is a closed auction, so coders can only see their own bids and comments. Buyers can view every posting made on their bid requests. |
See all rejected bids (and all comments)
| Name |
Bid Amount
|
Date |
Coder Rating |
|
|
This bid was accepted by the buyer!
|
$15 (USD)
|
Sep 10, 2002
12:21:12 PM EDT
|
10
(Excellent)
|
|
|
Hi DT!
I have Binary Search Tree class half ready. I will go through task one more time this evening and ask any questions i may have. I may need page from the book you've mentioned because I don't think I have it here. I will try to find book today and contact you later.
The program will be ready by Thursday 9/12 evening (around 10pm CT).
I cut price down just as I've promized you last time.
Sincerely yours,
Paul
|
|
|
|
|
|
|
