0

要素を BST に挿入するための次のアルゴリズムがあるとします。

 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);
 }

このアルゴリズムはO(n)最悪の場合に実行されます。

O(n)最悪の場合、より複雑でないアルゴリズムを使用して要素を BST に挿入することは可能ですか?

備考 1 : これは宿題ではありません (次の試験の準備)

備考 2 :AVL木を使わない場合

ありがとう

4

1 に答える 1

6

挿入は検索操作と同等です。明らかに、ツリーのバランスが取れていない場合、最悪の場合は常にリンク リスト形式のツリーになります。したがって、O(n) を回避する方法はありません。

于 2012-06-27T15:55:49.977 に答える