1

ウィキペディアの実装を見ると、標準の BST (非自己平衡化) は挿入中に再配置されないように思われるため、最初に追加された項目が常にルートになります。これは正しいです？もしそうなら、それはBSTがしばしばO(logN)よりも悪い可能性があることを意味しませんか?

これを再帰挿入のリファレンスとして使用する:

 /* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */
 void InsertNode(Node* &treeNode, Node *newNode)
 {
     if (treeNode == NULL)
       treeNode = newNode;
     else if (newNode->key < treeNode->key)
       InsertNode(treeNode->left, newNode);
     else
       InsertNode(treeNode->right, newNode);
 }
4

5 に答える 5

1

はい、単純に次の理由から、常にルート ノード上にあります。

  • 空のツリーに配置できる唯一の場所です。と
  • あなたはそれを動かしていません。

もちろん、それを削除すると、別のノードがルートになりますが、元の最初のノードがツリー内の別の場所に移動することはありません。

不均衡なバイナリ ツリーの縮退のケースは、O(n) の検索時間の複雑さを持つリンク リストです。

于 2009-04-23T00:03:29.263 に答える
0

はい、これが自己平衡型 BST が存在する理由です。

于 2009-04-22T23:39:58.790 に答える
0

このSO answerにいくつかの良い情報があります。

于 2009-04-22T23:42:05.850 に答える
0

はい、バランスの取れていない BST は悪い場合があります。実際、並べ替えられたデータを BST に追加すると、挿入が最後にあると仮定して、O(n) の挿入を持つ単一の連結リストのパフォーマンスにツリーをすばやく縮退させることができます。

ランダムなデータを扱っている場合、標準の BST は平均してかなりうまく機能します。最悪の敵は、ソートされたデータ、または逆ソートされたデータです。

これが、通常、バランスの取れた BST を使用する理由です (言語のライブラリから 1 つを選択するだけです)。

于 2009-04-22T23:52:42.517 に答える
0

はい、挿入の順序は、結果のツリーの形状/バランスに悪影響を及ぼす可能性があります。あなたが指摘したように、結果として得られるツリーの最悪のケースは O(log(N)) よりも悪く、単に linked-list のように見える可能性があります。

于 2009-04-22T23:39:16.933 に答える