下表总结了各种字典结构的渐进时间性能，其中的函数都是 O() 的
最坏情况
| 方法 | 查找 | 插入 | 删除 |
|---|---|---|---|
| 有序数组 | O(logn) | O(n) | O(n) |
| 有序链表 | O(n) | O(n) | O(n) |
| 跳表 | O(n) | O(n) | O(n) |
| 哈希表 | O(n) | O(n) | O(n) |
| 二叉搜索树 | O(n) | O(n) | O(n) |
| AVL 树 | O(logn) | O(logn) | O(logn) |
| 红黑树 | O(logn) | O(logn) | O(logn) |
| 分裂树 | O(n) | O(n) | O(n) |
| B 树 | O(logn) | O(logn) | O(logn) |
平均情况
| 方法 | 查找 | 插入 | 删除 |
|---|---|---|---|
| 有序数组 | O(logn) | O(n) | O(n) |
| 有序链表 | O(n) | O(n) | O(n) |
| 跳表 | O(logn) | O(logn) | O(logn) |
| 哈希表 | O(1) | O(1) | O(1) |
| 二叉搜索树 | O(logn) | O(logn) | O(logn) |
| AVL 树 | O(logn) | O(logn) | O(logn) |
| 红黑树 | O(logn) | O(logn) | O(logn) |
| 分裂树 | O(logn) | O(logn) | O(logn) |
| B 树 | O(logn) | O(logn) | O(logn) |
注：
STL 类 map 和 multimap 使用的是 红黑树结构，以保证查找、插入和删除操作具有对数级的时间性能。
在实际应用中，当要实施的操作都是按关键字进行查找、插入和删除时，认为散列技术在性能方面超过了平衡搜索树，因此，优先选择散列技术。如果是按关键字实施字典操作，而且操作时间不能超过指定的范围，这时提倡使用平衡搜索树。对于那些按名次实施的查找和删除操作，还有那些不按精确的关键字匹配所进行的字典操作（例如寻找关键字大于 k 的最小元素），建议使用平衡搜索树。
AVL 树和红黑树都使用“旋转”来保持平衡。AVL 树对每个插入操作最多需要一次旋转，对每个删除操作最多需要 O(logn) 次旋转。而红黑树对每个插入和删除操作，都只需要一次旋转。
为什么STL使用红黑树作为平衡树的实现？
答：（以下答案引用知乎：https://www.zhihu.com/question/20545708/answer/58717264，侵删）
至于, 为什么不用 AVL 树作为底层实现, 那是因为 AVL 树是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大. 红黑树插入只要两次旋转, 删除至多三次旋转. 但不可否认的是, AVL 树搜索的效率是非常稳定的. 选取红黑树, 我认为是一种折中的方案.
黑体字是不正确的，对AVL插一个node或者删一个node，显然不需要每次都做rotation来维持balance。且AVL插入最多也只需要2次旋转。下面是我的回答：
- 如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。
- 其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。
- map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。