1

我觉得这必须存在，但我就是想不出来。是否有一种数据结构可以保存排序的值列表并快速搜索（可能像数组一样的 log(N) 时间），并且还支持在 log(N) 或恒定时间内插入和删除元素？

4

1 回答 1

3

这几乎是对平衡二叉搜索树的描述，它按排序顺序存储元素，允许 O(log n) 的插入、删除和查找，并允许 O(n) 遍历所有元素。

有很多方法可以构建平衡的 BST - 有红/黑树、AVL 树、替罪羊树、展开树、AA 树、treaps、(a, b)-树等。任何这些都可以解决您的问题。其中，展开树可能是最容易编码的，其次是 AA 树和 AVL 树。

希望这可以帮助！

于 2013-07-15T06:15:05.687 回答