сбалансированная древовидная структура данных, которая изменяется до простых размеров

Question

Относительно этого: вопрос переполнения стека ,

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

Что такое древовидная структура данных за словарями .Net?

Спасибо.

Answer 1

Словари .Net реализованы в виде hastables, что вовсе не является древовидной структурой данных.Вопрос , на который вы ссылаетесь , объясняет, почему размер хеш-таблиц лучше изменить на простое число.

Что касается древовидных структур, я не могу представить цель изменения размера на простое число.Это не имеет особого смысла.Тем не менее, имеет смысл изменить размер сбалансированной древовидной структуры до полного дерева, которое для двоичного дерева будет 2 ⁿ -1.

Answer 2

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

.NET SortedDictionary использует Красно-черное дерево для поддержки пар ключ / значение.Так как красно-черное дерево хранится не в фиксированном массиве, а скорее как ряд на узлах с левыми / правыми дочерними узлами, на самом деле не существует никакой концепции определения размеров, поскольку узлы добавляются в дерево, в которое поворачивается деревоподдерживать баланс.