Двоичные деревья C# и словари

Я думал, что BST предполагалось быть более эффективным памятью, но кажется что один узел дерева требует больше байтов, чем одна запись в Словарь. Что дает? Есть ли указать, где BST лучше, чем Словари?

Я лично никогда не слышал о таком принципе. Даже еще его только общий принцип, а не категорический факт, оформленный в ткани вселенной.

Вообще, словари - это действительно просто модная обертка вокруг массива связанных списков. Вы вставляете в словарь что-то вроде:

LinkedList<Tuple<TKey, TValue>> list =
    internalArray[internalArray % key.GetHashCode()];
if (list.Exists(x => x.Key == key))
    throw new Exception("Key already exists");
list.AddLast(Tuple.Create(key, value));

так его почти O (1) операция. Словарь использует память o (InternationArray.length + N), где n представляет собой количество элементов в коллекции.

В целом BSTS может быть реализован как:

• связанные списки, которые используют пространство O (N), где n представляет собой числовые элементы в коллекции.
• Массивы , которые используют O (2 ^H - N) пространство, где H - высота дерева, а N - количество предметов в коллекции.
  • Поскольку красно-черные деревья имеют ограниченную высоту O (1.44 * N), реализация массива должна иметь ограниченное использование памяти около O (2 ^1.44N - N)

, Treeneionary C5 реализован с использованием массивов, которые, вероятно, ответственны за потраченное пространство.

Что дает? Есть ли точка в том, где BST лучше, чем словари?

словари имеют некоторые нежелательные свойства:

• Не может быть недостаточно непрерывных блоков памяти для удержания вашего словаря, даже если его требования к памяти намного меньше, чем общая доступная ОЗУ.

• Оценка хеш-функции может принимать произвольно долгую продолжительность времени. Строки, например, используют отражатель для изучения метода System.String.GethashCode - вы заметите хеширование строки, всегда принимают o (n) время, что означает, что он может занять значительное время для очень длинных струн Отказ С рукой, сравнивая строки для неравенства почти всегда быстрее, чем хеширование, поскольку это может потребовать смотреть на первые несколько символов. Это полностью возможно для вставок дерева, чтобы быть быстрее, чем словарные вставки, если оценка хеш-кода занимает слишком длинную.

  • INT32 Метод gethashcode буквально просто возвращает это , поэтому вы были бы сблудочены, чтобы найти случай, когда hashtable с ключами int медленнее, чем словарь дерева.

RB-деревья имеют некоторые желательные свойства:

• Вы можете найти / удалить минимальные и максимальные элементы в O (log n), по сравнению с o (n) временем с использованием словаря.

• Если дерево реализуется как связанный список, а не массив, дерево - это обычно больше пространства эффективно, чем в словаре.

• Аналогично, его смешное легко писать неизменные версии деревьев, которые поддерживают вставку / поиск / удаление в O (log n). Словари не адаптируются к неизменности, поскольку вам нужно скопировать весь внутренний массив для каждой операции (на самом деле, I имеет , наблюдал . , но реализация очень сложная).

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

Итак, выбор структуры данных действительно зависит от того, какие свойства вам нужны. Если вы просто хотите неупорядоченную сумку и можете гарантировать, что ваша хэш-функция быстро оценивается, переходите с .NET-словарь. Если вам нужна упорядоченная сумка или иметь медленную работу хэш-функции, перейдите с TreeneySionary.