二进制搜索树优于C++中的向量

Question

如果vector(按排序顺序)可以支持在log(n)时间内插入,删除和搜索(使用二进制搜索),那么二进制搜索树有什么用？

Answer 1

树的基本优点是向量中的插入和删除不是 O(log(n)) - 它们是O(n).(他们进行log(n)比较,但n移动.)

向量的优点是常数因子可以有利于他们的是巨大的(因为他们往往更加缓存友好,高速缓存未命中可以花费你100倍的性能).

排序的向量赢得了

• 主要是搜索.
• 频繁更新,但容器中只有少数元素.
• 对象具有高效的移动语义

树木赢了

• 容器中有许多元素的大量更新.
• 对象移动很昂贵.

......不要忘记哈希容器它是O(1)搜索,以及联合国下令载体+线性搜索(这是为O(n)的一切,但如果足够小,实际上是最快的).