0
キャッシュを効果的に使用するN進化ツリーを最適に設計する方法を探しています。私はツリー上の操作の大部分がノードからルートへのトラバーサルになると予想しているので、私がターゲットにしたいユースケース、挿入/削除がかなり高価だとは思えません。キャッシュに最適化されたN進化ツリーの設計
私の頭のOntopは、ノードを前後に（つまり、末尾に）格納することが望ましいプロパティの1つです。そして、私はあなたがBFSまたはDFSのいずれかにそれを保存することができると思います - これはこの場合に最適ですか？木が一定の大きさになったら問題になりますか？
また、私は簡単にこれを見つけました。これは有望だと思いますが、これはBSTではなく、どんな種類の検索や、子からルートへのトラバーサルも必要ありません。
編集：それはベクトル/アレイのontop、それで連続的なメモリを実装する必要があります。それはBSTである必要はありません。ノードはベクトル/配列のランダムアクセスプロパティを介して直接アクセスされますが、それはそこからルートへのトラバーサルです。
アイデア？
_Why_ツリーをトラバースしていますか？葉と根の間のノードを見つけるために、私は仮定しますか？どのように最初の場所で正しい葉のノードを見つけるのですか？リーフが 'Node * '経由で見つかると、それらを移動することはできず、挿入が複雑になります。 – MSalters
ノードなどを連続したデータ構造（ベクターなど）に保存できますか？あなたのデータはどれくらいの大きさで、ツリーの大きさはどれくらいですか？ –
私は完全に質問を理解していませんが、キャッシュを使用するBSTでB +ツリーを使用したい場合は、既に実装されている束がたくさんあります。 https://en.wikipedia.org/wiki/B%2B_tree – AlexG