мне нужно бинарное дерево или другую структуру, в которой я могу хранить объекты с отметкой времени, а затем быстро найти их не только по отметке времени, я знаю, есть, но и целым рядомC# BinaryTree реализация
(timestamp > min && timestamp < max).
Я нашел SortedDictionary и SortedSet, которые реализуют двоичное дерево. То, что мне не хватает, - это возможность искать по диапазону> & & <, не заставляя его (SortedDictionary или SortedSet) внутренне перебирать больше элементов, чем им нужно.
То, что я имею в виду, когда я называю
SortedDictionary.TryGetValue(DateTime.Now, ...
он должен принять логарифмическое время.
Я хочу, чтобы все предметы были между Min и Max в логарифмическом времени. Отсутствует
SortedDictionary.TryGetValueBetween(DateTime.Now-SomeInterval, DateTime.Now+SomeInterval,...
Если бы я сам реализовал двоичное дерево, это не было бы проблемой. Но я не вижу механизма для этого с SortedDictionary или SortedSet. И я не хочу прибегать к линейному времени.
Я просто не нахожу правильных методов или мне действительно нужно реализовать бинарное дерево для получения преимуществ, которые я ищу?
Другие варианты также приветствуются. Есть ли другая структура, которая давала бы мне вставить, удалить и «поиск диапазона» в лог-время или лучше.
Вы не сможете использовать ни один из этих типов BCL. Вам нужно будет использовать собственную или древовидную структуру третьей стороны. – Servy
Когда вы можете терпеть линейное время для вставки (& delete), вы можете использовать простой массив. Старый старый метод [BinarySearch()] (https://msdn.microsoft.com/en-us/library/2cy9f6wb%28v=vs.110%29.aspx) даст вам самый близкий (более низкий) индекс. –
Спасибо Хенк, но нет, мне нужно все 3 в log (n), как я упоминал в вопросе. Однако нашли некоторые решения. См. Мой ответ. –