Backtracking reverses a traversal when the current choice cannot complete the operation, allowing an earlier decision or node to provide the result or continue repair. section 6.2.5 section 10.3.2
A recursive backtracking step typically follows this pattern:
- Descend by following the currently preferred child or matching character. section 6.2.5 section 10.3.2
- Return immediately when the operation succeeds or no further descent is possible. section 6.2.5 section 10.3.2
- On failure or structural change, move back toward the root and inspect or update each ancestor. section 6.2.5 section 10.3.2
- Stop when the ancestor can absorb the result without further changes. section 10.3.2
Trie longest prefix
A recursive trie search follows the searched characters. If the path ends without a key, it backtracks; the first key node encountered supplies the longest stored prefix. The operation remains O(m) for a string of length m. section 6.2.5
SS-tree insertion
After inserting into a full leaf, the algorithm splits that leaf and backtracks through its ancestors. Each parent absorbs the replacement children or splits itself, while centroids and radii are recomputed until constraints hold. section 10.3.2
Listing 6.9 Method longestPrefix
function longestPrefix(node, s, prefix) #1
if s == “” then #2
if node.keyNode then #3
return prefix
else
return null #4
c, tail ← s.splitAt(0) #5
if node.children[c] == null then #6
if node.keyNode then return prefix else return null #7
else
result ← longestPrefix (node.children[c], tail, prefix + c) #8
if result != null then #9
return result
elsif node.keyNode then #10
return prefix
else
return null #11
Trace the longestPrefix recursion, including its fallback checks while unwinding the path. section 6.2.5
