归档 2015年4月2日

二叉搜索树(BST)相较于哈希表的优势

哈希表支持在Θ(1)时间内完成下列操作:

1) 查找
2) 插入
3) 删除

对于自平衡的二叉搜索树,比如红黑树(Red-Black Tree),平衡二叉树(AVL Tree),伸展树(Splay Tree)等,上述操作的时间复杂度是O(Logn)。

因此对于常用操作哈希表似乎完胜BST。那么我们在什么时候应该选择BST而不是哈希表,BST的优势何在。下面是BST的几项比较重要的优势。

我们只需通过中序遍历BST即可获得排好序的key列表。而这并非哈希表的自然操作,需要额外的工作才可以实现。

使用BST可以很容易地执行顺序统计,找出最接近的最小和最大元素,执行范围查询。像排序一样,这些操作也不是哈希表的自然操作。

BST相较于哈希表更容易实现,我们可以很容易地实现自定义的BST。而要实现哈希表,我们一般需要依赖编程语言提供的库函数。

使用BST,所有的操作都可以确保在O ...

继续阅读

昨天

明天

归档