Project #40638 - Binary Trees

QUESTION 2 QUESION 2 QUESTION 2 QUESTION 2 QUESTION 2

Balancing Binary Search Trees

1. Project Specification

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 ACE value is defined (Wiener and Pinson) as the Average Comparison 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)
}
ACE = sum / n

When the average comparison effort (i.e. the ACE 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 MinACE as the minimum value of ACE and MaxACE as the maximum value of ACE. MinACE value for a BST with n nodes, corresponds to the ACE value calculated for a BST of height floor(log n) + 1 which has all levels completely full, except for the last level. ACE value of a balanced BST equals MinACEMaxACE value for a BST with n nodes corresponds to the ACE value calculated for a BST which degenerates into a linear linked list with n nodes.

Part 1
Consider the file BST.java (a link to this file is provided below for downloading purposes) which defines a generic Binary Search Tree class.

Enhance the BST class with the following methods for executing experiments of balancing binary search trees.

• treeHeight, calculates tree height;
• nodeBalanceLevel calculates the balance level of a given node as the difference between the height of its left subtree and the height of its right subtree
• numberOfNodesAtLevel calculates the number of nodes at the specified level
• calculateACE, calculates the ACE value according to the above algorithm;
• calculateMinACE, calculates the minimum value of the ACE;
• calculateMaxACE, calculates the maximum value of the ACE;
• needsBalancing, evaluates whether this BST needs to be balanced or not. We consider that a BST needs to be balanced when its ACE value is greater than K * MinASE where K = 1.3;
• balanceBST, executes the balance operation on this BST;

Additional methods may be added if necessary.
The enhanced BST class should compile without errors.

Part 2
Design and implement a driver program TestBST 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 values taken from an input file. In the input file, the 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) pre-order tree traversal, (3) calculateACE, (4) calculateMinACE, (5) calculateMaxACE, (6) numberOfNodesAllLevels (this method displays the number of nodes at all levels of the tree), (7) treeHeight, (8) nodeBalanceLevel (9) needsBalancing, (10) balanceBST, (11) insert 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 values of the tree nodes should be shown to the console or, as a result of executing the calculateACE method, the ACE value should be displayed to the console.

Notes
1. If an operation requires additional information, the user will be prompted to enter it.
2. The input file (a simple .txt file) should be generated by the students using a simple text editor such as Notepad.
3. You may assume that there are no errors in the input file structure.
4. Tree root is considered as located at level 0. Tree height will be considered by counting the nodes, starting with the root, along the longest path.

2. Submission Requirements

Submit the following before the due date listed in the Calendar:

1. All .java source files and the input file.
2. A document file including relevant screenshots showing program execution as a result of test cases.
3. A document file describing your solution which should include the following elements: (3.1) a short problem analysis, (3.2) main design decisions, (3.3) assumptions, (3.4) short description of classes, (3.5) user interface, (3.6) test plan, (3.7) error handling, (3.8) lessons learned and (3.9) possible future developments. The size of the document should be of 3 pages, single spaced, font size 12.

 Subject Computer Due By (Pacific Time) 09/24/2014 12:00 am
TutorRating
pallavi

Chat Now!

out of 1971 reviews
amosmm

Chat Now!

out of 766 reviews
PhyzKyd

Chat Now!

out of 1164 reviews
rajdeep77

Chat Now!

out of 721 reviews
sctys

Chat Now!

out of 1600 reviews

Chat Now!

out of 770 reviews
topnotcher

Chat Now!

out of 766 reviews
XXXIAO

Chat Now!

out of 680 reviews