.net - profundidad - recorrido de arboles
estructura de datos equilibrada similar a un árbol que cambia el tamaño a tamaños primarios (2)
En relación con esto: pregunta de desbordamiento de pila ,
donde descubrí que los diccionarios .Net cambian de tamaño al siguiente tamaño principal que es al menos dos veces el tamaño actual, me preguntaba si existe alguna estructura de datos similar a un árbol equilibrada que pueda redimensionarse a tamaños primarios (similar a B-Trees o Binomial árboles tal vez).
¿Cuál es la estructura de datos similar a un árbol detrás de los diccionarios de .Net?
Gracias.
El diccionario utiliza un algoritmo de tabla hash , que almacena los datos en una matriz, es esta matriz que se dimensiona / se vuelve a clasificar según los números primos.
.NET SortedDictionary utiliza una estructura de árbol rojo-negro para mantener los pares clave / valor. Como el árbol rojo-negro no está almacenado en una matriz fija, sino como una serie en nodos con nodos secundarios izquierdo / derecho, no hay realmente un concepto de tamaño, ya que los nodos se agregan al árbol al que se rota el árbol. mantener el equilibrio.
Los diccionarios de .Net se implementan como parables, que no es una estructura de datos tipo árbol en absoluto. La pregunta a la que se vincula explica por qué las tablas hash se redimensionan mejor a un número primo.
En cuanto a las estructuras de árbol, no puedo imaginar un propósito para cambiar el tamaño a un primer plano. No tiene mucho sentido. Sin embargo, lo que tiene sentido es cambiar el tamaño de una estructura de árbol balanceada a un árbol completo, que para un árbol binario sería 2 n -1.