3

更具体地说,如果使用 AVL 树而不是哈希表,是否可以更有效地执行任何操作?

4

2 回答 2

5

我通常更喜欢 AVL 树而不是哈希表。我知道哈希表的预期时间 O(1) 复杂度胜过 AVL 树的保证时间 O(log n) 复杂度,但在实践中,常数因素使这两种数据结构通常具有竞争力,并且没有任何琐碎的担忧一些引起不良行为的意外数据。此外,我经常发现在程序的维护生命周期中的某个时候,在未预见到的情况下,哈希表的初始选择似乎是正确的,我需要按排序顺序的数据,所以我最终重写程序以使用AVL 树而不是哈希表;这样做足够多的时间,你就会知道你不妨从 AVL 树开始。

如果您的键是字符串,则三元搜索尝试提供了 AVL 树或哈希表的合理替代方案。

于 2012-01-12T18:46:59.573 回答
0

当然,一个明显的区别是,使用 AVL 树(和其他平衡树),您可以具有持久性:您可以在 O(log N) 空间和时间中从树中插入/删除一个元素,最终结果不是刚出新树,老树也得保住。

使用哈希表,您通常无法在少于 O(N) 的时间和空间内完成此操作。

另一个重要的区别是键所需的操作:AVL 树需要<=键之间的比较,而哈希表需要=比较和hash函数。

于 2016-04-05T16:56:14.273 回答