En la sección 2.2 de Cache-Ajeno B-Trees , Fuertemente Peso equilibrado de la búsqueda árboles se definen como:
Para alguna constante , cada nodo en altura tiene descendientes .
Ellos reclaman:
Los árboles de búsqueda que satisfacen las Propiedades 1 y 2 incluyen árboles B con equilibrio de peso, listas de omisión deterministas y listas de omisión en el sentido esperado.
Otros papeles también afirman que las listas de salto deterministas son fuertemente peso equilibrado, incluyendo concurrente Cache-Ajeno B-Trees y Cache-Ignorancia Streaming árboles B .
No puedo entender por qué las listas de salto deterministas tienen esta propiedad. El documento original sobre listas de omisión deterministas señala que
Como vemos en la Fig. 1, existe una correspondencia uno a uno entre 1-2 listas de omisión y 2-3 árboles.
Me parece, sin embargo, que 2-3 árboles no son fuertemente equilibrada de peso, ya que un nodo a la altura puede tener en cualquier lugar de a descendientes.
fuente
Respuestas:
He estado en contacto con uno de los autores. Confirmó que esto era un error.
Como se indicó anteriormente, esto no afecta, de ninguna manera, ninguno de los resultados del documento.
fuente