O(1) 余分なスペースを使用してバイナリ ツリーをバイナリ検索ツリーに変換するにはどうすればよいですか?
1669 次
2 に答える
7
順序付けされていない二分木を順序付けられた二分探索木に変換するのは簡単ですが、高速に行うのは少し難しくなります。
これは、あなたの基準を満たす単純な実装です。実際の手順については説明しません。アルゴリズム全体についてのみ説明します。
- 既存のツリーからランダムなリーフ ノードを取得します
- 既存のツリーからリーフ ノードのリンクを解除します
- ノードを新しい二分探索木のルートにする
- 既存のツリーから別のランダム リーフ ノードを取得します
- そのノードを既存のツリーからリンク解除します
- 新しいバイナリ検索ツリーに適切な場所を見つけて、ノードをリンクします
- 元のツリーが空になるまで、手順 4 ～ 6 を繰り返します。
リンクを解除するリーフ ノードの親 (ノードに親リンクがない場合)、新しいツリーのルート ノード、いくつかの一時変数など、すべて O(1 ) スペース基準。
これは、最適な二分探索木を生成しません。そのためには、ノードを追加する前にノードを並べ替えて正しい順序で追加するか、赤黒ツリーやスプレー ツリーなどのバランス 二分探索ツリーを使用する必要があります。
于 2010-05-17T10:24:22.813 に答える
-1
バイナリ ツリーを二重リンク リストに変換します。O(n) でインプレースで実行できます。次に、マージ ソートを使用して並べ替えます。nlogn リストをツリーに変換します - O(n)
シンプルな nlogn ソリューション。
于 2014-02-18T19:52:15.133 に答える