Suppose I have a list of 17 sorted elements (A0 ---- A16) and an integer x.....

Suppose I have a list of 17 sorted elements (A₀ ---- A₁₆) and an integer x_.. Assuming that we compare x with the first element A₀, if x is equal to A₀ , we found x and we return 1; otherwise we jump 4 elements (to A₄). If x is equal to A₄, we return 5 (index + 1), otherwise if it is less we back up 1 space to A₃; if x is equal to A₃ we return 4, otherwise we back-up to A₂, and if x is equal to A₂ we return 1, If x is less that A₂then we back-up to A₁ and if x = A₁ we return 2. If x is not equal to A1, x is not in the list and we return (0). If x it is larger than A₄ we repeat the process again and jump to A₈, and so on. Write the binary tree representation of the algorithm and give the worst-case running time.

Write the binary tree representation for the Binary Search for also 17 elements and give the worst-case

Solutions

Expert Solution

a.) Lets first define structure of each node in binary tree:-

node {

int data;

node *left, *right;

}

where variable 'data' will store the actual data in a node and pointer variables, 'left' and 'right' will store the address of left and right child respectively.

Now, lets define the structure of binary tree,

For an element at index 'i' its right child will be 'i+4', where 'i' will be multiple of 4. For example 'i' can have values,

0, 4, 8, 12, 16, 20, .... and so on.

i's left child will be 'i+3'.
'i+3's left child will be 'i+2', and 'i+3's right child will be NULL.
'i+2's left child will be 'i+1', and 'i+2's right child will be NULL.
'i+1' will be leaf node.

Special case:-

When last index of array is not a multiple of 4, then.

Last node's right child will be null.
And last node's left child will be the last index of array, that is greatest possible index in array.
Other things will remain same.

In worst case, we have to travers all right nodes and then all left nodes from the last right node. Element that we are searching for will be present in the last leaf node, and index of this node will be the last highest index which is not multiple of 4.

Maximum number of nodes which will be required to access is

MAX((last_index/4 + last_index%4), (last_index/4 + 2)) + 1.

T(n) = O(n).

where 'n' is the size of array.

Tree will look something like this, Missing nodes are NULL in this given binary tree .

Node A16 is the special case node.

venereology answered 1 year ago

Next > < Previous

Related Solutions

Lets say that I were to give you a sorted list of P elements that was...

Lets say that I were to give you a sorted list of P elements that was followed by randomly ordered elements. Please explain how you would sort the entire, whole list? Please give a detailed reasoning and provide a good explanation (In language C++) Please type answer if you can

In Coral. Given a sorted list of integers, output the middle integer .Assume the number of...

In Coral. Given a sorted list of integers, output the middle integer .Assume the number of integers ia odd. Ex: if the input 2 3 4 8 11 -1(a negative indicates end), the output is 4. the maximum number of inputs for any test case should not exceed 9 positive values. If exceeded , output Too many inputs". Hint: Use an array of size 9. First read the data into array.Then,based in the number of items, find the middle item.

In C++ Given a sorted list of integers, output the middle integer. A negative number indicates...

In C++ Given a sorted list of integers, output the middle integer. A negative number indicates the end of the input (the negative number is not a part of the sorted list). Assume the number of integers is always odd. Ex: If the input is: 2 3 4 8 11 -1 the output is: Middle item: 4 The maximum number of inputs for any test case should not exceed 9. If exceeded, output "Too many numbers". Hint: First read the...

how to sorted the list from another class!!! example i have a class public meso public...

how to sorted the list from another class!!! example i have a class public meso public meso(string id) public hashmap<string, integer> neou{ this class print out b d e c a now create another class public mesono public mesono(hashmap<string, integer> nei) //want to sorted meso class print list to this class!! // print out a b c d e } ( -------Java------)

(a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted...

(a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Mergesort. Count the number of comparisons made. (b) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Heapsort.

(a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted...

(a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Mergesort. Count the number of comparisonsmade. (b) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Heapsort

Suppose you have a list containing k integer numbers. Each number could be positive, negative, or...

Suppose you have a list containing k integer numbers. Each number could be positive, negative, or zero. Write pseudocode for a program that first asks the user for each of the numbers. After that, it should determine and display the number from the list that is nearest to the positive number five (5). Notes: 1. Try working this out for k = 4 and k = 5. See if you can find an algorithmic pattern that can be extended for...

Suppose x has a distribution with ? = 17 and ? = 16. (a) If a...

Suppose x has a distribution with ? = 17 and ? = 16. (a) If a random sample of size n = 39 is drawn, find ?x, ? x and P(17 ? x ? 19). (Round ?x to two decimal places and the probability to four decimal places.) ?x = ? x = P(17 ? x ? 19) = If a random sample of size n = 62 is drawn, find ?x, ? x and P(17 ? x ? 19)....

Suppose there are two known compounds containing the generic elements X and Y. You have a...

Suppose there are two known compounds containing the generic elements X and Y. You have a 1.00 g sample of each compound. One sample contains 0.31 g of X and the other contains 0.40 g of X. Identify plausible sets of formulas for these two compounds. X2Y and X3Y X2Y5 and X3Y5 XY and X2Y X3Y and X4Y XY3 and XY4 XY and X3Y X4Y2 and X3Y

goal Find the average of the elements in the list (list could have any number of...

goal Find the average of the elements in the list (list could have any number of elements). If the average is a decimal number, return only the integer part. Example: if average=10.8, return 10 Example: if list={10, 20, 30, 40, 50}, the method should return: 30 import java.io.*; import java.util.Scanner; class Node { int data; Node next; Node(int d){ // Constructor data = d; next = null; } } class LinkedList {// a Singly Linked List Node...

Subjects