Arvores Rubro Negras

1552 palavras 7 páginas
LISTA DE FIGURAS 4
RESUMO 5
1 INTRODUÇÃO 6
2 ÁRVORES RUBRO-NEGRA 7
2.1 PROPRIEDADES 7
2.2 INSERÇÃO 8
2.2.1 Caso 1 8
2.2.2 Caso 2 8
2.2.3 Caso 3 9 2.2.3.1 Caso 1 9 2.2.3.2 Caso 2 10 2.2.3.3 Caso 3 10
2.2.4 Caso 4 10
2.3 REMOÇÃO 11
2.3.1 Remoção efetiva 11
2.3.2 Remoção preguiçosa 11
CONCLUSÃO 12
REFERÊNCIAS 13

LISTA DE FIGURAS
Figura 1 – “Exemplo de Árvore Rubro-Negra” 7
Figura 2 – “Inserção em árvore vazia” 8
Figura 3 – “Pai negro” 8
Figura 4 – “Pai rubro” 9
Figura 5 – “Ambos rubros” 9
Figura 6 – “Pai rubro, tio negro e filho esquerdo” 10
Figura 7 – “Pai rubro, tio negro e filho direito” 10
Figura 8 – “Raiz da árvore final” 11

RESUMO
A Árvore rubro-negra é um tipo especial de árvore de busca binária, que se mantém balanceadas no decorrer de suas operações, existindo algoritmos de inserção e remoção de complexidade logarítmica, relativo ao número de nós.
Esta estrutura de dados, utilizada em ciência da computação, que teve seu inicio em 1972, inventada por um professor emérito de informática, Rudolf Bayer, são muito utilizadas, por ter sua prática muito eficiente e também pelo diferencial de ter um bit extra, que armazena a cor de cada nodo presente na estrutura (vermelho ou preto, rubro ou negra). Além disso, cada nodo é composto ainda pelo seu valor (dados do nó), fe (filho esquerdo, outro nó), fd (filho direito, outro nó) e pai (outro nó).

Palavras-chave: Árvore rubro-negra; Estrutura de dados; Ciência da

Relacionados

  • Árvores avl e sbb
    1470 palavras | 6 páginas
  • Exercícios introdução à Óptica
    1286 palavras | 6 páginas
  • Poemas de cesario verde
    15793 palavras | 64 páginas
  • moda
    3401 palavras | 14 páginas
  • Portfólio Pizzaria
    3168 palavras | 13 páginas
  • PROJETO FERNANDO
    3635 palavras | 15 páginas
  • Fichamento "o cortiço"
    7046 palavras | 29 páginas
  • Feijões ou problemas?
    6034 palavras | 25 páginas