Find Jobs
Hire Freelancers

Binary Search Tree Exploration

$30-5000 USD

完了済み
投稿日: 21年以上前

$30-5000 USD

完了時にお支払い
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 [login to view URL] 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 ## Deadline information please send the codes ontime
プロジェクト ID: 2869827

プロジェクトについて

16個の提案
リモートプロジェクト
アクティブ 22年前

お金を稼ぎたいですか?

Freelancerで入札する利点

予算と期間を設定してください
仕事で報酬を得る
提案をご説明ください
登録して仕事に入札するのは無料です
アワード者:
ユーザーアバター
See private message.
$12 USD 14日以内
5.0 (33 レビュー)
4.0
4.0
この仕事に16人のフリーランサーが、平均$21 USDで入札しています
ユーザーアバター
See private message.
$34 USD 14日以内
4.4 (72 レビュー)
5.5
5.5
ユーザーアバター
See private message.
$29.75 USD 14日以内
5.0 (78 レビュー)
5.2
5.2
ユーザーアバター
See private message.
$19.55 USD 14日以内
5.0 (47 レビュー)
4.5
4.5
ユーザーアバター
See private message.
$21.25 USD 14日以内
4.6 (60 レビュー)
4.5
4.5
ユーザーアバター
See private message.
$11.05 USD 14日以内
4.8 (62 レビュー)
4.2
4.2
ユーザーアバター
See private message.
$11.90 USD 14日以内
4.9 (17 レビュー)
3.3
3.3
ユーザーアバター
See private message.
$21.25 USD 14日以内
5.0 (53 レビュー)
3.3
3.3
ユーザーアバター
See private message.
$42.50 USD 14日以内
5.0 (2 レビュー)
2.9
2.9
ユーザーアバター
See private message.
$17 USD 14日以内
5.0 (7 レビュー)
2.6
2.6
ユーザーアバター
See private message.
$7.65 USD 14日以内
4.9 (5 レビュー)
1.8
1.8
ユーザーアバター
See private message.
$21.25 USD 14日以内
5.0 (3 レビュー)
1.8
1.8
ユーザーアバター
See private message.
$21.25 USD 14日以内
4.9 (6 レビュー)
1.1
1.1
ユーザーアバター
See private message.
$8.50 USD 14日以内
5.0 (2 レビュー)
0.9
0.9
ユーザーアバター
See private message.
$42.50 USD 14日以内
0.0 (0 レビュー)
0.0
0.0
ユーザーアバター
See private message.
$8.50 USD 14日以内
0.0 (0 レビュー)
0.0
0.0

クライアントについて

UNITED STATESのフラグ
United States
5.0
25
メンバー登録日:9月 16, 2001

クライアント確認

ありがとうございます!無料クレジットを受け取るリンクをメールしました。
メールを送信中に問題が発生しました。もう一度お試しください。
登録ユーザー 投稿された仕事の合計
Freelancer ® is a registered Trademark of Freelancer Technology Pty Limited (ACN 142 189 759)
Copyright © 2024 Freelancer Technology Pty Limited (ACN 142 189 759)
プレビューを読み込み中
位置情報へのアクセスが許可されました。
あなたのログインセッションの有効期限がきれ、ログアウトされました。もう一度ログインしてください。