Árvores rubro-negras

1567 palavras 7 páginas
ÁRVORES RUBRO-NEGRAS
Uma árvore rubro-negra é uma árvore binária balanceada onde cada nó, além dos atributos normais dos nós de árvores binárias, tem um atributo de cor (vermelho ou preto) e um ponteiro para o nó pai.
Nas árvores rubro-negras os nós folha não são considerados importantes e por isso não contêm dados, sendo identificados apenas por um ponteiro para NULL. Em certas ocasiões todos os nós folha são representados por apenas um único nó sentinela, que é apontado por todas as referências dos nós internos a nós folhas, para economia de memória.
Árvores rubro-negras possuem as seguintes propriedades:
• Todo nó ou é vermelho ou é preto.
• A raiz é preta.
• Todas as folhas (nil) são pretas.
• Todos os filhos de nós vermelhos são pretos, não havendo dois nós vermelhos consecutvos.
• Todo caminho de um nó para alguma de suas folhas descendentes possui o mesmo número de nós pretos.

Essas regras asseguram o balanceamento da árvore tornando a altura dela a menor possível. O maior caminho da raiz a uma folha não é maior que duas vezes o menor caminho para outra folha da árvore. Isso ocorre porque todos os caminhos até as folhas possuem o mesmo número de nós pretos e o menor caminho possui todos os nós pretos e o maior possui nós vermelhos e pretos alternados, uma vez que não é possível haver dois nós vermelhos seguidos.
Desta forma uma árvore rubro-negra, tendo a menor altura possível, possui um tempo de busca O(log n), onde n é o número total de nós da árvore.

INSERÇÃO EM UMA ÁRVORE RUBRO-NEGRA
As operações de inserção ou remoção podem gerar resultados que violem as propriedades de uma árvore rubro-negra. Por isso, depois das operações é necessário que seja realizada uma restauração das propriedades das árvores como modificações de cores de nós e rotações de árvore.
Uma rotação é uma operação realizada na árvore para garantir seu balanceamento. Na rubro-negra pode ser feita a direita e a esquerda, onde são alterados os ponteiros dos nós

Relacionados

  • Arvores Rubro Negras
    1542 palavras | 7 páginas
  • Árvores rubro-negras
    563 palavras | 3 páginas
  • Arvores Rubro Negras
    635 palavras | 3 páginas
  • Arvores Rubro Negra
    441 palavras | 2 páginas
  • Árvores rubro-negras
    765 palavras | 4 páginas
  • Abordagem de arvores rubro-negra
    2304 palavras | 10 páginas
  • Arvores rubro negras
    355 palavras | 2 páginas
  • Árvore rubro negra
    4598 palavras | 19 páginas
  • Arvores Red- Black
    1062 palavras | 5 páginas
  • arvore rubro negra
    796 palavras | 4 páginas