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

Question

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

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

Answer 1

A1：equals 指针标志着当前前缀的延续。因此 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