HERE it is said that each node in a ternary search tree has three pointers. Left, right and equals. But in the example tree for {CAT, BUGS, CATS, UP}, How is that equals pointer of 'C' points to 'A' ? 'C' and 'A' are not equal right ?
And if a node can have only three pointers, how will a ternary tree represent a set of keys like {CAB,CBA,CDA,CEA,CFA} ?
A1: The equals pointer marks the continuation of the current prefix. Thus C -> CA -> CAT -> CATS but not C -> CB[UGS].
A2: This would be a ternary search tree for the given set of expressions ( termination flags and leaf node expansion omitted):
C
|
+--------------------+---------------------+
| | |
/l/ /e/ /r/
| | |
C D C
| | |
+-----------+----+ +---+---+ +---+-----------+
| | | | | | | | |
/l/ /e/ /r/ /l/ /e/ /r/ /l/ /e/ /r/
| | | | | | | | |
C B x x A x x E C
| | | |
| | | |
+---+---+ +---+---+ +---+---+ +---+---+
| | | | | | | | | | | |
/l/ /e/ /r/ /l/ /e/ /r/ /l/ /e/ /r/ /l/ /e/ /r/
| | | | | | | | | | | |
x A x x A x x A x x F x
| |
| |
+---+---+ +---+---+
| | | | | |
/l/ /e/ /r/ /l/ /e/ /r/
| | | | | |
x B x x A x