Evaluating the Performance of Binary Search Tree The major advantage of binary search trees over other data structures is that the related sorting algorithms, search algorithms, insertion, and deletion can be very efficient when balanced. A binary search tree is an appropriate structure for many of the same applications discussed previously in conjunction with other collection structures, especially those providing sorted lists. The special advantage of using a binary search tree is that it facilitates searching while conferring the benefits of linking the elements. It provides the best features of both the sorted array-based list and the linked list. Similar to a sorted array-based list, it can be searched quickly, using a binary search. Similar to a linked list, it allows insertions and removals without having to move large amounts of data. Thus, a binary search tree is particularly well suited for applications in which processing time to insert, add and delete must be minimized. However, all aforementioned advantages are completed depend on how a tree was created. For example, in a balanced BST with N nodes, its minimum height is O(log n), it takes at maximum O(log n) comparisons to find a particular node. However, in the worst-case scenario, it takes up to O(n) comparisons to find a particular node. The following table summarizes the number of Nodes, height, and the number of comparisons to search a particular node in a balanced tree and the worst case. Example of Searching a Node in a Balanced Tree and the Worst Case Number of Nodes Height of the Tree Number of Comparisons Balanced Tree Worst Case Balanced Tree Worst Case 3 1 3 2 3 7 2 7 3 7 1024 9 1024 10 1024 4096 11 4096 12 4096 Your Tasks: For this assignment, you are required to design experiments to evaluate the relationship between BST tree height (h) and the number of comparisons to find a particular node in a tree.
I need help with this Java problem to output as it's explained in the image below:
public class BST {
private Node root;
public void insert(int data) {
root = insertRec(root, data);
}
private Node insertRec(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
if (data < root.data) {
root.left = insertRec(root.left, data);
} else if (data > root.data) {
root.right = insertRec(root.right, data);
}
return root;
}
public int getHeight() {
return getHeightRec(root);
}
private int getHeightRec(Node root) {
if (root == null) {
return 0;
} else {
int leftHeight = getHeightRec(root.left);
int rightHeight = getHeightRec(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
public int search(int data) {
return searchRec(root, data, 0);
}
private int searchRec(Node root, int data, int comparisons) {
comparisons++;
if (root == null) {
return comparisons;
}
if (root.data == data) {
return comparisons;
}
if (root.data > data) {
return searchRec(root.left, data, comparisons);
}
return searchRec(root.right, data, comparisons);
}
}
(Edit MyIntBSTTree. java)
/**
*
*
* MyIntBSTTree.txt: the template file of MyIntBSTTree.java
* Student tasks: implement tasks #1 and #2 as specified in this file
*/
import java.util.*;
public class MyIntBSTTree{
private Node root;
public MyIntBSTTree(){
root=null;
}
public int height(){
// *** Student task ***
/* Requirements:
The height of a binary tree is the largest number of edges in a path from the root node to a leaf node.
Essentially, it is the height of the root node. Note that if a tree has only one node, then that node
is at the same time the root node and the only leaf node, so the height of the tree is 0, similary,
the height of a tree with only two nodes is 1. Implement this method to return height of the tree
*** Enter your code below ***
*/
}
public int comparisons(Node node){
// *** Student task ***
/* Requirements:
Count and return how many comparisons performed to search for the argument node
*** Enter your code below ***
*/
}
public int comparisons(int val){
// *** Student task ***
/* Requirements:
Overloaded method - Count and return how many comparisons performed to search for the node whose data equals the argument val.
*** Enter your code below ***
*/
}
public MyIntBSTTree buildBalancedTree(){
// *** Student task ***
/* Requirements:
This method builds a balanced tree with values from the int arr and returns the new tree.
The original tree remains unchanged after calling this method.
*** Enter your code below ***
*/
}
public MyIntBSTTree buildWorstTree(){
// *** Student task ***
/* Requirements:
Build and return a tree whose height is arr.length - 1
The original tree remains unchanged after calling this method.
*** Enter your code below ***
*/
}
// **** DO NOT MODIFY CODE BEYOND THIS POINT ***
public Node getRoot(){
return root;
}
public void add(int data) {
root = addHelper(root, data);
}
private Node addHelper(Node node, int data) {//add node helper
if (node == null){
node = new Node(data);
}else if (data <= node.getData()){
node.setLeft(addHelper(node.getLeft(), data));
}else{
node.setRight(addHelper(node.getRight(), data));//System.out.println(data);
}
return node;
}
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
