Is SortedDictionary - красно-черное дерево?

Question

Я видел несколько цитат об этом в Интернете, но никакой официальной документации? Может ли кто-нибудь сказать мне, где я могу получить информацию об этом?

Answer 1

Это не должно быть документально оформлено, так как оно представляет собой деталь реализации.

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

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

Однако, это, вероятно, изменится в будущем, так как there are actually more efficient implementations (как B trees).

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

Answer 2

Со своей странице MSDN:

SortedDictionary шаблонный класс представляет собой бинарное дерево поиска с O (Log п) поиска, где п число элементов в словаре

Answer 3

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

Не знаете, насколько важна такая деталь реализации, но если вам действительно нужно дерево RedBlack, THEN реализуйте его явно ... что-нибудь еще будет «техническим долгом»/«desaster ждет, чтобы произойти» ИМХО.

Answer 4

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

SortedDictionary общий класс представляет собой бинарное дерево поиска с O (журнал п) извлечения, где п число элементов в словаре

---

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

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

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

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

Проверьте больше деталей из here.

Answer 5

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

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

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