algorithm - teoria - ¿Qué invariante mantienen los árboles RRB?
teoria de grafos ejercicios resueltos pdf (2)
@mcdowella tiene razón, eso dicen sobre los nodos relajados. Pero si está dividiendo y uniendo nodos, un rango de m a m -1 significa que a veces tendrá que ajustar hasta m -1 ( m -2?) Para agregar o eliminar un solo elemento de un nodo. Esto parece horriblemente ineficiente. Creo que significaron entre m y (2 m ) - 1 porque esto permite que los nodos se dividan en 2 cuando se vuelven demasiado grandes, o 2 nodos que se unen en uno cuando son demasiado pequeños sin tener que cambiar un tercer nodo. Así que es un error tipográfico que falta el "2" en "2 m " en el documento. La tesis de maestría de Jean Niklas L''orange me apoya en esto.
Además, todos los nodos estrictos tienen la misma longitud que debe ser una potencia de 2. La razón de esto es una optimización en Clojure PersistentVector de Rich Hickey. Bueno, creo que lo importante es empaquetar todos los nodos estrictos (más sobre esto más adelante) para que no tengas que adivinar qué rama del árbol descender. Pero ser capaz de cambiar de bit y enmascarar en lugar de dividir es una buena ventaja. No cronometré la operación get () en un Scala Vector relajado, pero el vector Paguro relajado es aproximadamente 10 veces más lento que el estricto . Por lo tanto, hace todo lo posible por ser lo más estricto posible, incluso produciendo 2 niveles estrictos si inserta repetidamente en 0.
Su árbol también tiene una altura uniforme: todos los nodos de las hojas están a la misma distancia de la raíz. Creo que aún funcionaría si los árboles relajados tuvieran que estar dentro, digamos, de un nivel a otro, aunque no estoy seguro de lo que eso te compraría.
Los nodos relajados pueden tener hijos estrictos, pero no al revés.
Los nodos estrictos deben rellenarse desde la izquierda (índice bajo) sin espacios. Cualquier nodo Strict no completo debe estar en el borde derecho (alto índice) del árbol. Todos los nodos de hoja estricta siempre pueden estar llenos si se agrega en un enfoque o una cola (más sobre esto más adelante).
Puede ver la mayoría de los invariantes buscando los métodos debugValidate () en la implementación de Paguro . Ese no es su papel, pero se basa principalmente en eso. En realidad, las variables de "visualización" en la implementación de Scala tampoco se mencionan en el documento. Si vas a estudiar estas cosas, es probable que desees comenzar por echar un vistazo a Clojure PersistentVector porque el árbol RRB tiene uno dentro. Las dos diferencias entre eso y el árbol RRB son 1. el árbol RRB permite nodos "relajados" y 2. el árbol RRB puede tener un "enfoque" en lugar de una "cola". Tanto el enfoque como la cola son pequeños búferes (tal vez el mismo tamaño que un nodo de hoja estricto), con la diferencia de que el enfoque probablemente se localizará en el área del vector que se insertó o agregó por última vez, mientras que la cola siempre está al final (PerSistentVector solo se puede agregar a, nunca se debe insertar en). Estas 2 diferencias son las que permiten O (log n) inserciones y eliminaciones arbitrarias, más las operaciones O (log n) split () y join ().
Los árboles balanceados con radix relajado ( árboles RRB) son una generalización de vectores inmutables (utilizados en Clojure y Scala) que tienen tiempos de actualización y indexación "efectivamente constantes". Los árboles RRB mantienen una indexación y actualización eficientes, pero también permiten una concatenación eficiente (log n).
Los autores presentan la estructura de datos de una manera que me resulta difícil de seguir. No estoy muy seguro de qué es lo invariable que mantiene cada nodo.
En la sección 2.5, describen su algoritmo. Creo que se están asegurando de que la indexación en el nodo solo requerirá e pasos adicionales de búsqueda lineal después de la búsqueda de radix. No entiendo cómo derivaron su fórmula para los pasos adicionales, y creo que quizás no estoy seguro de qué significan cada una de las variables (en particular, "un total de p ramas de sub-árboles").
¿Cómo funciona el algoritmo de concatenación de árbol RRB?
Describen un invariante en la sección 2.4 "Sin embargo, como se mencionó anteriormente, los nodos B-Trees no facilitan la búsqueda de radix. En su lugar, elegimos el invariante inicial de permitir que los tamaños de los nodos varíen entre m y m 1. Esto define una familia de balanceados árboles que comienzan con 2-3 árboles bien conocidos, 3-4 árboles y (para m = 32) 31-32 árboles. Este invariante asegura el equilibrio y logra la búsqueda de la rama de radix en la mayoría de los casos. Ocasionalmente se necesita una búsqueda lineal de algunos pasos después de la búsqueda de radix para encontrar la rama correcta. Los pasos adicionales requeridos aumentan en los niveles más altos ".
Mirando su fórmula, parece que han calculado el número máximo y mínimo posible de valores almacenados en un subárbol. La diferencia entre los dos es la diferencia máxima posible entre el número máximo y mínimo de valores debajo de un punto. Si divide esto por el número de valores debajo de una ranura, tiene el número máximo de ranuras en las que podría estar desconectado cuando calcule qué ranura buscar para ver si contiene el índice que está buscando.