Diferença entre árvore B e árvore binária

2019

B-tree e Binary tree são os tipos de estrutura de dados não lineares. Embora os termos pareçam semelhantes, mas são diferentes em todos os aspectos. Uma árvore binária é usada quando os registros ou dados são armazenados na RAM em vez de no disco, já que a velocidade de acesso da RAM é muito maior do que o disco. Por outro lado, o B-tree é usado quando os dados são armazenados no disco, reduzindo o tempo de acesso reduzindo a altura da árvore e aumentando as ramificações no nó.

Outra diferença entre a árvore B e a árvore binária é que a árvore B deve ter todos os seus nós filhos no mesmo nível, enquanto a árvore binária não possui tal restrição. Uma árvore binária pode ter no máximo 2 subárvores ou nós, enquanto que na árvore B pode ter M não de subárvores ou nós, onde M é a ordem da árvore B.

Gráfico de comparação

Base para comparação	B-tree	Árvore binária
Restrição essencial	Um nó pode ter um número M máximo de nós filhos (onde M é a ordem da árvore).	Um nó pode ter no máximo 2 números de subárvores.
Usava	É usado quando os dados são armazenados no disco.	É usado quando os registros e dados são armazenados na RAM.
Altura da árvore	log `_M` N (onde m é a ordem da árvore M-way)	log `₂` N
Aplicação	Estrutura de dados de indexação de código em muitos DBMS.	Otimização de código, codificação Huffman, etc.

Definição de B-tree

Uma árvore B é a árvore M de sentido balanceada e também conhecida como árvore de ordenação balanceada. É semelhante à árvore de pesquisa binária, na qual os nós são organizados com base na passagem interna. A complexidade do espaço da árvore B é O (n). A complexidade do tempo de inserção e exclusão é O (log n).

Existem certas condições que devem ser verdadeiras para uma árvore B:

A altura da árvore deve estar no mínimo possível.
Acima das folhas da árvore, não deve haver subárvores vazias.
As folhas da árvore devem estar no mesmo nível.
Todos os nós devem ter menos filhos, exceto nós de licença.

Propriedades da árvore B da ordem M

Cada nó pode ter um número M máximo de filhos e um número M / 2 mínimo de filhos ou qualquer número entre 2 e o máximo.
Cada nó tem uma chave menor que as crianças com chaves M-1 máximas.
O arranjo das chaves está em alguma ordem específica dentro dos nós. Todas as chaves na subárvore presentes à esquerda da chave são predecessoras da chave, e aquelas presentes à direita da chave são chamadas de sucessoras.
No momento da inserção de um nó completo, a árvore é dividida em duas partes e a chave com valor mediano é inserida no nó pai.
A operação de mesclagem ocorre quando os nós são excluídos.

Definição de árvore binária

Uma árvore binária é uma estrutura de árvore que pode ter no máximo dois ponteiros para seus nós filhos. Isso significa que o grau mais alto que um nó pode ter é 2 e também pode haver um nó de zero ou um grau.

Existem certas variantes de uma árvore binária, como árvore estritamente binária, árvore binária completa, árvore binária estendida, etc.

A árvore estritamente binária é uma árvore na qual cada nó não terminal deve ter subárvore esquerda e subárvore direita.
Uma árvore é chamada de Árvore binária completa quando satisfaz a condição de ter 2 nós em cada nível em que eu é o nível.
O binário encadeado é uma árvore binária que consiste em 0 não de nós ou 2 números de nós.

Técnicas de Traversal

O traversal da árvore é uma das operações mais freqüentes realizadas na estrutura de dados em árvore em que cada nó foi visitado exatamente uma vez de maneira sistemática.

Inorder - Nesta árvore, a subárvore esquerda é visitada recursivamente, em seguida, o nó raiz é visitado e, na última subárvore direita, é visitado.
Preor- Nesta travessia de árvore, o nó raiz é visitado na primeira e depois na esquerda e, finalmente, na subárvore direita.
Postorder - Essa técnica visita a subárvore esquerda, depois a subárvore direita e, finalmente, o nó raiz.

Principais diferenças entre a árvore B e a árvore binária

Na árvore B, o número máximo de nós filhos que um nó não terminal pode ter é M, em que M é a ordem da árvore B. Por outro lado, uma árvore binária pode ter no máximo duas subárvores ou nós filhos.
B-tree é usado quando os dados são armazenados no disco, enquanto a árvore binária é usada quando os dados são armazenados em memória rápida como a RAM.
Outra área de aplicação para B-tree é a estrutura de dados de indexação de código no SGBD, em contraste, a árvore binária é empregada na otimização de código, codificação de huffman, etc.
A altura máxima de uma árvore B é log _M N (M é a ordem da árvore). Em contraste, a altura máxima da árvore binária é log ₂ N (N é o número de nós e base é 2 porque é para binário).

Conclusão

A árvore B é usada em árvore de pesquisa binária e binária, a principal razão por trás disso é a hierarquia de memória onde a CPU está conectada ao cache com os canais de alta largura de banda enquanto a CPU está conectada ao disco através do canal de baixa largura de banda. Uma árvore binária é usada quando os registros são armazenados em RAM (pequena e rápida) e B-tree são usados quando os registros são armazenados em disco (grandes e lentos). Portanto, o uso da árvore B em vez da árvore Binária reduz significativamente o tempo de acesso devido ao alto fator de ramificação e à altura reduzida da árvore.