algorithm - 插入 BST 时，插入的第一项是否总是树的根？

Question

查看维基百科上的实现，标准 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);
 }

Answer 1

是的，它将总是在根节点上，因为:

• 那是你唯一可以把它放在空树中的地方；和
• 你没有移动它。

当然，您可以删除它，这将导致另一个节点成为根节点，但不会将原始第一个节点移动到树的其他位置。

不平衡二叉树的退化情况是链表，其搜索时间复杂度为 O(n)。