miniatura|dereita|275px|alt=Exemplo de árbore rubinegra.|Exemplo dunha árbore rubinegra.
En ciencias da computación, unha árbore rubinegra é unha estrutura de datos de árbore binaria de busca auto-equilibrada que destaca polo almacenamento e a recuperación rápidos de información ordenada. Os nós dunha árbore rubinegra levan un bit adicional de «cor», debuxada habitualmente como vermella e negra, que axuda a garantir que a árbore estea sempre aproximadamente equilibrada.
Cando se modifica a árbore, reorganízase e «repíntase» para restaurar as propiedades de coloración que restrinxen o desequilibrio no peor caso. Estas propiedades están deseñadas para que a reorganización e recolocación se poidan facer de forma eficiente.
O (re)equilibrado non é perfecto, pero garante a busca en tempo , onde é o número de elementos. As insercións e os borrados, xunto coa reorganización e a recolocación, tamén se executan en tempo .
Seguir a cor de cada nó só require un bit de información por nó, porque só hai dúas cores. A árbore non contén ningún outro dato específico polo feito de ser rubinegra, de modo que a súa pegada de memoria é case idéntica á dunha árbore binaria de busca clásica. Nalgúns casos, o bit engadido pódese almacenar sen custo adicional de memoria.
Historia En 1972, Rudolf Bayer describiu as «árbores B binarias simétricas», unha clase de árbores binarias para manter conxuntos ordenados con busca, inserción e borrado en tempo logarítmico. A súa construción era unha modificación das árbores B de Bayer e McCreight. Estas representacións binarias deben distinguirse das árbores 2-3-4 coas que se relacionan: nestas últimas, un nó interior pode ter entre dous e catro fillos.
Nun artigo de 1978, «A Dichromatic Framework for Balanced Trees», Leonidas J. Guibas e Robert Sedgewick derivaron a árbore rubinegra a partir da árbores B binaria simétrica. A cor «vermella» elixiuse porque era a que mellor se imprimía na impresora láser en cor de que dispoñían os autores en Xerox PARC.Robert Sedgewick, «Red–Black BSTs», Coursera, 2012. Nunha resposta posterior, Guibas indica que se debeu aos bolígrafos vermellos e negros de que dispuñan para debuxar as árbores.
En 1993, Arne Andersson introduciu a idea dunha árbore inclinada á dereita para simplificar as insercións e os borrados.
En 1999, Chris Okasaki mostrou como facer a inserción puramente funcional. A súa función de equilibrio só necesita tratar catro casos desequilibrados e un caso equilibrado por defecto.
O algoritmo orixinal usaba oito casos desequilibrados, pero Cormen et al. reducíronos a seis. En 2008, Sedgewick propuxo a árbore rubinegra inclinada á esquerda, aproveitando a idea de Andersson para simplificar a inserción e o borrado.
Terminoloxía A profundidade negra dun nó é o número de nós negros desde a raíz ata ese nó (é dicir, o número de antepasados negros). A altura negra dunha árbore rubinegra é o número de nós negros en calquera camiño da raíz ás follas que, polo requisito 4, é constante. A altura negra dun nó é a altura negra da subárbore con raíz nel. Neste artigo, a altura negra dun nó nulo tómase como 0.
Propiedades Ademais dos requisitos dunha árbore binaria de busca, unha árbore rubinegra debe satisfacer:
Todo nó é ou vermello ou negro. Todos os nós nulos considéranse negros. Un nó vermello non ten ningún fillo vermello. Todo camiño desde un nó dado ata calquera das súas follas (é dicir, ata calquera nó nulo descendente) pasa polo mesmo número de nós negros. (Conclusión) Se un nó N ten exactamente un fillo, ese fillo debe ser vermello.
Algúns autores, como Cormen et al., engaden «a raíz é negra» como quinto requisito; pero non Mehlhorn e Sanders nin Sedgewick e Wayne. Como a raíz sempre se pode cambiar de vermella a negra, esta regra ten pouco efecto na análise, e aquí omítese porque perturba lixeiramente os algoritmos recursivos e as demostracións.
As operacións de lectura, como a busca ou o percorrido, non afectan a ningún requisito. Pola contra, as operacións de modificación (inserción e borrado) manteñen doadamente os requisitos 1 e 2, pero para os demais hai que facer un esforzo adicional para evitar introducir unha violación do requisito 3, chamada violación rubia, ou do requisito 4, chamada violación negra.
Os requisitos impoñen unha propiedade crítica: o camiño da raíz á folla máis afastada non é máis do dobre de longo que o camiño da raíz á folla máis próxima. O resultado é que a árbore está equilibrada en altura. Como as operacións requiren un tempo proporcional á altura , este límite superior permite que as árbores rubinegras sexan eficientes no peor caso, é dicir, logarítmicas no número de elementos: . Para unha demostración matemática, véxase a sección de demostración dos límites.
As árbores rubinegras, como todas as árbores binarias de busca, permiten un acceso secuencial eficiente (por exemplo, o percorrido en orde) dos seus elementos, e tamén admiten un acceso directo asintoticamente óptimo mediante un percorrido da raíz á folla, cun tempo de busca .
Analoxía coas árbores 2-3-4 miniatura|alt=Un 2-nó correspóndese cun nó negro; un 3-nó, cun nó negro cun fillo vermello; un 4-nó, cun nó negro con dous fillos vermellos.|Figura 1: Semellanzas entre as árbores 2-3-4 e as árbores rubinegras.
As árbores rubinegras son estruturalmente semellantes ás árbores 2-3-4, que son árbores-B de orde 4. Nas árbores 2-3-4, cada nó pode conter entre 1 e 3 valores e ter entre 2 e 4 fillos. Estes nós 2-3-4 correspóndense con grupos de nó negro con fillos vermellos nas árbores rubinegras, como mostra a figura 1. Non é unha correspondencia un a un, porque os nós 3 teñen dúas representacións equivalentes: o fillo vermello pode estar á esquerda ou á dereita. A variante árbore rubinegra inclinada á esquerda fai que a relación sexa exactamente un a un, permitindo só a representación á esquerda. Como todo nó 2-3-4 ten un nó negro correspondente, a invariante 4 das árbores rubinegras equivale a dicir que as follas dunha árbore 2-3-4 están todas no mesmo nivel.
A pesar das semellanzas estruturais, as operacións nas árbores rubinegras son máis económicas que nas árbores-B, que requiren xestionar vectores de lonxitude variable, mentres que as rubinegras son simplemente árbores binarias.
Aplicacións e estruturas de datos relacionadas As árbores rubinegras ofrecen garantías no peor caso para a inserción, o borrado e a busca. Isto fainas valiosas nas aplicacións sensibles ao tempo, como as de tempo real, e tamén como bloques construtivos doutras estruturas de datos con garantías no peor caso. Por exemplo, moitas estruturas usadas en xeometría computacional baséanse en árbores rubinegras, e o Completely Fair Scheduler e a chamada ao sistema epoll do núcleo Linux usan árbores rubinegras.
A árbore AVL é outra estrutura que admite busca, inserción e borrado en . As árbores AVL pódense colorear como rubinegras, polo que son un subconxunto destas. A altura no peor caso dunha AVL é 0,720 veces a dunha rubinegra, de modo que as AVL están equilibradas de forma máis ríxida. As medicións de Ben Pfaff con casos de proba realistas en 79 execucións dan relacións AVL/RB entre 0,677 e 1,077, cunha mediana de 0,947 e unha media xeométrica de 0,910.Pfaff 2004. O rendemento das árbores WAVL sitúase entre as AVL e as rubinegras.
As árbores rubinegras tamén son valiosas en programación funcional, onde son unha das estruturas de datos persistentes máis comúns, usadas para construír táboas asociativas e conxuntos que conservan versións anteriores tras as modificacións. A versión persistente require de espazo por inserción ou borrado, ademais do tempo.
Para cada árbore 2-3-4, hai árbores rubinegras correspondentes cos mesmos elementos na mesma orde. As insercións e os borrados nas árbores 2-3-4 equivalen ao cambio de cor e ás rotacións nas rubinegras. Isto fai das árbores 2-3-4 unha ferramenta importante para entender a lóxica das rubinegras.
En 2008, Sedgewick introduciu unha versión máis simple chamada árbore rubinegra inclinada á esquerda, que elimina un grao de liberdade antes non especificado. Mantén a invariante adicional de que todas as ligazóns vermellas deben inclinarse á esquerda, agás durante as insercións e os borrados.
A descrición orixinal da árbore tango, un tipo de árbore optimizada para buscas rápidas, usa especificamente árbores rubinegras como parte da súa estrutura de datos.
Desde Java 8, HashMap pode transformar en árbores rubinegras os cubos con moitas colisións, ao superar determinados limiares de ocupación e capacidade. As listas ligadas seguen usándose nos cubos pequenos. As buscas poden beneficiarse dunha cota cando os valores hash ou a comparación entre chaves permiten dirixir o percorrido; para chaves co mesmo hash que non se poden ordenar entre si, pode ser necesario examinar máis ramas.
Implementación As operacións de lectura, como a busca ou o percorrido, non requiren modificación respecto das dunha árbore binaria de busca, porque toda árbore rubinegra é un caso particular dunha árbore binaria de busca simple. Porén, o resultado inmediato dunha inserción ou un borrado pode violar as propiedades, e a súa restauración chámase reequilibrado, de modo que as árbores rubinegras son auto-equilibradas.
O reequilibrado, mediante cambios de cor e rotacións, ten unha complexidade temporal no peor caso de e un custo amortizado de , sen incluír a busca da posición. Esta cota amortizada non é unha media probabilística sobre entradas aleatorias. Ademais, o reequilibrado non require máis de tres rotacións (dúas para a inserción).
A continuación móstrase a función auxiliar rotate_subtree empregada nos exemplos de inserción e borrado en C.
typedef enum Color { BLACK, RED } Color;
typedef enum Direction { LEFT, RIGHT } Direction;
// nó dunha árbore rubinegra typedef struct Node { struct Node* parent; // nulo para o nó raíz union { // Unión para poder usar ->left/->right ou ->child/->child struct { struct Node* left; struct Node* right;
struct Node* child;
Color color; int key; } Node;
typedef struct { struct Node* root; } Tree;
static Direction direction(const Node* N) { return N == N->parent->right ? RIGHT : LEFT; }
Node* rotate_subtree(Tree* tree, Node* sub, Direction dir) { Node* sub_parent = sub->parent; Node* new_root = sub->child[1 - dir]; // 1 - dir é a dirección oposta Node* new_child = new_root->child[dir];
sub->child[1 - dir] = new_child;
if (new_child) { new_child->parent = sub;
new_root->child[dir] = sub;
new_root->parent = sub_parent; sub->parent = new_root; if (sub_parent) { sub_parent->child[sub == sub_parent->right] = new_root; } else { tree->root = new_root;
return new_root; }
Inserción A inserción comeza colocando o novo nó (non nulo), chamado N, na posición dun nó nulo da árbore binaria de busca cuxo predecesor en orde ten unha chave menor que a do novo nó, que á súa vez é menor que a do seu sucesor en orde. O nó inserido colócase temporalmente en vermello, de modo que todos os camiños conteñen o mesmo número de nós negros ca antes. Pero se o seu pai P tamén é vermello, esta acción introduce unha violación rubia.
Os casos de reparación agrúpanse en seis constelacións de nós, arestas e cores. Nos casos 5 e 6, dir indica o lado que ocupa P respecto do seu pai G: esquerda é 0 e dereita é 1, como na función de rotación anterior. Caso 1: o pai P é negro, polo que se cumpren os requisitos 3 e 4; a inserción remata. Caso 2: o pai P e o tío U son vermellos. Recólcanse ambos en negro e o avó G en vermello, para manter o requisito 4; como todo camiño que pasa polo pai ou o tío pasa polo avó, o número de nós negros deses camiños non cambia. Con todo, o avó G pode agora violar o requisito 3 se ten un pai vermello. Tras reetiquetar G como N, o retroceso repítese un nivel negro (dous niveis de árbore) máis arriba.