¿Cuándo elegir RB tree, B-Tree o AVL tree?

Creo que los árboles B+ son una buena estructura de datos de contenedores ordenados de propósito general, incluso en la memoria principal. Incluso cuando la memoria virtual no es un problema, la facilidad de 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 facilidad de 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 lo hace inserta / elimina, invalidando punteros a esos elementos. Tengo una biblioteca de contenedores que hace "mantenimiento del cursor": los cursores se adjuntan al nodo de hoja al que hacen referencia actualmente en una lista vinculada, por lo que pueden corregirse o invalidarse automáticamente. Dado que 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 solo eso. Supongo que puedes quitarte o recrear los nodos que no son hojas dependiendo de si los necesita o no, pero con los nodos de árbol binarios obtiene mucha más flexibilidad. Un árbol binario se puede convertir en una lista enlazada y viceversa sin copiar nodos; simplemente cambia los punteros y luego recuerda que ahora lo estás 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 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 deletes puede extraer nodos (separarlos del árbol, pero no liberar la memoria). En un B-tree o B+ - tree, eso obviamente no funciona-los datos vivirán en un nodo multi-item. 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 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 splay, á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 los métodos Treap. La razón por la que elegí los árboles rojo-negro en lugar de AVL es porque personalmente entiendo mejor los algoritmos, 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: solo desarrollé originalmente mis contenedores de árbol 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 su biblioteca existente proporciona, por ejemplo, std::map, etc. en C++. Mi biblioteca evolucionó a lo largo de los años, me llevó bastante tiempo conseguir es estable, y recientemente descubrí que es técnicamente no portátil (depende de un poco de comportamiento indefinido WRT offsetof).

En la memoria B-Tree tiene la ventaja cuando el número de elementos es superior a 32000... Mira 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 hace frente a las operaciones del peor caso, por ejemplo, la inserción de registros que llegan en un orden ordenado
• espacio desperdiciado

Empezaría leyendo los artículos de Wikipedia referenciados por Robert Harvey.

Pragmáticamente, cuando se trabaja en lenguajes como Java, el programador promedio tiende a usar las clases de colección proporcionar. Si en una actividad de ajuste de rendimiento se descubre que el rendimiento de la colección es problemático, entonces se pueden buscar implementaciones alternativas. Rara vez es lo primero que un desarrollo dirigido por negocios tiene que considerar. Es extremadamente raro que uno necesite implementar tales estructuras de datos a mano, generalmente hay bibliotecas que se pueden usar.