algorithm - 是否可以向 BST 中插入复杂度低于 O(n) 最坏情况的元素？

Question

给定以下用于将元素插入 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树

谢谢

Answer 1

插入相当于一个搜索操作。显然，如果您的树不平衡，最坏的情况将始终是链表形式的树。所以没有办法避免O(n)。