ソートされた配列からバランスのとれた BST を作成しました。私の質問は、それをテストする方法です。ツリーがバランスが取れているかどうかをテストするだけでは、バイナリ ツリー (注 - BST ではなくバイナリ ツリーに言及) でさえバランスが取れている可能性があるため、役に立ちません。ツリーが BST かどうかのテストも enof ではありません。私が今持っている唯一の答えは、それがbalanced' &&bst かどうかを確認することです。現在、これは複雑な 2 ステップのテスト プロセスです。シンプルでスマートなソリューションはありますか?
質問する
132 次
2 に答える
1
バランスがとれている場合、深さは最大で log(n)+1 になります。ここで、n はツリー/配列内のノードの数です。
ツリーが実際に BST であるかどうかを確認するには、ノードを「順番に」トラバースし、それらが実際に順番に並んでいることを確認します。
ちなみに、ソートされた配列がある場合、そこからバランスの取れた BST を構築する非常に簡単な方法があります。二分探索と同じ方法で実行します。探す。たとえば、次のようにします。
1,2,3,4,5,6,7,8,9
最初に を挿入5し、その後に3とを挿入し、その後7に残りを挿入します。
于 2013-09-19T03:37:49.763 に答える
0
あなたの質問に答えるには：
あなたが読むことができる非常に良い記事があります.BSTとSorted arrayの間の関係について特に書かれています.
手短に答えると、BST はあらゆる種類の迷惑行為を示す可能性があります。賢明に構築することを選択しないと、配列がソートされていない場合、バランスの取れた BST の最善の保証は構築されたときです。無作為に。Eric Domaine のビデオ (ランダムに構築された BST )をご覧ください。
ソートされた配列から既に BST を構築したので、アルファシンで提案されていること [深さは最大で log(n) + 1] は良いチェックです...しかし、あなたが最大について話すとき、私は反対したいと思います深さは、各ノードをチェックしていくつかのスペースに格納するようなものです。最も深いノードがわからないため、巨大なツリーがあると難しいと思います。
ルートの高さを見つけることをお勧めします。ルートの高さが log(n) + 1 の場合、バランスが取れています。
計算された値のスタックへの格納はすべてプログラムに任せます。
于 2013-09-19T03:56:42.920 に答える