2

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} ?

Andy897
  • 6,915
  • 11
  • 51
  • 86

1 Answers1

1

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
collapsar
  • 17,010
  • 4
  • 35
  • 61
  • Thanks a lot for replying. I did not get the answer to part 2. Probably I should revisit and try to understand insert operation before asking again. But not sure how someone will search for CBA in the tree that you formed. .. I start at root which is C .. but then no child of root C has B. I think I have not understood the whole thing at all. :) – Andy897 Feb 14 '15 at 17:13
  • 1
    The key insight: If you follow the `e[qual]` pointer, you increment the 'current char' ('#cc') position in your input string. If you follow either `l[eft]` or `r[ight]`pointer, you don't. Example (CBA search): #cc is 1. Start with the root node, which has C as payload - match. Follow `e` (so #cc=2) and check the successor node if it has B as payload. It hasn't, the payload character (D) is greater than B. Therefore your input string is smaller than the strings under the current node and you have to search the left subtree of the parent node ... – collapsar Feb 14 '15 at 17:58
  • 1
    ... So backup to the parent node (and remember, that's where #cc was 1 !) and follow `l`. Don't change #cc. you compare C from the input string to the payload(C). Next you follow the `e` pointer, increment #cc to 2 and compare B to the payload (B). 1 more step ( A=A ) and you've consumed the input. Check that the termination bit of the node is set to make sure, that your input is a key represented in the search tree and not just a prefix of stored keys. – collapsar Feb 14 '15 at 18:01
  • That was am amazing explanation. Thanks a lot. Can you please explain insert as well in few words with an example. If we already have CDA in tree and we want to insert CBA .. something of this sort ? Thanks again .. sorry if I am pushing this too much. – Andy897 Feb 14 '15 at 18:12
  • If you suggest .. I can create a different question/post for insertion :) – Andy897 Feb 14 '15 at 18:13