Balancing Binary Search Trees

Closed Posted Nov 27, 2013 Paid on delivery
Closed Paid on delivery

The search effort for locating a node in a Binary Search Tree (BST) depends on the tree shape (topology). For a BST with n nodes the ASE value is defined (Wiener and Pinson) as the Average Search Effort for locating a node in a tree by summing all comparison operations for all tree nodes and dividing the result by the total number of tree nodes:

for (int level = 0, sum = 0; level < treeHeight; level++ ) {

sum += numberOfNodesAtLevel(level) * (level + 1)

}

ASE = sum / n

When the average search effort (i.e. the ASE value) gets over a certain threshold or after a certain number of tree insert/delete operations, for optimizing the search process, a tree balance operation should be executed resulting a tree whose height equals |_ log n _| + 1 (or floor(log n) + 1), thus requiring at most |_ log n _| + 1 (or floor(log n) + 1) comparison operations to identify any tree node.

For a given BST with n nodes we define MinASE as the minimum value of ASE and MaxASE as the maximum value of ASE. MinASE value for a BST with n nodes, corresponds to the ASE value calculated for a BST of height floor(log n) + 1 which has all levels completely full, except for the last level. For a balanced BST, its ASE value equals MinASE. MaxASE value for a BST with n nodes represents the ASE value calculated for a BST which degenerates into a linear linked list with n nodes.

For the BST class (Liang, Listing 27.5), design and implement the methods indicated below and integrate them into the existing class. Compile the BST class with the new added methods.

calculateASE, calculates the ASE value according to the above algorithm;

calculateMinASE, calculates the minimum value of the ASE;

calculateMaxASE, calculates the maximum value of the ASE;

calculateTreeHeight, calculates tree height;

needsBalancing, evaluates whether this BST needs to be balanced or not. We consider that a BST needs to be balanced when its ASE value is less than greater than K * MinASE where K = 1.25;

balanceBST, executes the balance operation on this BST; 1



Design and implement a driver program [url removed, login to view] and the test cases for testing the methods implemented in Part 1. The driver program should build an initial BST whose nodes contain positive integer key values taken from an input file. In the input file, the key values should be separated by the semicolon character. After building the BST, in a loop, the program should invite the user to select for execution one of the following operations:

1) in-order tree traversal,

2) post-order tree traversal,

3) calculateASE,

4)calculateMinASE,

5)calculateMaxASE,

6)calculateTreeHeight,

7) needsBalancing,

8) balanceBST,

9) insert new value, and

0) exit the loop and the program.

As a result of each operation execution, relevant information will be displayed to the user (for example, as a result of executing the in-order traversal, the key values of the tree nodes should be shown to the console or, as a result of executing the calculateASE method, the ASE value should be displayed to the console).

Additional (housekeeping) methods such as calculating the number of nodes at a certain level in the tree may be necessary to be defined.

If an operation requires additional information, the user will be prompted to enter it.

You may assume that there are no errors in the input file structure.

Deliverables

All .java source files and the data input file.

A document file describing solution. The solution description document should include the following elements: a short problem analysis, main design decisions, assumptions, description of classes, user interface, testing and test cases, error handling, results discussion and lessons learned.

This program is due by November 30, 2013 COB.

Java

Project ID: #5173146

About the project

13 proposals Remote project Active Jan 3, 2014

13 freelancers are bidding on average $119 for this job

dobreiiita

Hello, I am Java expert and can surely help you with this project, I have gone through the description and I'm comfortable with all requirements, Please communicate to discuss further. Thank You

$100 USD in 2 days
(207 Reviews)
6.7
it2051229

Hi, I am placing my bid on your project because I have read the requirements and I am confident enough with my Java and algorithm skills. I am focused mostly on doing computer science homework here in freelancer.com an More

$50 USD in 0 days
(238 Reviews)
6.4
gypsicoder

Very much interest about this project. I can complete tasks within 2 days. Ready to start. Waiting to hear from you. Regards, Bishnu 3rd Eye Lab

$111 USD in 2 days
(25 Reviews)
4.8
iit2009013

Hi! I am proficient in Java, I can complete this task for you. I will provide perfect implementations of all these tree methods.

$200 USD in 5 days
(10 Reviews)
4.5
CodingWhiz

Implementing a BST data structure (and the associated operations) is a trivial task for any developer. I can deliver on schedule, with clean and thoroughly commented code and a well-written solution document. Regard More

$45 USD in 3 days
(6 Reviews)
4.0
C0RETECHIES

Hello Sir, I am very good at BST. I have gone through your project requirements and we have highly skilled and qualified team who own all the right credentials to execute this job in a very proficient manner as per y More

$206 USD in 3 days
(1 Review)
3.1
nishants01

Hey, I can get this done for you in a couple of days. I've been programming in java since the past six years and I'm a computer science graduate student having done data structures research work in the past. Please More

$45 USD in 1 day
(5 Reviews)
2.6
niloybaidya

https://www.freelancer.com/u/xcodechai.html you can check our freelancer profile 5/5 with 100% complete rate here have a little company too ,.... We provide you industry standard Mobile Apps, Software, Desktop Apps, We More

$155 USD in 7 days
(0 Reviews)
0.0
jindal89

Hi, I have 5 years of java experience. I am very good in data structures and algorithms too. Thanks,

$144 USD in 3 days
(0 Reviews)
0.0
fabiomenza

Hi, I've already coded BST for my Algorithms course and I have 6 years experience in Java and TDD. I think I can handle this job for just 80$ in about a week. Let me know if you're interested, Fabio

$80 USD in 6 days
(0 Reviews)
0.0
codelangthang

I ever do the Balancing Binary Tree and show all the images of tree when the node is inserted or removed. I mean all operator of tree can visible on screen.

$150 USD in 5 days
(0 Reviews)
0.0