En informática , un árbol estadístico de orden es una variante del árbol de búsqueda binaria (o más generalmente, un árbol B [1] ) que admite dos operaciones adicionales más allá de la inserción, la búsqueda y la eliminación:
Ambas operaciones se pueden realizar en el peor de los casos, O (log n ), cuando se utiliza un árbol autoequilibrado como estructura de datos base.
Para convertir un árbol de búsqueda normal en un árbol de estadísticas de orden, los nodos del árbol deben almacenar un valor adicional, que es el tamaño del subárbol con raíz en ese nodo (es decir, la cantidad de nodos debajo de él). Todas las operaciones que modifican el árbol deben ajustar esta información para preservar la invariante que
tamaño[x] = tamaño[izquierda[x]] + tamaño[derecha[x]] + 1
donde size[nil] = 0por definición, Select se puede implementar como [2] : 342
función Seleccionar(t, i) // Devuelve el elemento i-ésimo (indexado uno) de los elementos en t p ← tamaño[izquierda[t]]+1 si i = p volver t de lo contrario, si i < p, devuelve Select(izquierda[t], i) de lo contrario, devuelve Select(derecha[t], i - p)
El rango se puede implementar, utilizando la función padre p[x], como [3] : 342
Función Rango(T, x) // Devuelve la posición de x (indexada en uno) en la lista ordenada linealmente de elementos del árbol T r ← tamaño[izquierda[x]] + 1 y ← x mientras y ≠ T.root si y = right[p[y]] r ← r + tamaño[izquierda[p[y]]] + 1 y ← p[y] volver r
Los árboles de estadísticas de orden se pueden modificar aún más con información de contabilidad para mantener el equilibrio (por ejemplo, se puede agregar la altura del árbol para obtener un árbol de estadísticas de orden AVL , o un bit de color para obtener un árbol de estadísticas de orden rojo-negro ). Alternativamente, el campo de tamaño se puede utilizar junto con un esquema de equilibrio de peso sin costo de almacenamiento adicional. [4]