какую структуру данных использовать для получения всех чисел меньше заданного числа

Question

Какая структура данных наиболее подходит для таких запросов, как вставка, удаление и получение всех элементов, значение которых меньше заданного числа. BST или приоритетная очередь? или любая другая структура данных.

Answer 1

BST похоже на то, что вам нужно. Вставка, удаление со сложностью O (h). Получение всех элементов меньше заданного числа также является O (h), вам просто нужен обход перед порядком, чтобы найти узел всего левого дерева.

h - высота дерева.

Если вы хотите быть более стабильным, поддержка AVL дает вам сложность O (logn) по сравнению с BST.