Arvore RN

Árvores:
Árvore B+ e Árvore Rubro-negra
Luiz Takeshi Murakami Ynoue¹, Marcela Mayumi Hitaka Nishida¹
¹ Graduando em Ciência da Computação, Faculdade Ciência e Tecnologia FCT-UNESP
Presidente Prudente – SP – Brasil [e-mail], [e-mail]

Resumo. Este artigo apresenta Árvore B+ e Árvore rubro-negra. Árvore rubro-negra é uma árvore binária de busca, com determinadas propriedades adicionais e um bit extra por nó. Árvore B+ é semelhante à árvore B, diferindo-se apenas que há um campo a mais na estrutura, tal campo é um ponteiro para auto-referencia do próximo, que estabelece o encadeamento nos nós folhas.

1. Introdução
No ramo da ciência da computação, as árvores são estrutura de dados, utilizadas para armazenar informações, onde seus dados estão dispostos de forma hierárquica, constituída por um elemento principal chamado raiz, que possui ligações com outros elementos, mais conhecidos como filhos ou nós. Essas estruturas oferecem uma eficiência na inserção, remoção e busca dos dados.
Há diversos tipos de árvores: árvore binária de busca, árvore AVL, árvore B.
Dentre elas, árvore rubro-negra e árvore B+, que serão analisadas.
Árvore rubro-negra, árvore vermelho e preto ou do inglês Red-Black Tree, é um tipo de árvore de busca binária balanceada, uma estrutura de dados. A estrutura original dessa árvore, foi chamada de "Árvores Binárias B Simétricas", inventada em 1972, dez anos depois da árvore AVL, por Rudolf Bayer, posteriomente esta árvore foi estudada profundamente, por Leonidas J. Guibas e Robert Sedgewick, que introduziram a converção de cores: vermelho ou preto, rubro ou negra. Sendo realmente conhecido esta estrutura com o nome atual em 1978, na publicação de artigo escrito por Guibas e
Sedgewick.
O nome árvore rubro-negra se deve a coloração de cada nó, cada nó é rubro ou negra, ou também o nó é vermelho ou preto, daí árvore vermelho preto.
Esta árvore pussui um balanceamento, que consiste no número de