data-structures - avl - red black tree java
¿Cuándo elegir el árbol RB, B-Tree o AVL? (4)
Como programador, ¿cuándo debería considerar usar un árbol RB, un árbol B o un árbol AVL? ¿Cuáles son los puntos clave que deben tenerse en cuenta antes de decidir sobre la elección?
¿Puede alguien explicar con un escenario para cada estructura de árbol por qué se elige sobre otros con referencia a los puntos clave?
Al elegir estructuras de datos, usted está intercambiando factores tales como
- velocidad de recuperación v velocidad de actualización
- qué tan bien la estructura hace frente a las peores operaciones del caso, por ejemplo, la inserción de registros que llegan en un orden ordenado
- espacio perdido
Comenzaría leyendo los artículos de Wikipedia a los que hace referencia Robert Harvey.
Pragmáticamente, cuando se trabaja en lenguajes como Java, el programador promedio tiende a usar las clases de colección proporcionadas. Si en una actividad de ajuste de rendimiento uno descubre que el rendimiento de la colección es problemático, entonces uno puede buscar implementaciones alternativas. Rara vez es lo primero que debe considerar un desarrollo empresarial. Es extremadamente raro que uno necesite implementar tales estructuras de datos a mano, generalmente hay bibliotecas que se pueden usar.
Creo que los árboles B + son una buena estructura de datos de contenedores ordenados de uso general, incluso en la memoria principal. Incluso cuando la memoria virtual no es un problema, a menudo es amigable con la caché, y los árboles B + son particularmente buenos para el acceso secuencial: el mismo rendimiento asintótico que una lista vinculada, pero con facilidad de memoria caché cercana a una matriz simple. Todo esto y O (log n) buscar, insertar y eliminar.
Sin embargo, los árboles B + tienen problemas, como los elementos que se mueven dentro de los nodos cuando se insertan / eliminan, invalidando los punteros a esos elementos. Tengo una biblioteca de contenedores que hace "mantenimiento del cursor": los cursores se conectan al nodo hoja al que hacen referencia actualmente en una lista vinculada, por lo que pueden corregirse o invalidarse automáticamente. Como rara vez hay más de uno o dos cursores, funciona bien, pero de todos modos es un poco más de trabajo.
Otra cosa es que el árbol B + es esencialmente solo eso. Supongo que puedes quitarte o recrear los nodos de hojas dependiendo de si los necesitas o no, pero con los nodos de árboles binarios obtienes mucha más flexibilidad. Un árbol binario se puede convertir a una lista vinculada y volver sin copiar nodos; solo debe cambiar los punteros y luego recordar que ahora lo está tratando como una estructura de datos diferente. Entre otras cosas, esto significa que te resultará bastante fácil O (n) fusión de árboles: convierte ambos árboles en listas, combínalos y luego conviértelos de nuevo en un árbol.
Otra cosa más es la asignación de memoria y la liberación. En un árbol binario, esto se puede separar de los algoritmos: el usuario puede crear un nodo y luego llamar al algoritmo de inserción, y las eliminaciones pueden extraer nodos (separarlos del árbol, pero no liberar la memoria). En un árbol B o árbol B +, obviamente eso no funciona, los datos vivirán en un nodo de múltiples elementos. Escribir métodos de inserción que "planifiquen" la operación sin modificar los nodos hasta que sepan cuántos nuevos nodos se necesitan y que se pueden asignar es un desafío.
Rojo negro vs. AVL? No estoy seguro de que haga una gran diferencia. Mi propia biblioteca tiene una clase de "herramienta" basada en políticas para manipular nodos, con métodos para listas de doble enlace, árboles binarios simples, árboles de dispersión, árboles rojo-negro y tramposos, incluidas varias conversiones. Algunos de esos métodos solo se implementaron porque en algún momento me aburrí. No estoy seguro de haber probado los métodos de prueba. La razón por la que elegí árboles rojo-negro en lugar de AVL es porque personalmente entiendo mejor los algoritmos, lo que no significa que sean más simples, es solo un golpe de suerte que estoy más familiarizado con ellos.
Una última cosa: originalmente desarrollé mis contenedores de árbol B + como un experimento. Es uno de esos experimentos que nunca terminaron realmente, pero no es algo que anime a otros a repetir. Si todo lo que necesita es un contenedor ordenado, la mejor respuesta es usar el que su biblioteca existente proporciona, por ejemplo, std :: map, etc. en C ++. Mi biblioteca evolucionó a lo largo de los años, llevó bastante tiempo estabilizarla, y recientemente descubrí que no es técnicamente portátil (depende de un comportamiento indefinido WRT offsetof).
En la memoria B-Tree tiene la ventaja cuando la cantidad de elementos es más de 32000 ... Mire speedtest.pdf desde stx-btree .
Toma esto con una pizca de sal:
B-tree cuando está administrando más de miles de elementos y los está paginando desde un disco o algún medio de almacenamiento lento.
Árbol RB cuando realiza inserciones, eliminaciones y recuperaciones bastante frecuentes en el árbol.
Árbol AVL cuando sus inserciones y eliminaciones son poco frecuentes en relación con sus recuperaciones.