Geometría de los árboles de búsqueda binaria

En ciencias de la computación , un enfoque al problema de optimalidad dinámica en algoritmos en línea para árboles de búsqueda binaria 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 borde. ^{[ 1 ]}

Secuencias de acceso y ratio competitivo

Tal como se formula habitualmente, el problema del árbol de búsqueda binaria en línea implica árboles de búsqueda definidos sobre un conjunto fijo de claves. $\{1,2,...,n\}$ Una secuencia de acceso es una secuencia $x_{1},x_{2},$ ... donde cada acceso $x_{i}$ pertenece al conjunto de claves.

Cualquier algoritmo particular para mantener árboles de búsqueda binaria (como el algoritmo de árbol splay o la estructura de conjunto de trabajo de Iacono ) tiene un costo para cada secuencia de acceso que modela la cantidad de tiempo que tomaría usar la estructura para buscar cada una de las claves en la secuencia de acceso por turno. 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 binaria, que al comienzo de cada búsqueda apunta a la raíz del árbol. El algoritmo puede entonces realizar cualquier secuencia de las siguientes operaciones:

Mueva el puntero a su hijo izquierdo.
Mueva el puntero a su hijo derecho.
Mueve el puntero a su elemento padre.
Realiza una única rotación de árbol sobre el puntero y su elemento padre.

En algún punto de esta secuencia de operaciones, se requiere realizar una búsqueda para mover el puntero a un nodo que contenga la clave. El costo de la búsqueda es el número de operaciones realizadas en la secuencia. El costo total _A ( X ) del 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 habitual en el análisis competitivo , la razón competitiva de un algoritmo A se define como el máximo, sobre todas las secuencias de acceso, de la razón entre el coste de A y el mejor coste que cualquier algoritmo podría alcanzar:

\rho _{A}=\sup _{X}{\frac {\mathrm {cost} _{A}(X)}{\mathrm {cost} _{\mathrm {opt} }(X)}}.

La conjetura de optimalidad dinámica afirma que los árboles splay tienen una razón de competitividad constante, pero esto aún no se ha demostrado. La perspectiva geométrica de los árboles de búsqueda binaria ofrece una forma diferente de comprender el problema, lo que ha llevado al desarrollo de algoritmos alternativos que también podrían (conjeturalmente) tener una razón de competitividad constante.

Traducción a un conjunto de puntos geométricos

En la vista geométrica del problema del árbol de búsqueda binaria en línea, una secuencia de acceso $x_{1},...,x_{m}$ (secuencia de búsquedas realizadas en un árbol de búsqueda binaria (BST) con un conjunto de claves) ${1,2,...,n}$ ) se asigna al conjunto de puntos ${(x_{i},i)}$ donde el eje X representa el espacio de claves y el eje Y representa el tiempo; al cual se agrega un conjunto de nodos tocados . Por nodos tocados entendemos lo siguiente. Consideremos un algoritmo de acceso a BST con un solo puntero a un nodo en el árbol. Al comienzo de un acceso a una clave dada $x_{i}$ Este puntero se inicializa en la raíz del árbol. Cuando el puntero se mueve a un nodo o se inicializa en él, decimos que el nodo se toca. ^{[ 2 ]} Representamos un algoritmo BST para una secuencia de entrada dada dibujando un punto por cada elemento que se toca.

Por ejemplo, supongamos que se da el siguiente BST de 4 nodos: El conjunto de claves es {1, 2, 3, 4}.

Mapeo de la secuencia de acceso 3, 1, 4, 2 solamente.

Una representación geométrica del algoritmo del árbol de búsqueda binaria.

Sea 3, 1, 4, 2 la secuencia de acceso.

En el primer acceso, solo se modifica el nodo 3.
En el segundo acceso, se tocan los nodos 3 y 1.
En el tercer acceso, se tocan los números 3 y 4.
En el cuarto acceso, pulse 3, luego 1 y después 2.

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 ).

Conjuntos de puntos satisfechos arbóreamente

Se dice que un conjunto de puntos satisface arborológicamente la condición si se cumple la siguiente propiedad: para cualquier par de puntos que no se encuentren en la misma línea horizontal o vertical, existe un tercer punto que se encuentra dentro del rectángulo formado por los dos primeros puntos (ya sea dentro o en el límite).

Teorema

Un conjunto de puntos que contiene los puntos $(x_{i},i)$ se satisface arbóreamente si y solo si corresponde a un BST válido para la secuencia de entrada. $x_{1},x_{2},...,x_{m}$ .

Prueba

Primero, demuestre que el conjunto de puntos para cualquier algoritmo BST válido se satisface arborológicamente. Considere los puntos $(x,i)$ y $(y,j)$ donde $x$ se toca en el instante $i$ $e$ y se toca en el instante $j$ . Supongamos por simetría que $x<y$ y $i<j$ . Es necesario demostrar que existe un tercer punto en el rectángulo con vértices como $(x,i)$ y $(y,j)$ . También deja $\mathrm {LCA} _{t}(a,b)$ denota el ancestro común más bajo de los nodos $a$ y $b$ justo antes del tiempo $t$ . Hay algunos casos:

Si $\mathrm {LCA} _ {i}(x,y)\neq x$ , luego usa el punto $(\mathrm {LCA} _{i}(x,y),i)$ , desde $\mathrm {LCA} _{i}(x,y)$ Debe haber sido tocado si $x$ lo fue.
Si $\mathrm {LCA} _ {j}(x,y)\neq y$ , entonces el punto $(\mathrm {LCA} _ {j}(x,y),j)$ puede utilizarse.
Si ninguno de los dos casos anteriores se cumple, entonces $x$ debe ser un antepasado de $y$ justo antes del tiempo $i,$ e y $debe$ ser un antepasado de $x$ justo antes del tiempo $j$ . Entonces, en algún momento $k$ $(i\leq k<j)$ , $y$ debe haber sido rotado sobre $x$ , por lo que el punto $(y,k)$ puede utilizarse.

A continuación, mostramos la otra dirección: dado un conjunto de puntos satisfecho arbóreamente, se puede construir un BST válido correspondiente a ese conjunto de puntos. Organizamos nuestro BST en un treap que está organizado en orden de montón por next-touch-time. Nótese que next-touch-time tiene empates y, por lo tanto, no está definido de forma única, pero esto no es un problema siempre que haya una forma de romper los empates. Cuando se alcanza el tiempo $i$ , los nodos tocados forman un subárbol conectado en la parte superior, por la propiedad de ordenación de montón. Ahora, asignamos nuevos next-touch-times para este subárbol y lo reorganizamos en un nuevo treap local. Si un par de nodos, $x$ e $y$ , se encuentran a ambos lados del límite entre la parte tocada y la no tocada del treap, entonces si $y$ se toca antes que $x,$ entonces $(x,now)\to (y,next-touch(y))$ es un rectángulo insatisfecho porque el punto más a la izquierda de dicho rectángulo sería el hijo derecho de $x$ , no $de y$ .

Corolario

Encontrar la mejor ejecución de BST para la secuencia de entrada $x_{1},x_{2},...,x_{m}$ 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 que satisface arboralmente un conjunto general de puntos de entrada (no limitado a un punto de entrada por coordenada $y$ ) es NP-completo . ^{[ 1 ]}

Algoritmo voraz

El siguiente algoritmo voraz construye conjuntos arborológicamente satisfacibles:

Recorre el conjunto de puntos con una línea horizontal aumentando la coordenada $y$ .
En el instante $i$ , coloque el número mínimo de puntos en $y=i$ para dejar claro el punto establecido $y\geq i$ Satisfecho arbóreamente. Este conjunto mínimo de puntos está definido de forma única: para cualquier rectángulo insatisfecho formado con $(x_{i},i)$ en una esquina, agregue la otra esquina en $y=i$ .

Se ha conjeturado que el algoritmo es óptimo dentro de un término aditivo. ^{[ 3 ]}

Otros resultados

La geometría de los árboles de búsqueda binaria se ha utilizado para proporcionar un algoritmo que es dinámicamente óptimo si algún algoritmo de árbol de búsqueda binaria es dinámicamente óptimo. ^{[ 4 ]}

Véase también

Referencias

1 2 Demaine, Erik D. ; Harmon, Dion; Iacono, John ; Kane, Daniel ; Pătraşcu, Mihai (2009). "La geometría de los árboles de búsqueda binaria". Actas del vigésimo simposio anual ACM-SIAM sobre algoritmos discretos . Nueva York. págs. 496–505 . doi : 10.1137/1.9781611973068.55 . ISBN 978-0-89871-680-1.{{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
↑ Demaine, Erik D. ; Harmon, Dion; Iacono, John ; Pătraşcu, Mihai (2007). "Optimalidad dinámica—casi" . SIAM Journal on Computing . 37 (1): 240– 251. CiteSeerX 10.1.1.99.4964 . doi : 10.1137/S0097539705447347 . MR 2306291 . S2CID 1480961 .
↑ Fox, Kyle (15-17 de agosto de 2011). Límites superiores para árboles de búsqueda binaria máximamente voraces (PDF) . Algoritmos y estructuras de datos: 12.º Simposio Internacional, WADS 2011. Lecture Notes in Computer Science. Vol. 6844. Nueva York: Springer. pp. 411-422 . arXiv : 1102.4884 . doi : 10.1007/978-3-642-22300-6_35 .
↑ Iacono, John (2013). "En busca de la conjetura de optimalidad dinámica". Estructuras de datos, flujos y algoritmos eficientes en espacio . Lecture Notes in Computer Science. Vol. 8066. pp. 236–250 . arXiv : 1306.0207 . Bibcode : 2013arXiv1306.0207I . doi : 10.1007/978-3-642-40273-9_16 . ISBN 978-3-642-40272-2. S2CID 14729858 .