Árvore Rubro Negra - Resumo

Prévia do material em texto

Árvores Rubro Negra 
 
Definição: 
 
É uma árvore binária de busca balanceada que tem esse nome devido a coloração 
dos nós. Para ser considerada Rubro Negra a árvore deve satisfazer as seguintes 
propriedades: 
- Todo nó é vermelho ou preto; 
- O nó raiz é preto; 
- Todo nó folha NIL é preto; 
- Se um nó é vermelho, então seus filhos são pretos; 
- Para cada nó, todos os caminhos de um nó até as folhas descendentes possuem o 
mesmo número de nós pretos. 
 
Estrutura 
 
Se um nó sem filho não aponta pra NIL, e sim para o nó SENTINELA, que será a 
folha de todos os nós da árvore até que estes recebam filhos. O nó sentinela é utilizado 
para economizar de espaço. 
 
Cada nó tem os seguintes campos: 
- 1 bit pra cor (vermlho ou preto) 
- key (valor da chave) 
- ponteiros left e right (apontando para subárvore) 
- ponteiro pai (apontando para o nó pai) 
 
 O campo pai do nó raiz aponta para NIL. 
 
Ao inserir nós na árvore deve-se garantir que nenhuma propriedade seja violada, 
portanto pode ser que as cores dos nós sejam alteradas, e a estrutura da árvore seja 
modificada através das rotações esquerda ou direita. 
 
Exemplo de AR,, onde os nós vermelhos são representados pela cor branca: 
 
 
 
 
Referência (conteúdo e imagem): T. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. 
Algoritmos: Teoria e Prática, 2 ed, Rio de Janeiro: Elsevier, 2002