Incremento de valores en un árbol de búsqueda después de la inserción de un par de clave-valor

Question

Estoy trabajando en un problema de programación y estoy en una barricada. Estoy tratando de encontrar una estructura de datos para mapear un entero arbitrario a otro entero. ¡Puede inclinarse a decir "Tabla Hash"! o "Search Tree!", y de hecho he pensado en esto (e incluso he intentado una implementación sucia). Pero, hay una trampa!

Cada vez que inserte o elimine un valor de la asignación, también deseo aumentar/disminuir (en uno o en algunos desplazamientos arbitrarios) todos los valores superiores o iguales al valor insertado/eliminado.

Aquí hay un ejemplo.

Decir que tengo dos listas de números enteros que voy a utilizar para mis claves y valores en este mapa:

Keys: (1, 6, 18, 21, 24) 
Vals: (2, 1, 3, 0, 4) 

Ahora si añado un par clave-valor (7, 1), quiero incrementar todos los valores mayores que o iguales a 1 que resulta en esto:

Keys: (1, 6, 7, 18, 21, 24) 
Vals: (3, 2, 1, 4, 0, 5) 

y, posteriormente, si elimino el par clave-valor (21, 0), este es el resultado:

Keys: (1, 6, 7, 18, 24) 
Vals: (2, 1, 0, 3, 4) 

Esto es bastante trivial con un par de listas/matrices y algún procesamiento después de cada inserción/eliminación (es decir, revisar los valores y cambiarlos uno a uno).

Pero, estoy buscando una forma de hacerlo de manera más eficiente, tal vez sin tener que pasar por la lista completa de valores y aumentarlos/disminuirlos. Quizás al retrasar el incremento/decremento hasta que se haya solicitado un valor (que debería haberse incrementado/decrementado).

¿Alguna idea?

Answer 1

Creo que si necesita realizar búsquedas rápidas con alguna clave y modificar los resultados en función de los valores reales, necesita dos estructuras de datos: una para clave y otra para valores.

La estructura de datos para la clave va a ser solo una matriz asociativa (impleméntela como una tabla hash, árbol de autoequilibrado o una lista de omisión, no importa) de sus claves a nodos en un árbol para valores.

El árbol de valores va a ser un árbol de búsqueda binaria autoequilibrante (o una lista de saltos, ver edición a continuación). Los nodos en el árbol tienen un delta asociado a ellos, junto con su valor. El delta se aplica a todos los nodos que son mayores o iguales a un nodo particular, es decir, se aplica a sí mismo y a todos los nodos en su subárbol derecho.

Cuando inserta un valor, incrementa el delta de todos los nodos mayores o iguales que el valor que está insertando. Esto incrementa el valor real de todos los nodos cuyo valor es mayor o igual que el valor que está insertando en todo el árbol. La eliminación es similar, usted acaba con el incremento reemplazado por decremento.

Cuando quiere leer un valor, usa la estructura basada en claves para encontrar el nodo en el árbol basado en valores. A continuación, suba a la raíz (para esto, debe mantener los punteros a los padres de los nodos en el árbol) y acumule delta desde los nodos, cuyo valor es mayor o igual que el valor en el nodo donde comenzó.

Debe tener cuidado al hacer el reequilibrio ya que el algoritmo de autoequilibrado que elija requiere, porque debe volver a calcular los deltas de algunos de los nodos, pero esto no debería afectar la complejidad del tiempo.

EDIT: para Skip-lista, la gestión de los deltas es muy fácil: cuando se está buscando un lugar para insertar, delta incremento en todos los nodos de la lista enlazada se compara a que es mayor o igual que el valor que está insertando (lo que también significa que va un nivel más abajo). La eliminación es similar, excepto que debe mover cualquier delta que el elemento eliminado tenga a la derecha.

Cuando desee calcular el valor real de un nodo determinado, suba lo más alto que pueda en el elemento actual, aplique el delta allí (un elemento puede tener deltas de una inserción o eliminación varias veces en diferentes niveles, siempre tiene que usar el valor en el nivel más alto), luego vaya a la lista vinculada un nodo a la izquierda y repita el proceso hasta llegar al ítem más a la izquierda.

La forma en que está accediendo a los nodos también significa que las listas vinculadas deben estar doblemente vinculadas.