从排序数字流生成平衡二叉搜索树的最佳方法
Optimal Way To Generate A Balanced Binary Search Tree From A Stream Of Sorted Numbers
我有一个按升序排列的整数输入流，我的任务是根据该流即时创建一个平衡二叉搜索树。我已经浏览了 link:BBST from a stream of integers 并了解到我们可以利用红黑树。问题是，我正在寻找使用输入数据中的 'sorted information' 的更优解决方案。
如果元素是按排序顺序排列的，那么最简单和最有效的做法可能就是将每个元素推到 dynamic array 的末尾（一个数组，当它变成例如，已满）。
- 推入数组是amortized O(1).
- 排序数组中的搜索是 O(log(n)) 使用 binary search。而且，它是常数非常小的对数时间。
尽管排序数组很简单，但它是一种平衡二叉搜索树。
问题是数据量未知。因此，无论输入是否有模式（升序），这棵树必须是自平衡的。
如果 O(log n) 插入时间在这种情况下是不可接受的（比如红黑树），那么我不知道为什么你需要首先以平衡二叉树形式存储它地方。对动态数组进行二分查找与树一样快，插入时间为 O(1)。
如果事先知道流的大小，那么构建树当然会容易得多。
如果您使用红黑树但总是从插入的最后一个节点开始插入，而不是从根节点开始插入，并且使用自下而上的插入算法，则插入的时间复杂度为 O(1)。这意味着构建树的成本为 O(n)，而不是 Ω(n log n)。
我有一个按升序排列的整数输入流，我的任务是根据该流即时创建一个平衡二叉搜索树。我已经浏览了 link:BBST from a stream of integers 并了解到我们可以利用红黑树。问题是，我正在寻找使用输入数据中的 'sorted information' 的更优解决方案。
如果元素是按排序顺序排列的，那么最简单和最有效的做法可能就是将每个元素推到 dynamic array 的末尾（一个数组，当它变成例如，已满）。
- 推入数组是amortized O(1).
- 排序数组中的搜索是 O(log(n)) 使用 binary search。而且，它是常数非常小的对数时间。
尽管排序数组很简单，但它是一种平衡二叉搜索树。
问题是数据量未知。因此，无论输入是否有模式（升序），这棵树必须是自平衡的。
如果 O(log n) 插入时间在这种情况下是不可接受的（比如红黑树），那么我不知道为什么你需要首先以平衡二叉树形式存储它地方。对动态数组进行二分查找与树一样快，插入时间为 O(1)。
如果事先知道流的大小，那么构建树当然会容易得多。
如果您使用红黑树但总是从插入的最后一个节点开始插入，而不是从根节点开始插入，并且使用自下而上的插入算法，则插入的时间复杂度为 O(1)。这意味着构建树的成本为 O(n)，而不是 Ω(n log n)。