Consider a set of positive integers X = {₁,...,n} where each z; is represented in base 2³ that is, over the alphabet {0.

[answerhappygod]

Consider A Set Of Positive Integers X N Where Each Z Is Represented In Base 2 That Is Over The Alphabet 0 1 (52.26 KiB) Viewed 13 times

Consider a set of positive integers X = {₁,...,n} where each z; is represented in base 2³ that is, over the alphabet {0..2 - 1} - and x; ≤ ne for some constant c. We assume for simplicity that s divides clog n. Suppose we store all ; strings in a compressed trie T in the following way. For each node v € T, we maintain an array A, of size 2. In this array, A, [] contains a pointer to the child v, of v such that the edge of T connecting v and u, is labelled with the symbol j. If no such v, exists, then A, [j] = 0. (a) What is the upper bound on the maximum height of T in terms of s, n, and c? (b) What is the upper bound on the maximum space usage of all arrays A,? Consequently, what is the upper bound on the maximum space usage of T? (c) What time is needed to search for a key k in T?