c++ - 二叉搜索树相对于 C++ vector 的优势

Question

数据结构Binary Search Tree有什么用，如果 vector (按排序顺序)可以支持插入，删除和log(n)时间的搜索(使用二分查找)？

Answer 1

树的基本优点是 vector 中的插入和删除不是 O(log(n)) - 它们是 O(n)。 (他们进行 log(n) 次比较，但移动 n 次。)

vector 的优势在于常数因子可能对它们非常有利(因为它们往往对缓存更友好，而缓存未命中会使您的性能损失 100 倍)。

排序 vector 获胜时

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

什么时候树赢

• 容器中包含许多元素的大量更新。
• 对象移动是昂贵的。

...并且不要忘记 O(1) 搜索的散列容器，以及 un 有序 vector + 线性搜索(对于所有内容都是 O(n)，但如果足够小实际上最快)。