Diferença entre árvore B e árvore binária
Contente
- Gráfico de comparação
- Definição de árvore B
- Propriedades da árvore B da ordem M
- Definição de árvore binária
- Técnicas transversais
- Conclusão
Árvore B e Árvore Binária são os tipos de estrutura de dados não lineares. Embora os termos pareçam ser semelhantes, são diferentes em todos os aspectos. Uma árvore binária é usada quando os registros ou dados são armazenados na RAM em vez do disco, pois a velocidade de acesso à RAM é muito maior que o disco. Por outro lado, a árvore B é usada quando os dados são armazenados no disco e reduz 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 essa restrição. Uma árvore binária pode ter no máximo 2 subárvores ou nós, enquanto na árvore B pode haver M não de subárvores ou nós onde M é a ordem da B-árvore.
- Gráfico de comparação
- Definição
- Principais diferenças
- Conclusão
Gráfico de comparação
| Base para comparação | Árvore B | Árvore binária |
|---|---|---|
| Restrição essencial | Um nó pode ter no máximo M número 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 registros e dados são armazenados na RAM. |
| Altura da árvore | registroM N (onde m é a ordem da árvore M-way) | registro2 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 árvore B
Uma árvore B é a árvore M-way balanceada e também conhecida como árvore de classificação balanceada. É semelhante à árvore de pesquisa binária, na qual os nós são organizados com base no percurso da ordem. A complexidade espacial 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 vir no mesmo nível.
- Todos os nós devem ter menos número de filhos, exceto nós de saída.
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 de 2 ao máximo.
- Cada nó possui uma chave a menos que os filhos com o máximo de chaves M-1.
- A organização das chaves está em alguma ordem específica dentro dos nós. Todas as chaves na subárvore presente à esquerda da chave são predecessoras da chave e as presentes à direita da chave são chamadas 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ó 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 em que 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 Eu nós em cada nível em que i é o nível.
- O binário encadeado é uma árvore binária que consiste em 0 não de nós ou 2 número de nós.
Técnicas transversais
A travessia de árvore é uma das operações mais frequentes executadas na estrutura de dados da árvore em que cada nó visitou exatamente uma vez de maneira sistemática.
- Inorder- Nesta travessia em árvore, a subárvore esquerda é visitada recursivamente, em seguida, o nó raiz é visitado e na última subárvore direita é visitada.
- Pré-ordenação - Nesta árvore, o nó raiz é visitado na primeira subárvore esquerda e, finalmente, na subárvore direita.
- Pós-ordem - Essa técnica visita a subárvore esquerda, a direita e, finalmente, o nó raiz.
- Na árvore B, o número máximo de nós filhos que um nó não terminal pode ter é M, onde 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.
- A árvore B é usada quando os dados são armazenados no disco, enquanto a árvore binária é usada quando os dados são armazenados na memória rápida, como a RAM.
- Outra área de aplicação da árvore B é a estrutura de dados de indexação de código no DBMS, ao contrário, a árvore binária é empregada na otimização de código, na codificação de huffman etc.
- A altura máxima de uma árvore B é logMN (M é a ordem das árvores). Em contrapartida, a altura máxima da árvore binária é log2N (N é o número de nós e a base é 2 porque é para binário).
Conclusão
A árvore B é usada na árvore de pesquisa binária e binária. A principal razão por trás disso é a hierarquia de memória na qual 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 na RAM (pequena e rápida) e a árvore B é usada quando os registros são armazenados no disco (grande e lento). 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.
