Árbol de búsqueda binaria para la intención específica

Question

Todos sabemos que hay un montón de árboles de búsqueda binaria de autoequilibrado (BST), siendo el más famoso el Rojo-Negro y el AVL. También podría ser útil echar un vistazo a árboles AA y árboles de chivo expiatorio.

Quiero hacer inserciones, inserciones y búsquedas, como cualquier otra BST. Sin embargo, será común eliminar todos los valores en un rango determinado o eliminar subárboles enteros. Entonces:

1. Quiero insertar, buscar, eliminar valores en O (log n) (árbol balanceado).
2. me gustaría borrar un sub-árbol, manteniendo todo el árbol equilibrado, en O (log n) (en el peor de los casos o amortizado)
3. Podría ser útil para eliminar varios valores de una fila, antes de equilibrar el árbol
4. voy a lo más a menudo inserto 2 valores a la vez, sin embargo, esto no es una regla (sólo un consejo en caso de que haya una estructura de datos de árbol que tiene esto en cuenta)

¿existe una variante de la AVL o RB eso me ayuda en esto? Los árboles de chivo expiatorio se parecen más a esto, pero también necesitarían algunos cambios, cualquiera que tenga experiencia en ellos puede compartir algunos aspectos.

Más precisamente, ¿qué procedimiento de balanceo y/o procedimiento de eliminación me ayudaría a mantener estas acciones de tiempo eficiente?

Answer 1

Es posible eliminar un rango de valores a BST en O (logn + objects num).

La manera más fácil que conozco es trabajando con la estructura de datos Deterministic Skip List (es posible que desee leer un poco sobre esta estructura de datos antes de continuar). En la lista de omisiones determinista, todos los valores reales se almacenan en el nivel inferior, y hay punteros en los niveles superiores para ellos. Insertar, buscar y eliminar se hacen en O (logn).

La operación gama eliminación se puede hacer de acuerdo con el siguiente algoritmo:

• encontrar el primer elemento en el rango de - O (log n)
• avanzar en la lista enlazada, y eliminar todos los elementos que todavía están en el rango. Si hay elementos con punteros a los niveles superiores, elimínelos también, hasta alcanzar el nivel superior (eliminación de una lista vinculada) - O (número de objetos eliminados)
• Fije los punteros para que se ajusten a la lista de omisiones determinista (2-3 elementos entre cada puntero hacia arriba)

La complejidad total de la eliminación de rango es O (logn + número de objetos en el rango). Tenga en cuenta que si elige trabajar con una lista de omisiones al azar, obtendrá la misma complejidad, pero en promedio, y no en el peor de los casos. La ventaja es que no tiene que arreglar los indicadores de nivel superior para cumplir con la demanda 2-3.

Una lista de omisiones determinista tiene una asignación de 1-1 a un árbol 2-3, por lo que con un poco más de trabajo, el procedimiento descrito anteriormente también podría funcionar para un árbol 2-3.

Answer 2

Hmm, ¿qué hay de B-trees? También son equilibrados, y si eliges uno grande -depende de cuántos artículos tengas-, ahorrarás muchos tiempos de creación/destrucción de objetos.

Para 2. Si tiene un B-tree de orden 100, puede eliminar hasta 100 elementos con una llamada a función.

a 3. Esta función se puede aplicar a casi todos los árboles, simplemente implemente una función RemoveSome() que elimina N elementos y realiza un reequilibrio. Para B-trees, es un poco más complicado, pero se puede hacer.

Nota: Supongo que eres un programador. Si necesita una solución completa, probada y lista para usar, necesita otra respuesta.

Answer 3

Hace mucho tiempo en los días previos a STL escribí mi propio algoritmo B-Tree (BST) porque tenía un conjunto de datos bastante grande en ese momento (aproximadamente 700 K elementos en 2 árboles que eran interdependientes). Descubrí que el reequilibrio después de cada 100-200 inserciones/eliminaciones era el máximo rendimiento que podía obtener en ese momento, basado en la experimentación con hardware 486 y SGI. Este número puede ser diferente ahora, o tal vez no, ya que parece ser un límite de optimización algorítmica a menos que se convierta a un modelo paralelo.

En resumen, puede aplicar un disparador de modificación para el reequilibrio y permitir el reequilibrio forzado cuando haya completado todas sus modificaciones.

La mejora fue notable. La carga lineal inicial no se completó después de 25 m (eliminó el proceso). Reequilibrar como fuimos también fue asesinado después de 15 m. La modificación restringida se carga con un reequilibrio cada 100 mods cargados y se ejecuta en menos de 3 m. Tenga en cuenta que durante la parte "ejecutar", hubo una modificación de 0-8 en el árbol por entrada inicial. Realmente necesita considerar si siempre necesita estar en equilibrio cuando el árbol se modificará nuevamente en el corto plazo.

Answer 4

Debería ser fácil implementar la eliminación de un nodo y sus subnodos en un árbol AVL si cada nodo almacena su altura en lugar de un factor de equilibrio. Después de eliminar un nodo, siga girando hasta que los dos nodos secundarios difieran en no más de uno. Luego sube al árbol y repite. La única diferencia real de una eliminación normal será while en lugar de if para probar las alturas.

Answer 5

La implementación Set en la biblioteca estándar OCaml es un árbol AVL puramente funcional que satisface todos sus requisitos y, en particular, tiene implementaciones muy eficientes de operaciones teóricas (unión, intersección, diferencia). La inserción y eliminación son O (log n). Puede eliminar subárboles y ejecuciones de elementos representándolos como un conjunto y utilizando la diferencia establecida. Puede insertar dos elementos simultáneamente creando un conjunto de 2 elementos y aplicando conjunto de unión.