私は試験の準備をしていますが、次の質問に出くわしました。
次の順序でデータを追加した場合に得られる二分探索木を描画します。
10,9,8,7,6,5,4,3結果のツリーが効率的な検索に適さないのはなぜですか?
私の答え：
BST を作成するときに、ルート ノードとして値 10 から開始し、最初のレベルの左サブ ツリー値として 9 を追加すると考えたでしょう。次に、8 から 9 の左側のサブツリーへ、というように続きます。なぜこれが検索の効率を低下させるのかはわかりません。何か案は？
3 に答える
8
値は降順であるため、各レベルで左に追加され、実際にはリンクされたリストが残ります。これは、BST の優先 O(logN) ではなく、検索に O(N) を必要とします。
描く：
10
/
9
/
8
/
7
/
6
/
5
/
4
/
3
于 2012-05-16T12:30:08.650 に答える
0
これは単なる一連のノードであるため、リンクされたリストが作成されます。これは非常にバランスの悪い木です。
赤黒 木を 調べ て ください. それらは同じ時間の複雑さを持っていますが、常にノードの周りを移動するため、常に三角形を形成しています。これにより、ツリーのバランスが保たれます。
于 2012-05-16T12:30:30.023 に答える
0
ノードは常に前のノードの左側のサブツリーに追加されるため、これは非効率的です。答えが常に左側にあるにもかかわらず、結果が見つかるまでリスト内のすべてのノードを検索してチェックするため、実際には、ループを介して検索されるリストを単純に持つよりも多くの計算が必要になります。
于 2012-05-16T12:33:54.977 に答える