Hispanopedia WikiEn ciencias de la computación , un árbol doblemente logarítmico es un árbol donde cada nodo interno de altura 1, la capa del árbol por encima de las hojas, tiene dos hijos, y cada nodo interno de alturatienehijos. Cada hijo de la raíz contienehojas. [ 1 ] El número de hijos en un nodo desde cada hoja hasta la raíz es 0,2,2,4,16, 256, 65536, ... (secuencia A001146 en el OEIS )
En el algoritmo Funnelsort de Prokop et al., que ignora la caché, se utiliza un árbol similar llamado k-merger para fusionar elementos. [ 2 ]
Referencias
- ↑ Berkman, Omer; Schieber, Baruch ; Vishkin, Uzi (1993), "Algoritmos paralelos doblemente logarítmicos óptimos basados en la búsqueda de todos los valores más pequeños cercanos", Journal of Algorithms , 14 (3): 344–370 , CiteSeerX 10.1.1.55.5669 , doi : 10.1006/jagm.1993.1018
- ↑ Harald Prokop. Algoritmos que ignoran la caché . Tesis de maestría, MIT. 1999.
Lecturas adicionales
- M. Frigo, CE Leiserson, H. Prokop y S. Ramachandran. Algoritmos que ignoran la caché. En Actas del 40.º Simposio IEEE sobre Fundamentos de la Informática (FOCS 99), págs. 285-297. 1999. Resumen extendido en IEEE , en Citeseer .
- Demaine, Erik . Revisión del algoritmo de ordenación sin tener en cuenta la caché . Notas para el curso 6.897 de Ciencias de la Computación del MIT: Estructuras de datos avanzadas.
Categoría :
- Árboles (estructuras de datos)