¿Cuándo elegir árbol RB, árbol B o árbol AVL?

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 la elección?

¿Alguien puede explicar con un escenario para cada estructura de árbol por qué se elige sobre otras con referencia a los puntos clave?

Toma esto con una pizca de sal:

B-tree cuando administra más de miles de elementos y los pagina desde un disco o algún medio de almacenamiento lento.

RB tree cuando está haciendo inserciones, eliminaciones y recuperaciones bastante frecuentes en el árbol.

AVL cuando sus inserciones y eliminaciones son poco frecuentes en relación con sus recuperaciones.

Creo que los árboles B + son una buena estructura de datos de contenedor ordenada de uso general, incluso en la memoria principal. Incluso cuando la memoria virtual no es un problema, la compatibilidad con la caché a menudo lo es, y los árboles B + son particularmente buenos para el acceso secuencial: el mismo rendimiento asintótico que una lista vinculada, pero con una compatibilidad con la 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 inserta / elimina, invalidando los punteros a esos elementos. Tengo una biblioteca de contenedores que hace "mantenimiento del cursor": los cursores se adjuntan 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 es un poco más de trabajo de todos modos.

Otra cosa es que el árbol B + es esencialmente eso. Supongo que puede quitar o recrear los nodos que no son hojas dependiendo de si los necesita o no, pero con los nodos de árbol binario se obtiene mucha más flexibilidad. Un árbol binario se puede convertir en una lista enlazada y viceversa sin copiar los nodos; simplemente cambie los punteros y luego recuerde que ahora lo está tratando como una estructura de datos diferente. Entre otras cosas, esto significa que obtiene una fusión O (n) de árboles bastante fácil: convierta ambos árboles en listas, combínelos y luego vuelva a convertirlos en un árbol.

Otra cosa más es la asignación y liberación de memoria. 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 +, eso obviamente no funciona: los datos vivirán en un nodo de varios elementos. Escribir métodos de inserción que "planifiquen" la operación sin modificar nodos hasta que sepan cuántos nodos nuevos se necesitan y que se pueden asignar es un desafío.

¿Rojo negro vs. AVL? No estoy seguro de que haya 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 extensión, árboles rojo-negro y treaps, incluidas varias conversiones. Algunos de esos métodos solo se implementaron porque estaba aburrido en un momento u otro. No estoy seguro de haber probado siquiera los métodos de tratamiento. La razón por la que elegí árboles rojo-negros en lugar de AVL es porque personalmente entiendo mejor los algoritmos, lo que no significa que sean más simples, es solo una casualidad de la historia que esté más familiarizado con ellos.

Una última cosa: originalmente desarrollé mis contenedores de árboles B + como un experimento. Es uno de esos experimentos que nunca terminó realmente, pero no es algo que animaría a otros a repetir. Si todo lo que necesita es un contenedor ordenado, la mejor respuesta es usar el que proporciona su biblioteca existente, por ejemplo, std :: map, etc. en C ++. Mi biblioteca evolucionó a lo largo de los años, me tomó bastante tiempo estabilizarla y recientemente descubrí que técnicamente no es portátil (depende de un comportamiento indefinido de WRT offsetof).

En memoria, B-Tree tiene la ventaja cuando el número de elementos es más de 32000 ... Mire speedtest.pdf de stx-btree .

Al elegir estructuras de datos, está intercambiando factores como

• velocidad de recuperación v velocidad de actualización
• qué tan bien la estructura maneja las operaciones del peor de los casos, por ejemplo, la inserción de registros que llegan en un orden clasificado
• espacio desperdiciado

Comenzaría leyendo los artículos de Wikipedia a los que hace referencia Robert Harvey.

De manera pragmática, cuando se trabaja en lenguajes como Java, el programador medio tiende a utilizar las clases de colección proporcionadas. Si en una actividad de ajuste del rendimiento uno descubre que el rendimiento de la colección es problemático, entonces puede buscar implementaciones alternativas. Rara vez es lo primero que debe considerar un desarrollo impulsado por una empresa. Es extremadamente raro que uno necesite implementar tales estructuras de datos a mano, generalmente hay bibliotecas que se pueden usar.