El algoritmo Day-Stout-Warren (DSW) es un método para equilibrar eficientemente los árboles de búsqueda binarios , es decir, disminuir su altura a O (log n ) nodos, donde n es el número total de nodos. A diferencia de un árbol de búsqueda binario autoequilibrado , no lo hace de forma incremental durante cada operación, sino periódicamente, de modo que su costo se pueda amortizar en muchas operaciones. El algoritmo fue diseñado por Quentin F. Stout y Bette Warren en un artículo del CACM de 1986 , [1] basado en el trabajo realizado por Colin Day en 1976. [2]
El algoritmo requiere tiempo lineal (O ( n )) y está en su lugar . El algoritmo original de Day genera un árbol lo más compacto posible: todos los niveles del árbol están completamente llenos excepto posiblemente el más bajo. Opera en dos fases. Primero, el árbol se convierte en una lista vinculada por medio de un recorrido en orden , reutilizando los punteros en los nodos del árbol ( enhebrado ). Una serie de rotaciones a la izquierda forma la segunda fase. [3]La modificación Stout-Warren genera un árbol binario completo, es decir, uno en el que el nivel más bajo se llena estrictamente de izquierda a derecha. Esta es una transformación útil de realizar si se sabe que no se realizarán más inserciones. No requiere que el árbol esté enhebrado, ni requiere más que un espacio constante para operar. [1] Al igual que el algoritmo original, Day-Stout-Warren opera en dos fases, la primera completamente nueva, la segunda una modificación de la fase de rotación de Day. [1] [3]
Un artículo de 2002 de Timothy J. Rolfe llamó la atención sobre el algoritmo DSW; [3] el nombre es del título de la sección "6.7.1: El algoritmo DSW" en el libro de texto de Adam Drozdek. [4] Rolfe cita dos ventajas principales: "en circunstancias en las que se genera un árbol de búsqueda binario completo al comienzo del procesamiento, seguido de acceso de búsqueda de elementos para el resto del procesamiento" y "pedagógicamente dentro de un curso sobre estructuras de datos donde uno progresa desde el árbol de búsqueda binaria a árboles autoajustables, ya que da una primera exposición para hacer rotaciones dentro de un árbol de búsqueda binaria ".
Pseudocódigo
La siguiente es una presentación del algoritmo DSW básico en pseudocódigo , según el artículo de Stout-Warren. [1] [nota 1] Consiste en una rutina principal con tres subrutinas . La rutina principal viene dada por
- Asigne un nodo, la "pseudo-raíz", y haga que la raíz real del árbol sea el hijo correcto de la pseudo-raíz.
- Llame a tree-to-vine con la pseudo-raíz como argumento.
- Llame a vine-to-tree en la pseudo-raíz y el tamaño (número de elementos) del árbol.
- Haga que la raíz real del árbol sea igual al hijo derecho de la pseudorraíz.
- Elimina la pseudo-raíz.
Las subrutinas se definen de la siguiente manera: [nota 2]
rutina árbol-a-vid (raíz) // Convertir el árbol en una "vid", es decir, una lista enlazada ordenada, // usando los punteros correctos para apuntar al siguiente nodo de la lista cola ← raíz resto ← cola derecha while rest ≠ nil si rest.left = nil cola ← resto descansar ← descansar derecha demás temp ← resto izquierda rest.izquierda ← temp.derecha temp. derecha ← descanso resto ← temp tail.right ← temp
rutina de vid a árbol (raíz, tamaño) hojas ← tamaño + 1-2 ⌊log 2 (tamaño + 1)) ⌋ comprimir (raíz, hojas) tamaño ← tamaño - hojas mientras que el tamaño> 1 comprimir (raíz, ⌊ tamaño / 2⌋) tamaño ← ⌊ tamaño / 2⌋
Compresión de rutina (raíz, recuento) escáner ← raíz para i ← 1 a recuento niño ← escáner derecho scanner.right ← child.right escáner ← escáner derecho child.right ← scanner.left scanner.left ← niño
Notas
- ^ Esta versión no produce nodos perfectamente equilibrados; Stout y Warren presentan una modificación que sí, en la que la primera llamada a comprimir es reemplazada por una subrutina diferente.
- ^ En la presentación original, tree-to-vine calculó el tamaño del árbol a medida que avanzaba. En aras de la brevedad, asumimos que este número se conoce de antemano.
Referencias
- ^ a b c d Stout, Quentin F .; Warren, Bette L. (septiembre de 1986). "Reequilibrio de árboles en un espacio y tiempo óptimos" (PDF) . Comunicaciones de la ACM . 29 (9): 902–908. doi : 10.1145 / 6592.6599 . hdl : 2027.42 / 7801 .
- ^ Día, A. Colin (1976). "Equilibrio de un árbol binario" . Computación. J. 19 (4): 360–361. doi : 10.1093 / comjnl / 19.4.360 .
- ^ a b c Rolfe, Timothy J. (diciembre de 2002). "Equilibrio de árbol de búsqueda binaria de una sola vez: el algoritmo de Day / Stout / Warren (DSW)" . Boletín SIGCSE . ACM SIGCSE. 34 (4): 85–88. doi : 10.1145 / 820127.820173 . Archivado desde el original el 13 de diciembre de 2012.
- ^ Drozdek, Adam (1996). Estructuras de datos y algoritmos en C ++ . PWS Publishing Co. págs. 173-175. ISBN 0-534-94974-6.