algorithm - 从排序数字流生成平衡二叉搜索树的最佳方法

Question

我有一个按升序排列的整数输入流，我的任务是动态地从该流中创建一个平衡二叉搜索树。我已经浏览了链接：来自整数流的 BBST，并了解我们可以使用红黑树。问题是，我正在寻找更优化的解决方案，这些解决方案使用输入数据中的“排序信息”。

Answer 1

如果元素按排序顺序出现，那么最简单和最有效的做法可能就是将每个元素推到动态数组的末尾（例如，一个数组，只要它变满，它的大小就会翻倍）。

1. 推入数组是摊销的O(1)。
2. 使用二分搜索在有序数组中的搜索是O(log(n))。此外，它是具有非常低常数的对数时间。

尽管它很简单，但排序数组是一种平衡二叉搜索树。

Answer 2

如果您使用红黑树，但始终从插入的最后一个节点而不是根节点开始插入，并使用自下而上的插入算法，则插入是 O(1) 摊销的。这意味着构建树将花费 O(n)，而不是 Ω(n log n)。

Answer 3

问题是数据量是未知的。因此，无论输入是否有模式（升序），这棵树都必须是自平衡的。

如果在这种情况下 O(log n) 插入时间是不可接受的（例如对于红黑树），那么我不知道为什么首先需要以平衡二叉树的形式存储它。动态数组上的二进制搜索与树一样快，插入时间平均为 O(1)。

如果事先知道流的大小，那么构建树当然会容易得多。