Является ли SortedDictionary красно-черным деревом?

Ответ 1

Это не должно документироваться с момента его детализации реализации.

Например, существует более одной реализации SortedDictionary: theres Microsoft и the the Mono.

И реализация Mono фактически использует красно-черное дерево в текущей версии (2.10.9). Так же и в текущей версии .NET(вы можете найти это, декомпилировав код, например, используя Reflector, ildasm.exe или встроенный просмотрщик IL в MonoDevelop).

Однако это, вероятно, изменится в будущем, так как есть фактически более эффективные реализации (as B trees).

Итак, опять же: эта информация не полезна, ее деталь реализации, и она будет изменяться с большой вероятностью.

Ответ 2

Это официальная документация из MSDN;

Общий класс SortedDictionary - это двоичное дерево поиска с O (log n), где n - количество элементов в словаре

Является ли SortedDictionery красно-черным деревом?

Ну, я не слишком разбираюсь в red-black tree, но я просто декомпилировал класс SortedDictionary с dotPeek (что бесплатно), но алгоритм удаления красно-черного дерева и код метода SortedDictionary Remove() не похожи. Итак, мои деньги для Нет.

SortedDictionary сохраняет свои ключи всегда отсортированными. Это позволяет избежать сортировки ключей самостоятельно. Его производительность поиска медленнее, чем Dictionary. Он имеет преимущества, если вам нужна отсортированная таблица поиска в памяти.

Dictionary lookup time:       Close to O(1)
SortedDictionary lookup time: O(log n) 

Подробнее читайте here.

Ответ 3

Документация, похоже, гарантирует O (log n) для извлечения из BST. Если они сообщают "в среднем" с соответствующими деревьям, то даже не балансирующие реализации могут утверждать это. Даже если это была худшая гарантия, это вместе с бытием BST недостаточно, чтобы сказать, является ли оно или не реализовано как красно-черные деревья, не прибегая к декомпиляции. Это также может быть AVL, splay или какой-либо другой балансирующий сорт.

Я вытащил точку заглядывания. На сборке 4.0.0.0. В OrderedDictionary используется Treeset, который подклассы SortedSet. Вероятно, это будет красно-черное дерево. Тем не менее, это не типичный пример, подобный многим примерам в Интернете, который обеспечивает балансировку реализации после вставки или удаления. Реализация в первую очередь повторяется, и вставка, как представляется, исправляет цвета по пути вниз, а не после вставки (сверху вниз - есть пара статей по подобному подходу). Нечто похожее было на удаление, но у него нет времени проверить его. Конечно, не что-то прямо сопоставимое.

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

Ответ 4

На странице MSDN:

Общий класс SortedDictionary - это двоичное дерево поиска с извлечением O (log n), где n - количество элементов в словаре

Ответ 5

Вы можете декомпилировать его (например, с помощью Reflector)... НО, так как это "деталь реализации", я бы не стал полагаться на него, его можно было изменить в любое время с любым обновлением.

Не уверен, насколько релевантна такая деталь реализации, но если вам действительно нужно дерево RedBlack, THEN реализует это явно... все остальное будет "техническим долгом" / "desaster waiting for happen" IMHO.