Самый эффективный способ найти индекс элемента в SortedDictionary

Я использую отсортированный словарь для ведения списка элементов, из которых мне регулярно нужно следить за состоянием верхних элементов x. Каждый раз, когда я обновляю элемент, я хотел бы быстро выяснить, какой индекс использует элемент, на который я ссылаюсь. Я понимаю, что могу перечислить весь список и сосчитать мою позицию, но я ищу что-то с O(log n) или лучше, после того как весь отсортированный словарь находится в дереве RedBlack. Каждый узел должен иметь возможность отслеживать своих дочерних элементов, и это должен быть быстрый расчет.

Источник

2 ответа

Решение

Вы можете просто изменить свой SortedDictionary<TKey, TValue> в SortedList<TKey, TValue> а затем использовать IndexOfKey(key):

var s = new SortedList<string, string>
    { { "a", "Ay" }, { "b", "Bee" }, { "c", "Cee" } };

// Outputs 1
Console.WriteLine(s.IndexOfKey("b"));

IndexOfKey внутренне использует Array.BinarySearch<TKey>(), так что это будет O (log n), что быстрее, чем O (n) (что было бы, если бы вы искали спереди назад, просматривая его).

Источник

Древовидная структура может быть построена для доступа к элементам по индексу или отчета об индексе существующего элемента за время lgN, что требует очень небольшого дополнительного времени для вставок и удалений. Один из способов сделать это - отслеживать количество элементов в левой и правой ветвях каждого узла (при вставке или удалении измените количество узлов родительских узлов при изменении количества дочерних узлов). Однако, если древовидная структура не предоставляет такой возможности, я не знаю простого способа ее модернизации.

Источник
Другие вопросы по тегам