|
82 |
|
|
|
|
access to the records is given in Figure 4.12.
The topmost element contains no symbol, it merely functions as the start of the structure.
Given an arbitrary key its presence or absence is detected by matching it against keys in the structure.
Matching proceeds level by level, once a matching symbol has been found at one level, the P1 pointer is followed to the set of alternative symbols at the next level down.
The matching will terminate either:
(1) when the key is exhausted, that is, no more key symbols are left to match; or (2) when no matching symbol is found at the current level.
For case (1) we have:
(a) the key is present if the P1 pointer in the same cell as the last matching symbol now points to a record; (b) P1 points to a further symbol, that is, the key 'falls short' and is therefore not in the structure.
For case (2), we also have that the key is not in the structure, but now there is a mismatch.
Stanfel and Patt have concentrated on generating search trees with minimum expected search time, and preserving this property despite updating. For the detailed mathematics demonstrating that this is possible the reader is referred to their cited work.
|
|
|
82 |
|
|
|