102 CHAPTER 4 Principles in Action tries to halve the binary search range again. This time the search tries entry 4, which is in the guard range. The search finds equality, moves to the right, and finds BMW , as desired. In general, every multiword entry W 1 , W 2 , . . . , W n will store a precomputed guard range. The range for W i points to the range of entries that have W 1 , W 2 , . . . , W i in the first i words. This ensures that on a match with W i in the ith column, the binary search in column i + 1 will search only in this guard range. For example, the N entry in BNY (second column) has a guard range of 5­7, because these entries all have BN in the first two words. The resulting search strategy takes log 2 N + W probes if there are N identifiers. The cost is the addition of two 16-bit pointers to each word. Since most word sizes are at least 32 bits, this results in adding 32 bits of pointer space for each word, which can at most double memory usage. Besides adding state, a second dominant idea is to use precomputation (P2a) to trade a slower insertion time for a faster search. The idea is due to Butler Lampson. E XERCISE · (This is harder than the usual exercises.) The naive method of updating the binary search data structure requires rebuilding the entire structure (especially because of the precomputed ranges) when a new entry is added or deleted. However, the whole scheme can be elegantly represented by a binary search tree, with each node having the usual > and < pointers but also an = pointer, which corresponds to moving to the next column to the right, as shown earlier. The subtree corresponding to the = pointer naturally represents the guard range. The structure now looks like a trie of binary search trees. Use this observation and standard update techniques for balanced binary trees and tries to obtain logarithmic update times. 4.15 VIDEO CONFERENCING VIA ASYNCHRONOUS TRANSFER MODE