Cuando elegir árbol RB, B-árbol o un árbol AVL?

Question

Como programador cuando se debería considerar el uso de un árbol RB, árbol B o un árbol AVL? ¿Cuáles son los puntos clave que debe tenerse en cuenta antes de decidir sobre la elección?

Por favor alguien puede explicar con un escenario para cada estructura de árbol por la que se elige por encima de otros con referencia a los puntos clave?

Answer 1

tomar esto con una pizca de sal:

árbol B cuando administre más de miles de artículos y ya está a la paginación de un disco u otro medio de almacenamiento lento.

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

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

Answer 2

creo B + árboles son un buen propósito general ordenó estructura de datos de contenedores, incluso en la memoria principal. Incluso cuando la memoria virtual no es un problema, caché de uso a menudo, y B + árboles son particularmente buenos para el acceso secuencial - el mismo rendimiento asintótica como una lista enlazada, pero con caché de uso cerca de una simple matriz. Todo esto y O (log n) buscar, insertar y eliminar.

B + árboles tiene problemas, sin embargo - como los artículos moverse dentro de los nodos cuando se hace inserciones / eliminaciones, invalidando punteros a esos artículos. Tengo una biblioteca de contenedor que hace de "mantenimiento del cursor" - cursores adhieren al nodo hoja que actualmente referencia en una lista enlazada, por lo que pueden ser fijas o automáticamente invalidados. 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 sólo eso. Creo que se puede deshacer o volver a crear los nodos que no son hojas en función de si los necesita o no, pero con los nodos del árbol binario que da mucha más flexibilidad. Un árbol binario se puede convertir en una lista enlazada y la espalda sin copiar nodos - que acaba de cambiar los punteros a continuación, recuerde que usted está tratando como una estructura de datos diferente ahora. Entre otras cosas, esto significa que se obtienen O bastante fácil (n) la fusión de los árboles -. Convertir los dos árboles de listas, que se fusionan, a continuación, convertir de nuevo a un árbol

Sin embargo, otra cosa es la asignación de memoria y liberación. En un árbol binario, este puede ser separado hacia fuera de los algoritmos - el usuario puede crear un nodo a continuación, llamar el algoritmo de inserción, y eliminaciones puede extraer nodos (desprenderlas del árbol, pero no te libera la memoria). En un árbol B o árbol B +, que, obviamente, no funciona - los datos van a vivir en un nodo de varios artículos. Inserto de escritura de métodos que el "plan" de la operación sin necesidad de modificar los nodos hasta que sepan cuántos se necesitan nuevos nodos y que pueden ser asignados es un reto.

Red AVL vs negro? No estoy seguro de que haga alguna diferencia grande. Mi propia biblioteca tiene una clase basada en políticas "herramienta" para manipular nodos, con los métodos para las listas de doble ligado, árboles binarios simples, árbol biselado, árboles rojo-negro y treaps, incluyendo varias conversiones. Algunos de estos métodos sólo se ejecutaron porque se aburre en un momento u otro. No estoy seguro de que he probado, incluso los métodos Treap. La razón por la que eligió árboles rojo-negro en lugar de AVL es porque yo personalmente entiendo los algoritmos mejor -. Lo cual no significa que sean más simple, es sólo una casualidad de la historia que estoy más familiarizado con ellos

Una última cosa - yo sólo desarrolló originalmente mis contenedores B + árboles como un experimento. Es uno de esos experimentos que nunca terminó de verdad, pero no es algo que me gustaría animar a otros a repetir. Si todo lo que necesita es un recipiente ordenada, la mejor respuesta es utilizar la que su biblioteca existente proporciona - por ejemplo, std :: map etc en C ++. Mi biblioteca evolucionado durante años, se tomó un buen tiempo para conseguirlo estable, y sólo hace relativamente poco tiempo descubrió que técnicamente no portátil (dependiente de un poco de indefinido WRT comportamiento offsetof).

Answer 3

En la memoria de árbol B tiene la ventaja, cuando el número de elementos es más de 32000 ... Mira speedtest.pdf de href="https://github.com/bingmann/stx-btree" rel="nofollow"> STX-árbolB .

Answer 4

Al elegir las estructuras de datos que son de comercio de factores tales como

• velocidad de recuperación de la velocidad v de la actualización
• qué tan bien las capas pluviales estructura con las operaciones de los casos, por ejemplo, la inserción de los registros que llegan en un orden clasificado
• espacio perdido

Yo empezaría por la lectura de los artículos de Wikipedia referenciados por Robert Harvey.

De manera pragmática, cuando se trabaja en lenguajes como Java el programador medio tiende a utilizar las clases de recogida previstos. Si en una actividad de ajuste del rendimiento se descubre que el rendimiento de recogida es problemático entonces uno puede buscar implementaciones alternativas. Es muy raro que la primera cosa que un desarrollo impulsado por las empresas tiene que tener en cuenta. Es extremadamente raro que uno necesita para poner en práctica este tipo de estructuras de datos a mano, por lo general hay bibliotecas que se pueden utilizar.