3

ツリーを複製/乗算するには、(g++ の場合) (計算時間) 最適化されたアルゴリズム ツリー構造が必要です。

私のツリーは k-ary ツリーになりますが、必ずしも埋められるわけではありません。主な操作は、既存のツリーを (k 回まで) 乗算し、ツリーをサブツリーとして新しいノードに追加することです。次に、固定レベルのルールを保持するためにリーフ ノード レベルが消去されます。

これを提供するデータ構造を知っている人はいますか?

乗算の例: 二分木があるとします。

      A
      |
     / \
    /   \
   B     C
   |    / \
   |   /   \
   D   E    F

そして、新しいノードを追加したい/乗算したい

    R
   / \
  /   \
 ..   ..

したがって、結果は次のようになります

            R
           / \
          /   \
         /     \
        /       \
       /         \
      A           A
      |           |            
     / \         / \        
    /   \       /   \        
   B     C      B     C        
   |    / \     |    / \        
   |   /   \    |   /   \    
   D   E    F   D   E    F

これをヒープのような構造の std::vector で整理しようとしましたが、ツリー全体を一度にコピーするのではなく、各ツリー レベルを個別にコピーする必要があるため、ツリーの乗算はまだ少し遅いです。

4

2 に答える 2

0

たぶん、T9辞書のAndroidコードを見てください。AFAIR は平らに見えますが、基本的には文字のツリーを構築することであり、ツリーを上から下にトラバースすることで単語が作成されます。そして、ノードから次のノードにジャンプするために相対オフセットを使用したと思います（リンクされたリストのように）。

したがって、1 回の実行でツリー全体をコピーできるはずです。

正確なレイアウトを覚えていません。ここで行うように醜いパディングを行っていないと思いますが、例を続けると、次のようになります(!):

# your tree

         __________
      ///   _      \      _
     /// /// \      \  /// \
A007021B007000D000000C007014E000000F000000
  \\\_/                   \\\_____/


# copying it, "under" R:
                __________                                __________
     _       ///   _      \      _                     ///   _      \      _
  /// \     /// /// \      \  /// \                   /// /// \      \  /// \
R007049A007021B007000D000000C007014E000000F000000A007021B007000D000000C007014E000000F000000
     \\\ \\\_/                   \\\_____/      /  \\\_/                   \\\_____/
      \\\______________________________________/
于 2013-04-17T07:14:08.680 に答える