Consider the following list of integers: In this example, the root will be (array position 5) and the value of 6. Keep in mind that positions in the array begin at 0. If the search term were entered to be 2, then the midpoint would be selected which we would determine with the following formula: midpoint = length of array /2 Since the length is 11, the midpoint is position 5. We would then compare the search term 3 to the value in position 5 and since 3 < 6 the search will continue on the left side of the tree structure. We would repeat the process. With the following formula: newbranch = current position / 2 The new length of the array is the left side of the tree up to the root which is 5. This new formula would yield position 2 which is the value 3. Since our search value is 2, it is less than the new branch of the tree meaning that our search value must be on the left of this branch. We repeat this process one more time: newbranch = = current position / 2 The current position is 2 so the new index position will be 1 which contains the value of 2. Our search term is 2 and the value in the new position is also 2 meaning that we have found the value we were looking for. In this case our algorithm required 3 iterations to find the search term. The following code details the algorithm for the preceding example. You can use this code to further understand binary tree implementations and leverage some of the techniques that are supported within Jeliot, however, you cannot use this code as the basis for your assignment. // // Example of an array based implementation of a binary search developed in the Jeliot tool // import Prog1Tools.IOTools; import java.util.*; public class binarySearchTree public static void main (String] args) { int iterations; // This variable counts the number of iterations of search that occur int index; // This variable identifies the node of the tree currently being searched int prev; // This variable will be used to keep track of the 'range' of the branch int searchValue; // This variable will contain the value we are searching for // // In this example we are using an array implementation of a binary tree and the array // is being pre-populated with the integers in the tree in the correct sequence. // in your assignment you must populate your binary tree by accepting values // from the user and populating a structure in the proper sequence using either // an array or linked list implementation // int bTree[] = {1,2,3,4,6,7,8,9,10,12,13,14,15,16,17,18,19,20,21,23,24,25,26,27,2 8, 29,30,33,34,35,36,37,38,39,40 }; %3D // // Using Jeliot, you can use the System.out.printin method to output information // to the console. // System.out.printin("Enter an integer between 1 and 40 to search for:"); // // Using Jeliot, you must use the scanner class to get input from the user as // illustrated below. // Scanner in = new Scanner(System.in); in.nextInt(); searchValue = iterations=1; // // In this section we set the initial midpoint of the array which is the root value // index=bTree.length /2; prev=bTree.length; // // Here we call the binary search method which is designed to recursively // search until the proper value has been found // binarySearch(bTree, index, prev, searchValue, iterations); } public static void binarySearch(int[] bTree, int index, int prev, int searchValue, int iterations) { // // If our search value is smaller then the current position then // we need to search the left branch of the tree. The index value // indicates the current node that is being compared with the search value // the prev value is used to help identify the width of the current branch /l so that we can identify the next branch to follow down. // if (bTreeſindex] < searchValue) { index = (prev-index)/2+index; iterations++; binarySearch(bTree, index, prev, searchValue, iterations); } // // If our search value is larger than the current position then // we need to search the right branch of the tree. Note that in each // iteration of the search we recursively call binarySearch which searches // the next level down in the tree. // else if (bTree[index] > searchValue ) { prev = index; index = index / 2; iterations++; binarySearch(bTree, index, prev, searchValue, iterations); } // // When the search value is found, print the number of iterations the search // took to the console and exit the binarySearch method // else { System.out.printIn("Found search value in:"+iterations+" iterations"); return; } } } In the preceding example, the tree values were created in sequence meaning that the array was populated with values in order. Your algorithm must be able to accommodate values entered in any sequence which means that you must be able to adjust the structure of the tree as the root value and other values change. In the example above, we have an array that forms the basis of our binary search tree. We determine the root by looking midway through the array. The example above has an advantage in that the array is already in sorted order. In your algorithm you will not have that advantage. When you have completed your algorithm and your Asymptotic analysis of your algorithm please run it several times within Jeliot and observe the results. Use the following values for both the contents of the binary search tree and the search value: Integers to add to binary search tree: 10, 5, 12, 3, 1, 13, 7, 2, 4, 14, 9, 8, 6, 11 Search value: 9 Is the time (expressed in the number of iterations required to complete a search) consistent with your Asymptotic analysis in worst case (Big O)? As part of your assignment, you must submit both a description of the assignment and how your algorithm works including an Asymptotic analysis of your algorithm. Your analysis must include the efficiency of your algorithm expressed in Big Oh notation. The scope of your asymptotic analysis should only include the binary search portion of your assignment. Further, as part of your assignment, you must include the code of your algorithm. All of these elements of this assignment must be completed and posted to the assignment for Unit 4 by the end of the week for unit 4. Finally, you must include a screen shot or other capture of the output of you binary search tree that indicates the number of iterations that were required to find the search value.
Consider the following list of integers: In this example, the root will be (array position 5) and the value of 6. Keep in mind that positions in the array begin at 0. If the search term were entered to be 2, then the midpoint would be selected which we would determine with the following formula: midpoint = length of array /2 Since the length is 11, the midpoint is position 5. We would then compare the search term 3 to the value in position 5 and since 3 < 6 the search will continue on the left side of the tree structure. We would repeat the process. With the following formula: newbranch = current position / 2 The new length of the array is the left side of the tree up to the root which is 5. This new formula would yield position 2 which is the value 3. Since our search value is 2, it is less than the new branch of the tree meaning that our search value must be on the left of this branch. We repeat this process one more time: newbranch = = current position / 2 The current position is 2 so the new index position will be 1 which contains the value of 2. Our search term is 2 and the value in the new position is also 2 meaning that we have found the value we were looking for. In this case our algorithm required 3 iterations to find the search term. The following code details the algorithm for the preceding example. You can use this code to further understand binary tree implementations and leverage some of the techniques that are supported within Jeliot, however, you cannot use this code as the basis for your assignment. // // Example of an array based implementation of a binary search developed in the Jeliot tool // import Prog1Tools.IOTools; import java.util.*; public class binarySearchTree public static void main (String] args) { int iterations; // This variable counts the number of iterations of search that occur int index; // This variable identifies the node of the tree currently being searched int prev; // This variable will be used to keep track of the 'range' of the branch int searchValue; // This variable will contain the value we are searching for // // In this example we are using an array implementation of a binary tree and the array // is being pre-populated with the integers in the tree in the correct sequence. // in your assignment you must populate your binary tree by accepting values // from the user and populating a structure in the proper sequence using either // an array or linked list implementation // int bTree[] = {1,2,3,4,6,7,8,9,10,12,13,14,15,16,17,18,19,20,21,23,24,25,26,27,2 8, 29,30,33,34,35,36,37,38,39,40 }; %3D // // Using Jeliot, you can use the System.out.printin method to output information // to the console. // System.out.printin("Enter an integer between 1 and 40 to search for:"); // // Using Jeliot, you must use the scanner class to get input from the user as // illustrated below. // Scanner in = new Scanner(System.in); in.nextInt(); searchValue = iterations=1; // // In this section we set the initial midpoint of the array which is the root value // index=bTree.length /2; prev=bTree.length; // // Here we call the binary search method which is designed to recursively // search until the proper value has been found // binarySearch(bTree, index, prev, searchValue, iterations); } public static void binarySearch(int[] bTree, int index, int prev, int searchValue, int iterations) { // // If our search value is smaller then the current position then // we need to search the left branch of the tree. The index value // indicates the current node that is being compared with the search value // the prev value is used to help identify the width of the current branch /l so that we can identify the next branch to follow down. // if (bTreeſindex] < searchValue) { index = (prev-index)/2+index; iterations++; binarySearch(bTree, index, prev, searchValue, iterations); } // // If our search value is larger than the current position then // we need to search the right branch of the tree. Note that in each // iteration of the search we recursively call binarySearch which searches // the next level down in the tree. // else if (bTree[index] > searchValue ) { prev = index; index = index / 2; iterations++; binarySearch(bTree, index, prev, searchValue, iterations); } // // When the search value is found, print the number of iterations the search // took to the console and exit the binarySearch method // else { System.out.printIn("Found search value in:"+iterations+" iterations"); return; } } } In the preceding example, the tree values were created in sequence meaning that the array was populated with values in order. Your algorithm must be able to accommodate values entered in any sequence which means that you must be able to adjust the structure of the tree as the root value and other values change. In the example above, we have an array that forms the basis of our binary search tree. We determine the root by looking midway through the array. The example above has an advantage in that the array is already in sorted order. In your algorithm you will not have that advantage. When you have completed your algorithm and your Asymptotic analysis of your algorithm please run it several times within Jeliot and observe the results. Use the following values for both the contents of the binary search tree and the search value: Integers to add to binary search tree: 10, 5, 12, 3, 1, 13, 7, 2, 4, 14, 9, 8, 6, 11 Search value: 9 Is the time (expressed in the number of iterations required to complete a search) consistent with your Asymptotic analysis in worst case (Big O)? As part of your assignment, you must submit both a description of the assignment and how your algorithm works including an Asymptotic analysis of your algorithm. Your analysis must include the efficiency of your algorithm expressed in Big Oh notation. The scope of your asymptotic analysis should only include the binary search portion of your assignment. Further, as part of your assignment, you must include the code of your algorithm. All of these elements of this assignment must be completed and posted to the assignment for Unit 4 by the end of the week for unit 4. Finally, you must include a screen shot or other capture of the output of you binary search tree that indicates the number of iterations that were required to find the search value.
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
Attached photo is the question. Please help. Thanks.
Binary Search Tree code:
//
// Example of an array based implementation of a binary search developed in the Jeliot tool
//
import Prog1Tools.IOTools;
import java.util.*;
public class binarySearchTree
{
public static void main (String[] args)
{
int iterations; // This variable counts the number of iterations of search that occur
int index; // This variable identifies the node of the tree currently being searched
int prev; // This variable will be used to keep track of the 'range' of the branch
int searchValue; // This variable will contain the value we are searching for
//
// In this example we are using an array implementation of a binary tree and the array
// is being pre-populated with the integers in the tree in the correct sequence.
// in your assignment you must populate your binary tree by accepting values
// from the user and populating a structure in the proper sequence using either
// an array or linked list implementation
//
int bTree[] = { 1,2,3,4,6,7,8,9,10,12,13,14,15,16,17,18,19,20,21,23,24,25,26,27,28, 29,30,33,34,35,36,37,38,39,40 };
//
// Using Jeliot, you can use the System.out.println method to output information
// to the console.
//
System.out.println("Enter an integer between 1 and 40 to search for:");
//
// Using Jeliot, you must use the scanner class to get input from the user as
// illustrated below.
//
Scanner in = new Scanner(System.in);
searchValue = in.nextInt();
iterations=1;
//
// In this section we set the initial midpoint of the array which is the root value
//
index=bTree.length /2;
prev=bTree.length;
//
// Here we call the binary search method which is designed to recursively
// search until the proper value has been found
//
binarySearch(bTree, index, prev, searchValue, iterations);
}
public static void binarySearch(int[] bTree, int index, int prev, int searchValue, int iterations) {
//
// If our search value is smaller then the current position then
// we need to search the left branch of the tree. The index value
// indicates the current node that is being compared with the search value
// the prev value is used to help identify the width of the current branch
// so that we can identify the next branch to follow down.
//
if (bTree[index] < searchValue) {
index = (prev-index)/2+index;
iterations++;
binarySearch(bTree, index, prev, searchValue, iterations);
}
//
// If our search value is larger than the current position then
// we need to search the right branch of the tree. Note that in each
// iteration of the search we recursively call binarySearch which searches
// the next level down in the tree.
//
else if (bTree[index] > searchValue ) {
prev = index;
index = index / 2;
iterations++;
binarySearch(bTree, index, prev, searchValue, iterations);
}
//
// When the search value is found, print the number of iterations the search
// took to the console and exit the binarySearch method
//
else {
System.out.println("Found search value in:"+iterations+" iterations");
return;
}
}
}
![Consider the following list of integers:
In this example, the root will be (array position 5) and the value of 6.
Keep in mind that positions in the array begin at 0. If the search
term were entered to be 2, then the midpoint would be selected
which we would determine with the following formula:
midpoint = length of array /2
Since the length is 11, the midpoint is position 5. We would then
compare the search term 3 to the value in position 5 and since 3 < 6
the search will continue on the left side of the tree structure. We
would repeat the process. With the following formula:
newbranch = current position / 2
The new length of the array is the left side of the tree up to the root
which is 5. This new formula would yield position 2 which is the
value 3. Since our search value is 2, it is less than the new branch
of the tree meaning that our search value must be on the left of this
branch. We repeat this process one more time:
newbranch =
= current position / 2
The current position is 2 so the new index position will be 1 which
contains the value of 2. Our search term is 2 and the value in the
new position is also 2 meaning that we have found the value we
were looking for.
In this case our algorithm required 3 iterations to find the search
term. The following code details the algorithm for the preceding
example. You can use this code to further understand binary tree
implementations and leverage some of the techniques that are
supported within Jeliot, however, you cannot use this code as the
basis for your assignment.
//
// Example of an array based implementation of a binary search
developed in the Jeliot tool
//
import Prog1Tools.IOTools;
import java.util.*;
public class binarySearchTree
public static void main (String] args)
{
int iterations; // This variable counts the number of iterations of
search that occur
int index; // This variable identifies the node of the tree
currently being searched
int prev; // This variable will be used to keep track of the 'range'
of the branch
int searchValue; // This variable will contain the value we are
searching for
//
// In this example we are using an array implementation of a
binary tree and the array
// is being pre-populated with the integers in the tree in the
correct sequence.
// in your assignment you must populate your binary tree by
accepting values
// from the user and populating a structure in the proper
sequence using either
// an array or linked list implementation
//
int bTree[] =
{1,2,3,4,6,7,8,9,10,12,13,14,15,16,17,18,19,20,21,23,24,25,26,27,2
8, 29,30,33,34,35,36,37,38,39,40 };
%3D
//
// Using Jeliot, you can use the System.out.printin method to
output information
// to the console.
//
System.out.printin("Enter an integer between 1 and 40 to
search for:");
//
// Using Jeliot, you must use the scanner class to get input
from the user as
// illustrated below.
//
Scanner in = new Scanner(System.in);
in.nextInt();
searchValue =
iterations=1;
//
// In this section we set the initial midpoint of the array which is
the root value
//
index=bTree.length /2;
prev=bTree.length;
//
// Here we call the binary search method which is designed to
recursively
// search until the proper value has been found
//
binarySearch(bTree, index, prev, searchValue, iterations);
}
public static void binarySearch(int[] bTree, int index, int prev, int
searchValue, int iterations) {
//
// If our search value is smaller then the current position then
// we need to search the left branch of the tree. The index value
// indicates the current node that is being compared with the
search value
// the prev value is used to help identify the width of the current
branch
/l so that we can identify the next branch to follow down.
//
if (bTreeſindex] < searchValue) {
index = (prev-index)/2+index;
iterations++;
binarySearch(bTree, index, prev, searchValue, iterations);
}
//
// If our search value is larger than the current position then
// we need to search the right branch of the tree. Note that in
each
// iteration of the search we recursively call binarySearch which
searches
// the next level down in the tree.
//
else if (bTree[index] > searchValue ) {
prev = index;
index = index / 2;
iterations++;
binarySearch(bTree, index, prev, searchValue, iterations);
}
//
// When the search value is found, print the number of iterations
the search
// took to the console and exit the binarySearch method
//
else {
System.out.printIn("Found search value in:"+iterations+"
iterations");
return;
}
}
}
In the preceding example, the tree values were created in sequence
meaning that the array was populated with values in order. Your
algorithm must be able to accommodate values entered in any
sequence which means that you must be able to adjust the
structure of the tree as the root value and other values change.
In the example above, we have an array that forms the basis of our
binary search tree. We determine the root by looking midway
through the array. The example above has an advantage in that the
array is already in sorted order. In your algorithm you will not have
that advantage.
When you have completed your algorithm and your Asymptotic
analysis of your algorithm please run it several times within Jeliot
and observe the results. Use the following values for both the
contents of the binary search tree and the search value:
Integers to add to binary search tree: 10, 5, 12, 3, 1, 13, 7, 2, 4, 14,
9, 8, 6, 11
Search value: 9
Is the time (expressed in the number of iterations required to
complete a search) consistent with your Asymptotic analysis in
worst case (Big O)?
As part of your assignment, you must submit both a description of
the assignment and how your algorithm works including an
Asymptotic analysis of your algorithm. Your analysis must include
the efficiency of your algorithm expressed in Big Oh notation. The
scope of your asymptotic analysis should only include the binary
search portion of your assignment.
Further, as part of your assignment, you must include the code of
your algorithm. All of these elements of this assignment must be
completed and posted to the assignment for Unit 4 by the end of the
week for unit 4. Finally, you must include a screen shot or other
capture of the output of you binary search tree that indicates the
number of iterations that were required to find the search value.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fe5a3425f-101d-417a-b762-3342c91c2324%2F65fc710a-e513-431c-a870-5a442ed9b392%2F8fc0zze_processed.png&w=3840&q=75)
Transcribed Image Text:Consider the following list of integers:
In this example, the root will be (array position 5) and the value of 6.
Keep in mind that positions in the array begin at 0. If the search
term were entered to be 2, then the midpoint would be selected
which we would determine with the following formula:
midpoint = length of array /2
Since the length is 11, the midpoint is position 5. We would then
compare the search term 3 to the value in position 5 and since 3 < 6
the search will continue on the left side of the tree structure. We
would repeat the process. With the following formula:
newbranch = current position / 2
The new length of the array is the left side of the tree up to the root
which is 5. This new formula would yield position 2 which is the
value 3. Since our search value is 2, it is less than the new branch
of the tree meaning that our search value must be on the left of this
branch. We repeat this process one more time:
newbranch =
= current position / 2
The current position is 2 so the new index position will be 1 which
contains the value of 2. Our search term is 2 and the value in the
new position is also 2 meaning that we have found the value we
were looking for.
In this case our algorithm required 3 iterations to find the search
term. The following code details the algorithm for the preceding
example. You can use this code to further understand binary tree
implementations and leverage some of the techniques that are
supported within Jeliot, however, you cannot use this code as the
basis for your assignment.
//
// Example of an array based implementation of a binary search
developed in the Jeliot tool
//
import Prog1Tools.IOTools;
import java.util.*;
public class binarySearchTree
public static void main (String] args)
{
int iterations; // This variable counts the number of iterations of
search that occur
int index; // This variable identifies the node of the tree
currently being searched
int prev; // This variable will be used to keep track of the 'range'
of the branch
int searchValue; // This variable will contain the value we are
searching for
//
// In this example we are using an array implementation of a
binary tree and the array
// is being pre-populated with the integers in the tree in the
correct sequence.
// in your assignment you must populate your binary tree by
accepting values
// from the user and populating a structure in the proper
sequence using either
// an array or linked list implementation
//
int bTree[] =
{1,2,3,4,6,7,8,9,10,12,13,14,15,16,17,18,19,20,21,23,24,25,26,27,2
8, 29,30,33,34,35,36,37,38,39,40 };
%3D
//
// Using Jeliot, you can use the System.out.printin method to
output information
// to the console.
//
System.out.printin("Enter an integer between 1 and 40 to
search for:");
//
// Using Jeliot, you must use the scanner class to get input
from the user as
// illustrated below.
//
Scanner in = new Scanner(System.in);
in.nextInt();
searchValue =
iterations=1;
//
// In this section we set the initial midpoint of the array which is
the root value
//
index=bTree.length /2;
prev=bTree.length;
//
// Here we call the binary search method which is designed to
recursively
// search until the proper value has been found
//
binarySearch(bTree, index, prev, searchValue, iterations);
}
public static void binarySearch(int[] bTree, int index, int prev, int
searchValue, int iterations) {
//
// If our search value is smaller then the current position then
// we need to search the left branch of the tree. The index value
// indicates the current node that is being compared with the
search value
// the prev value is used to help identify the width of the current
branch
/l so that we can identify the next branch to follow down.
//
if (bTreeſindex] < searchValue) {
index = (prev-index)/2+index;
iterations++;
binarySearch(bTree, index, prev, searchValue, iterations);
}
//
// If our search value is larger than the current position then
// we need to search the right branch of the tree. Note that in
each
// iteration of the search we recursively call binarySearch which
searches
// the next level down in the tree.
//
else if (bTree[index] > searchValue ) {
prev = index;
index = index / 2;
iterations++;
binarySearch(bTree, index, prev, searchValue, iterations);
}
//
// When the search value is found, print the number of iterations
the search
// took to the console and exit the binarySearch method
//
else {
System.out.printIn("Found search value in:"+iterations+"
iterations");
return;
}
}
}
In the preceding example, the tree values were created in sequence
meaning that the array was populated with values in order. Your
algorithm must be able to accommodate values entered in any
sequence which means that you must be able to adjust the
structure of the tree as the root value and other values change.
In the example above, we have an array that forms the basis of our
binary search tree. We determine the root by looking midway
through the array. The example above has an advantage in that the
array is already in sorted order. In your algorithm you will not have
that advantage.
When you have completed your algorithm and your Asymptotic
analysis of your algorithm please run it several times within Jeliot
and observe the results. Use the following values for both the
contents of the binary search tree and the search value:
Integers to add to binary search tree: 10, 5, 12, 3, 1, 13, 7, 2, 4, 14,
9, 8, 6, 11
Search value: 9
Is the time (expressed in the number of iterations required to
complete a search) consistent with your Asymptotic analysis in
worst case (Big O)?
As part of your assignment, you must submit both a description of
the assignment and how your algorithm works including an
Asymptotic analysis of your algorithm. Your analysis must include
the efficiency of your algorithm expressed in Big Oh notation. The
scope of your asymptotic analysis should only include the binary
search portion of your assignment.
Further, as part of your assignment, you must include the code of
your algorithm. All of these elements of this assignment must be
completed and posted to the assignment for Unit 4 by the end of the
week for unit 4. Finally, you must include a screen shot or other
capture of the output of you binary search tree that indicates the
number of iterations that were required to find the search value.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 4 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY