Consider a set X = {x1,...,xn } where every xi is a positive integer and xi ≤ nf for some constant f . We represent xi a
Posted: Fri Jul 08, 2022 6:35 am
Consider a set X = {x1,...,xn } where every xi is a positiveinteger and xi ≤ nf for some constant f . We represent xi asstrings over an alphabet 0, 1, . . . , 2t − 1 (i.e., representingeach xi in base 2t) and store all xi from X in a compressed trie T.For every node u of T we keep an array A(u) of size 2t + 1. A(u)contains a pointer to the child ui of u such that the edge from uto ui is marked with i; A(u) = NULL if there is no such ui inT.
Specify all of the following in big-O in terms of f, n, and t(as necessary). What is the maximum height of T? What is the totalspace usage of T and all A(u)? What time is
needed to search for a key k in T ?
Specify all of the following in big-O in terms of f, n, and t(as necessary). What is the maximum height of T? What is the totalspace usage of T and all A(u)? What time is
needed to search for a key k in T ?