Optimalidad independiente de la clave

La optimalidad independiente de la clave es una propiedad de algunas estructuras de datos de árboles de búsqueda binaria en ciencias de la computación propuesta por John Iacono . ^{[ 1 ]} Supongamos que los pares clave-valor se almacenan en una estructura de datos y que las claves no tienen relación con sus pares de valores. Una estructura de datos tiene optimalidad independiente de la clave si, al asignar aleatoriamente las claves, el rendimiento esperado de la estructura de datos está dentro de un factor constante de la estructura de datos óptima. La optimalidad independiente de la clave está relacionada con la optimalidad dinámica .

Existen muchos algoritmos de árbol de búsqueda binaria que pueden buscar una secuencia de${\displaystyle m}$ llaves${\displaystyle X=x_{1},x_{2},\cdots ,x_{m}}$, donde cada${\displaystyle x_{i}}$ es un número entre${\displaystyle 1}$y${\displaystyle n}$. Para cada secuencia${\displaystyle X}$, dejar${\displaystyle {\textit {OPT}}(X)}$ ser el algoritmo de árbol de búsqueda binaria más rápido que busca los elementos en${\displaystyle X}$en orden. Deje${\displaystyle b}$ser uno de los ${\displaystyle n!}$permutación posible de la secuencia${\displaystyle 1,2,\cdots ,n}$, elegido al azar, donde ${\displaystyle b(i)}$es el${\displaystyle i}$entrada de${\displaystyle b}$. Dejar${\displaystyle b(X)=b(x_{1}),b(x_{2}),\cdots ,b(x_{m})}$. Iacono definió, para una secuencia${\displaystyle X}$, eso${\displaystyle {\textit {KIOPT}}(X)=E[{\textit {OPT}}(b(X))]}$.

Una estructura de datos tiene optimalidad independiente de la clave si puede buscar los elementos en${\displaystyle X}$a tiempo ${\displaystyle O({\textit {KIOPT}}(X))}$.

Se ha demostrado que la optimalidad independiente de la clave es asintóticamente equivalente al teorema del conjunto de trabajo . Se sabe que los árboles splay poseen optimalidad independiente de la clave.