我有一个按升序排列的整数输入流，我的任务是从该流中动态创建一个平衡二叉搜索树。我已经从整数流中浏览了链接：BBST，并了解到我们可以利用红黑树。问题是，我正在寻找使用输入数据中的"排序信息"的更优化的解决方案。
如果使用红黑树，但始终从插入的最后一个节点而不是根节点开始插入，并使用自下而上的插入算法，则插入是 O（1） 摊销的。这意味着构造树将花费O（n），而不是Ω（n log n）。
如果元素按排序顺序排列，那么最简单和最有效的做法可能是将每个元素推到动态数组的末尾（例如，一个数组，每当它变满时，其大小就会加倍）。
- 推入阵列将摊销 O（1）。
- 排序数组中的搜索是 O（log（n）） 使用二叉搜索。此外，它是常数非常低的对数时间。
尽管排序数组很简单，但它是一种平淡无奇的二叉搜索树。
问题是数据量未知。因此，无论输入是否具有模式（升序），此树都必须是自平衡的。
如果在这种情况下 O（log n） 插入时间是不可接受的（例如对于红黑树），那么我不知道为什么您需要首先以平衡的二叉树形式存储它。动态数组上的二叉搜索与树一样快，具有摊销的 O（1） 插入时间。
如果事先知道溪流的大小，那么建造树当然会容易得多。