The sentinel values may not exist because there is (there should be) no restriction on key values that can be used in an M-way tree. However, the sentinel values can be recognized by their out-of-bounds indices: the left sentinel at -1 (assuming 0-origin indexing) and the right sentinel at the n, where n is the key-sequence size.
Any reference to keys[i] assuming the sentinels exist has to be translated
into actual code that checks the index i to make sure it's not referring
to a sentinel value. That is, replace references to keys[i] with
if i < 0 // deal with -∞ < k < k0 case. else if i ≥ n // deal with kn-1 ≤ k < +∞ case. else // deal with ki ≤ k < ki + 1 case.
As a practical matter, there is almost never any need to reference the +∞ sentinel directly, and the code can be usually be simplified to
if i < 0 // deal with -∞ < k < k0 case. else // deal with ki ≤ k < ki + 1 case.
For example, the MWST insert pseudo-code
if root.k[i] = v return true
would have to be replaced by the more accurate
if i < 0 // handle the -∞ < k < k0 case. else if root.k[i] = v return true
Because -∞ < v for any key value and this code tests for equality, the code can be simplified to
if i ≥ 0 ∧ root.k[i] = v return true
Because i represents the left end of bracketing range, it will never equal
n and there's no need to test for the +∞ case.
This page last modified on 24 January 2006.