Question

Void PrintInCommon(int *array1, int array1_size, int *array2, int array2_size) {

create a balanced binary tree T;
foreach element X in array1:
add X to T;
foreach element Y in array2:
search T for Y;
if Y was found:
print(Y);
free the tree T;
}

When the above function is running, we would expect the most temporal locality for accesses to which of the following?
a. the elements of array1 and array2 in the loops
b. the root of the binary tree
c. the leaves of the binary tree
Comments:

Answer 1

The root of the binary tree experiences the most temporal locality during the execution of the function, as it is repeatedly accessed during both insertion and search operations.

Step-by-step explanation:

When the above function is running, we would expect the most temporal locality for accesses to the root of the binary tree. Temporal locality refers to the tendency of a processor to access the same memory locations repeatedly over a short period of time. In the context of a balanced binary tree, the root node is accessed every time a new search or insertion is initiated.

Since both the insertion loop (which processes array1) and the search loop (which processes array2) begin at the root, this node will experience the highest temporal locality. In contrast, individual leaves are accessed less frequently, as they are the endpoint of a particular search or insertion path and are not repeatedly accessed unless specific values residing in those leaves are repeatedly looked for.