用于获取小于给定数字的所有数字的数据结构

Question

哪种数据结构最适合插入，删除和获取所有元素之类的查询其值小于给定数字。 BST还是优先队列？或任何其他数据结构。

Answer 1

BST似乎是您需要的那个。插入，删除的复杂度为O（h）。使所有元素都小于给定数也为O（h），您只需要进行预遍历即可找到整个左树的节点。

h是树的高度。

如果您想更稳定，保持AVL可以使您比BST拥有O（logn）复杂度。