algorithm - 三分探索木の等号ポインタと制限事項

Question

ここでは、三分探索木の各ノードには 3 つのポインターがあると言われています。左、右、および等しい。しかし、{CAT, BUGS, CATS, UP} の例のツリーでは、'C' のポインタが 'A' を指しているのとどのように等しいのでしょうか? 「C」と「A」は等しくありませんよね？

また、ノードが 3 つのポインターしか持てない場合、三分木は {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