擅长:python、mysql、java
<p>据我所知,没有什么特别的原因-我想原因是对于许多应用程序来说,经过高度优化的<code>dict</code>和<code>set</code>实现(它们是哈希表)工作得很好。它们在大多数情况下都足够好。在某些情况下,您肯定需要平衡的二进制搜索树的性能特性(比如基于键的有序遍历,而不是加法顺序),但是这些特性已经远远偏离了常规路径,人们很乐意在这种情况下获取第三方包。</p>
<p>我在PyPI上使用<a href="https://pypi.python.org/pypi/bintrees/">bintrees</a>包有很好的经验。它在纯Python和<a href="http://cython.org/">Cython</a>中都实现了不平衡、AVL和红黑二叉树。</p>
<p>我认为其余的原因本质上是历史偶然。如果编写bintrees的人游说将其包含在stdlib中,并且愿意忍受对维护和发布的限制,那么它很可能会加入。(我想,尽管Cython依赖性会引起问题。)</p>
<p><strong>算法复杂度:</strong></p>
<p>对于哈希表(如dict或set),插入和查找是O(1),而对于平衡树,插入和查找是O(log(n))。在树中,键的遍历顺序是O(n),但是要对哈希表执行相同的操作,需要首先对键进行排序,所以是O(n*log(n))。在选择要使用哪种数据结构时,需要考虑要使用哪种操作,并选择在应用程序中最有意义的折衷方案。</p>