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

Question

查看 Wikipedia 上的实现，似乎标准 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

是的，它总是在根节点上，原因很简单：

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

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

The degenerate case for an unbalanced binary tree is a linked list, which has a search time complexity of O(n).

Answer 2

是的，插入顺序会对生成的树的形状/平衡产生负面影响。正如您所指出的，树的最坏情况比 O(log(N)) 更糟糕，最终可能看起来就像一个链表。

Answer 3

是的，这就是存在自平衡 BST 的原因。

Answer 4

这个SO answer中有一些很好的信息。

Answer 5

是的，不平衡的 BST 可能很糟糕。事实上，如果您将排序数据添加到 BST，您可以快速将您的树退化为单链表性能，其中插入 O(n)，假设插入在末尾。

如果您正在处理随机数据，标准的 BST 平均会做得很好。你最大的敌人是排序的，或者反向排序的数据。

这就是为什么您通常希望使用平衡的 BST（只需从您的语言库中选择一个）。