しばらくの間、私はこの質問に対する答えを疑問に思って探していました。それは次のとおりです。ツリーデータ構造のノードの下にあるすべての葉を効率的に（時間的に具体的に）リストするにはどうすればよいですか？
私は当初、そのノードの下にあるすべてのリーフを接続するリンクリストを使用して実行できると考えていました。
これが可能であれば、O（n）の線形時間でサブツリーの下の葉を反復処理できます。ここで、nはそのサブツリーの下の葉の数です。
ただし、各サブツリーに異なるリンクリストが必要になることを考えると、実用的ではないように思われます。
それで、誰かがそれが可能であるか、そうでないか、そしてその理由を指摘することができれば、私は感謝するでしょう？
この場合、単純な二分木を考えてみましょう。
よろしく
B+ ツリーは、リーフ間のポインター (次、前) を許可します。すべてのデータがリーフ レベルに格納されていると仮定すると、B+ ツリーが要求を達成するための最良の方法である可能性があります。
共通のルート ノード (ツリー全体のルートではない) を持つリーフ ノードのみを求めている場合は、そのルートの下の一番左のノードを見つけて、リーフ ノード whos に到達するまで「次の」リンクをたどることができます。値がルート ノードの右側のノードより大きくなっています。
特別な機能を持たない一般的なツリー (各ノードにはペイロード インデックスとサブツリーへのポインターしかありません) では、サブツリー全体をたどる必要があります。少なくとも初めては他に方法はありません。
高速な方法でそれらの葉ノードに再度アクセスする必要がある場合よりも、ほぼ O(1) 時間のアクセスを可能にするポインタのベクトル/配列を設定できますが、新しいノードを挿入するときにポインタを管理する必要があります古い葉を参照するのではなく、新しい葉を参照します
複数のサブツリーに対応する葉が必要な場合、通常の状況では単純で高速な解決策は多次元配列 (この場合は 2D) ですが、非常に大きなデータセットまたはメモリが限られている場合は問題になる可能性があります (この場合、必要に応じてよりメモリに優しい B+Tree にスワップします)
それはまったく非現実的ではありません。
葉ごとに「次の」葉を設定し、各ノードに最初の (または最小の) 葉と最後の葉 (最大の葉) へのポインタのみを格納できます。
次に、各ノード (サブツリー) から最初のリーフに到達し、リーフを反復処理できます。
最初と最後のリーフは、挿入時に O(logn) の複雑さで更新できます。
速度とメモリ サイズは常にトレードオフです。
科学には何百もの異なる試みがあります。ただし、そのような追加のポインターやリストなどはすべて、追加のメモリが必要です。
そして、速度の問題がほとんどの場合ツリーではない場合、それは一般的な解決策には実用的ではありません。
ツリーノードの下にあるすべてのリーフをリストしたい特定のアプリケーションのために、非常に特別なツリーが必要な場合は、左と右のサブツリーを単純に反復するよりも高速なものが必要な場合に、特殊な実装を使用する必要があります。適度な速さで。
さらに、すべてのサブノードのリーフを知りたい人はいますか?
これはツリーの内部トピックであり、外部からは、ノードの下に何があるかさえわからないはずです。（バランスの取れた木を考えてください。構造が変わります）。