等于三元搜索树中的指针和限制

Equals pointer in ternary search tree and limitations

HERE据说三元搜索树中的每个节点都有三个指针。左，右和平等。但是在 {CAT, BUGS, CATS, UP} 的示例树中，'C' 的指针如何指向 'A' ？ 'C' 和 'A' 不相等吧？

如果一个节点只能有三个指针，三元树将如何表示一组键，如 {CAB,CBA,CDA,CEA,CFA}？

A1： 等于指针标记当前前缀的延续。因此 C -> CA -> CAT -> CATS 而不是 C -> CB[UGS].

A2： 这将是给定表达式集的三元搜索树（省略了终止标志和叶节点扩展）：

                                           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