疑问：用AVL树或红黑树实现的字典为何称时间复杂度O(1)？

• 先搞清楚一个核心点：字典是抽象数据类型（ADT），它只规定了键值对操作的接口（查找、插入、删除等），没限定具体实现方式，所以不同实现的时间复杂度肯定不一样。
• 很多编程语言里的默认字典（比如Python的dict、Java的HashMap）是用哈希表实现的，这种实现下，查找、插入、删除的平均时间复杂度是O(1)，这也是大家常说字典是O(1)的原因——指的是这个主流实现的平均场景。
• 要是用AVL树或者红黑树来实现字典（比如Java的TreeMap），不管是平均还是最坏情况，这些操作的时间复杂度都是O(logN)。这种实现的好处是能保证键的有序性，还支持范围查询这类哈希表做不到的操作。
• 说白了，“字典时间复杂度是O(1)”是特指哈希表实现的平均情况；平衡BST实现的字典就是O(logN)，两者不矛盾，只是对应不同的实现方案而已。

内容的提问来源于stack exchange，提问作者hongpower