En informática , una aproximación al problema de optimización dinámica de algoritmos en línea para árboles de búsqueda binarios implica reformular el problema geométricamente, en términos de aumentar un conjunto de puntos en el plano con la menor cantidad posible de puntos adicionales para evitar rectángulos con solo dos puntos en su límite. [1]
Como suele formularse, el problema del árbol de búsqueda binaria en línea implica árboles de búsqueda definidos sobre un conjunto de claves fijas . Una secuencia de acceso es una secuencia ... donde cada acceso pertenece al conjunto de claves.
Cualquier algoritmo particular para mantener árboles de búsqueda binarios (como el algoritmo de árbol splay o la estructura de conjunto de trabajo de Iacono ) tiene un costo por cada secuencia de acceso que modela la cantidad de tiempo que tomaría usar la estructura para buscar cada una de las claves en el secuencia de acceso a su vez. El costo de una búsqueda se modela asumiendo que el algoritmo del árbol de búsqueda tiene un único puntero a un árbol de búsqueda binario, que al inicio de cada búsqueda apunta a la raíz del árbol. Luego, el algoritmo puede realizar cualquier secuencia de las siguientes operaciones:
La búsqueda requiere, en algún punto dentro de esta secuencia de operaciones, mover el puntero a un nodo que contiene la clave, y el costo de la búsqueda es el número de operaciones que se realizan en la secuencia. El costo total A ( X ) para el algoritmo A en la secuencia de acceso X es la suma de los costos de las búsquedas para cada clave sucesiva en la secuencia.
Como es estándar en el análisis competitivo , la relación competitiva de un algoritmo A se define como el máximo, sobre todas las secuencias de acceso, de la relación entre el costo de A y el mejor costo que cualquier algoritmo podría lograr:
La conjetura de la optimización dinámica establece que los árboles extendidos tienen una proporción competitiva constante, pero esto aún no se ha demostrado. La visión geométrica de los árboles de búsqueda binarios proporciona una forma diferente de entender el problema que ha llevado al desarrollo de algoritmos alternativos que también podrían (conjeturalmente) tener una relación competitiva constante.
En la vista geométrica del problema del árbol de búsqueda binaria en línea, una secuencia de acceso (secuencia de búsquedas realizadas en un árbol de búsqueda binaria (BST) con un conjunto de claves ) se asigna al conjunto de puntos , donde el eje X representa el espacio de claves. y el eje Y representa el tiempo; al que se suma un conjunto de nodos tocados . Por nodos tocados nos referimos a lo siguiente. Considere un algoritmo de acceso BST con un único puntero a un nodo del árbol. Al comienzo de un acceso a una clave determinada , este puntero se inicializa en la raíz del árbol. Siempre que el puntero se mueve o se inicializa en un nodo, decimos que el nodo es tocado. [2] Representamos un algoritmo BST para una secuencia de entrada determinada dibujando un punto para cada elemento que se toca.
Por ejemplo, supongamos que se proporciona el siguiente BST en 4 nodos:
El conjunto de claves es {1, 2, 3, 4}.
Sea 3, 1, 4, 2 la secuencia de acceso.
Los toques se representan geométricamente: si se toca un elemento x en las operaciones para el iésimo acceso, entonces se traza un punto ( x , i ).
Se dice que un conjunto de puntos está satisfecho arbóricamente si se cumple la siguiente propiedad: para cualquier par de puntos que no se encuentran en la misma línea horizontal o vertical, existe un tercer punto que se encuentra en el rectángulo abarcado por los dos primeros puntos (ya sea dentro o en el límite).
Un conjunto de puntos que contiene los puntos se satisface arboralmente si y sólo si corresponde a un BST válido para la secuencia de entrada .
Primero, demuestre que el punto establecido para cualquier algoritmo BST válido se cumple arbóricamente. Considere los puntos y , donde x se toca en el momento i y y se toca en el momento j . Supongamos por simetría que y . Es necesario demostrar que existe un tercer punto en el rectángulo con esquinas como y . También denotemos el ancestro común más bajo de los nodos a y b justo antes del tiempo t . Hay algunos casos:
A continuación, muestre la otra dirección: dado un conjunto de puntos arbóricamente satisfecho, se puede construir un BST válido correspondiente a ese conjunto de puntos. Organice nuestro BST en un grupo que esté organizado en orden de montón al momento del siguiente toque. Tenga en cuenta que el tiempo del siguiente toque tiene vínculos y, por lo tanto, no está definido de forma única, pero esto no es un problema siempre que haya una manera de romper los vínculos. Cuando llegué al momento , los nodos tocados forman un subárbol conectado en la parte superior, mediante la propiedad de ordenación del montón. Ahora, asigne nuevos tiempos de siguiente toque para este subárbol y reorganícelo en un nuevo grupo local. Si un par de nodos, x e y , se extienden a ambos lados del límite entre la parte tocada y la no tocada del treap, entonces si y debe tocarse antes que x , entonces es un rectángulo insatisfecho porque el punto más a la izquierda sería el hijo derecho de x. , no y .
Encontrar la mejor ejecución BST para la secuencia de entrada es equivalente a encontrar el superconjunto de puntos de cardinalidad mínima (que contiene la entrada en representación geométrica) que se satisface arboralmente. Se sabe que el problema más general de encontrar el superconjunto de cardinalidad mínima satisfecho arboralmente de un conjunto general de puntos de entrada (no limitado a un punto de entrada por coordenada y ) es NP-completo . [1]
El siguiente algoritmo codicioso construye conjuntos arbóricamente satisfactibles:
Se ha conjeturado que el algoritmo es óptimo dentro de un término aditivo. [3]
La geometría de los árboles de búsqueda binarios se ha utilizado para proporcionar un algoritmo que es dinámicamente óptimo si cualquier algoritmo de árbol de búsqueda binario es dinámicamente óptimo. [4]
