Question

1. 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.

            

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

Answer 1

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.