binary-tree - 二分探索木の葉に効率的に到達するにはどうすればよいですか?

Question

BST の葉のすべての値を合計したい。どうやら、ツリー全体を横断しないと葉に到達できないようです。これは本当ですか？O(N) 時間をかけずに葉にたどり着くことができますか?

Answer 1

いずれにせよ、葉自体が少なくとも O(n) の 1/2 になることはわかりますか?

Answer 2

ツリー全体をトラバースせずにツリーの葉を取得する方法はありません (特にすべての葉が必要な場合)。残念ながら O(n) 時間で動作します。これらすべての葉にアクセスしたい場合、ツリーがデータを格納する最良の方法であると確信していますか? データへのより効率的なアクセスを可能にする他のデータ構造があります。

Answer 3

子のないノードを検索してツリーをトラバースするか、ツリーを表すために使用している構造を変更して、リーフ ノードのリストを含める必要があります。これには、リストを維持するために挿入メソッドと削除メソッドを変更する必要もあります (たとえば、ノードから最後の子を削除すると、それはリーフ ノードになります)。ツリーが非常に大きい場合を除き、先に進んでツリーをトラバースするだけで十分でしょう。