要素を 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
木を使わない場合
ありがとう