stringtranslate.com

Ordenar árbol estadístico

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.

Implementación de árbol de búsqueda aumentada

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]

Referencias

  1. ^ "Árboles B contados". 11 de diciembre de 2004. Consultado el 18 de enero de 2014 .
  2. ^ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. Introducción a los algoritmos (2.ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03293-7.
  3. ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03384-4.
  4. ^ Roura, Salvador (2001). Un nuevo método para equilibrar árboles binarios de búsqueda . ICALP . Lecture Notes in Computer Science. Vol. 2076. págs. 469–480. doi :10.1007/3-540-48224-5_39. ISBN. 978-3-540-42287-7.

Véase también

Enlaces externos