Como programador, ¿cuándo debería considerar usar un árbol RB, árbol B o un árbol AVL? ¿Cuáles son los puntos clave que deben tenerse en cuenta antes de decidir sobre la elección?¿Cuándo elegir el árbol RB, B-Tree o AVL?
¿Puede alguien explicar con un escenario para cada estructura de árbol por qué se elige sobre otros con referencia a los puntos clave?
tomar esto con una pizca de sal:
árbol B cuando administre más de miles de artículos y los estás de búsqueda desde un disco u otro medio de almacenamiento lento.
árbol RB cuando realiza inserciones, elimina y recupera con bastante frecuencia en el árbol.
Árbol AVL cuando las inserciones y eliminaciones son poco frecuentes en relación con las recuperaciones.
Solo para agregar algo más de detalle: B-trees puede tener un número variable de hijos que le permiten mantener muchos registros pero aún así mantener un árbol de altura corta. RB Tree tiene reglas menos estrictas sobre el reequilibrio que hacen que las inserciones/eliminaciones sean más rápidas que el árbol AVL. Por el contrario, el árbol AVL está más estrictamente equilibrado, por lo que las búsquedas son más rápidas que el árbol RB. – pschang
Los árboles RB también tienen un mejor rendimiento O (1) en el reequilibrio, lo que los hace más adecuados para estructuras de datos persistentes con retroceso y avance. –
Al elegir las estructuras de datos que son de comercio de factores tales como
me gustaría empezar por la lectura de los artículos de Wikipedia referenciados por Robert Harvey.
Pragmáticamente, cuando se trabaja en lenguajes como Java, el programador promedio tiende a utilizar 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.
Para ser justos, OP preguntó 'cuándo debería considerar el uso', no' cuándo debería considerar la implementación'. Si bien el último párrafo es verdadero, no proporciona mucho valor en el contexto de esta pregunta. Incluso con las bibliotecas, debe comprender los algoritmos para elegir efectivamente qué estructura se adapta mejor a las necesidades de su negocio. – Dan
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.
B + los árboles tienen problemas, como los elementos que se mueven dentro de los nodos cuando se insertan o eliminan, lo que invalida 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 básicamente 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 proporciona su biblioteca existente, por ej. 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 memoria B-Tree tiene la ventaja cuando el número de elementos es más de 32000 ... Mire speedtest.pdf desde stx-btree.
Bueno, por mi parte agradezco esta pregunta, actualmente presenta una opción de fastutil IntAVLTreeSet vs. IntRBTreeSet. – Yang