Consider a hash table with chaining where the elements (string) of same hash value are inserted in a binary search tree (BST) implemented dynamically.

• Give necessary declarations and write a function that returns an array that contains the number of collisions on each cell in the array; this array is named array of collisions.

In the following, we define the array of intervals of an array A[k] as the array of integers of length k - 1 with the following elements: A[1] - A[0], A[2] - A[1], $$\cdots$$ , A[k-1] - A[k-2].

A hash function is called almost uniform if it satisfies the following conditions:

• the difference between the maximum and the minimum in the array of collisions is $$\leq$$ 2
• each element in the array of intervals obtained from the array of collisions {-1, 0, 1}

• Write a function to determine if the hash function used to fill a given hash table is almost uniform or not.

int count(BST B)
{
    if(!B) return 0;
    return 1+count(B->left)+count(B->right);
}

void array_collisions(hashtable h, int col[])
{
    int i , x;
    for(i=0; i<M;i++)
    {
        x=count(h[i]);
        col[i]=(x<2)?x:x-1;
    }
}


void array_intervals(int T[], int interv[])
{
	int i;
	for (i=0;i<M-1;i++)
		interv[i] = T[i+1] - T[i];
}


void min_max(int T[], int *min, int *max)
{
	int i;
	*max = *min = T[0];
	for (i=1;i<M;i++)
		if (T[i] < *min) 
		    *min = T[i];
        else 
            if (T[i] > *max)
                *max = T[i];
}

int almost_uniform(hashtable T)
{
	int i,min,max,arr_col[M],arr_int[M-1];
	array_collisions(T,arr_col);
    array_intervals(arr_col,arr_int);
    min_max(arr_col,&min,&max);
    if (max - min > 2) return 0;
	for (i=0;i<M-1;i++)
		if (arr_int[i] > 1 || arr_int[i] < -1) 
		    return 0;
	return 1;
}