問題タブ [2-3-tree]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
data-structures - 2-3 Tree の Iterator オブジェクト
2-3 ツリーのイテレータについて助けが必要でした。私が現在実装している方法は、DFS にほぼ似た再帰的アプローチです。ルートからトラバーサルを初期化し、リーフ ノードに到達するまで左側のブランチにアクセスし、それを Linked-List に追加します。再帰がバックトラックするにつれて、左のブランチのすべてのノードが追加され、次にルートの最初のキーが順序を維持するために追加されます。真ん中と右の枝でも同じことをします。リンク リストが作成されたら、そのイテレータを返すだけです。私が知りたかったのは、これが 2-3 ツリーのイテレータを構築する最良の方法ですか? 効率的にするために何を変更できますか？ツリーが巨大化すると、再帰呼び出しで StackOverFlowError が発生するのではないかと心配しています (笑、皮肉です)。
time-complexity - 2 ～ 3 ツリーでの挿入と削除の時間の複雑さ
2-3 ツリーでの挿入操作と削除操作が常に O(logn) の複雑さを持つのはなぜですか? 数学的な証明はありますか?