12-2 Radix trees

Given two strings \(a = a_0a_1 \ldots a_p\) and \(b = b_0b_1 \ldots b_q\), where each \(a_i\) and each \(b_j\) is in some ordered set of characters, we say that string \(a\) is lexicographically less than string \(b\) if either

  1. there exists an integer \(j\), where \(0 \le j \le \min(p, q)\), such that \(a_i = b_i\) for all \(i = 0, 1, \ldots j - 1\) and \(a_j < b_j\), or
  2. \(p < q\) and \(a_i = b_i\) for all \(i = 0, 1, \ldots, p\).

For example, if \(a\) and \(b\) are bit strings, then \(10100 < 10110\) by rule 1 (letting \(j = 3\)) and \(10100 < 101000\) by rule 2. This ordering is similar to that used in English-language dictionaries.

The radix tree data structure shown in Figure 12.5 stores the bit strings \(1011, 10, 011, 100\), and \(0\). When searching for a key \(a = a_0a_1 \ldots a_p\), we go left at a node of depth \(i\) if \(a_i = 0\) and right if \(a_i = 1\). Let \(S\) be a set of distinct bit strings whose lengths sum to \(n\). Show how to use a radix tree to sort \(S\) lexicographically in \(\Theta(n)\) time. For the example in Figure 12.5, the output of the sort should be the sequence \(0, 011, 10, 100, 1011\).

(Removed)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用