其实二叉搜索树的优势已经在与查找、插入的时间复杂度上了，通常只有O(log n)，很多集合都是通过它来实现的。在进行插入的时候，实质上是给树添加新的叶子节点，避免了节点移动，搜索、插入和删除的复杂度等于树的高度，属于O(log n)，最坏情况下整棵树所有的节点都只有一个子节点，完全变成一个线性表，复杂度是O(n)。
Trie树在最坏情况下查找要快过二叉搜索树，如果搜索字符串长度用m来表示的话，它只有O(m)，通常情况（树的节点个数要远大于搜索字符串的长度）下要远小于O(n)。
我们给Trie树举例子都是拿字符串举例的，其实它本身对key的适宜性是有严格要求的，如果key是浮点数的话，就可能导致整个Trie树巨长无比，节点可读性也非常差，这种情况下是不适宜用Trie树来保存数据的；而二叉搜索树就不存在这个问题。
和Hash表相比
考虑一下Hash表键冲突的问题。Hash表通常我们说它的复杂度是O(1)，其实严格说起来这是接近完美的Hash表的复杂度，另外还需要考虑到hash函数本身需要遍历搜索字符串，复杂度是O(m)。在不同键被映射到"同一个位置"（考虑closed hashing，这"同一个位置"可以由一个普通链表来取代）的时候，需要进行查找的复杂度取决于这"同一个位置"下节点的数目，因此，在最坏情况下，Hash表也是可以成为一张单向链表的（对于Hash冲突问题，请阅读《Hash Collision DoS问题》）。
Trie树可以比较方便地按照key的字母序来排序（整棵树先序遍历一次就好了），这是绝大多数Hash表是不同的（Hash表一般对于不同的key来说是无序的）。
在较理想的情况下，Hash表可以以O(1)的速度迅速命中目标，如果这张表非常大，需要放到磁盘上的话，Hash表的查找访问在理想情况下只需要一次即可；但是Trie树访问磁盘的数目需要等于节点深度。
很多时候Trie树比Hash表需要更多的空间，我们考虑这种一个节点存放一个字符的情况的话，在保存一个字符串的时候，没有办法把它保存成一个单独的块。Trie树的节点压缩可以明显缓解这个问题，后面会讲到。
和后缀树相比
Read full article from Trie树和其它数据结构的比较 | 四火的唠叨
No comments:
Post a Comment