Árvore Binária Completa vs Árvore Binária Completa
Árvore binária é uma árvore onde cada nó tem um ou dois filhos. Em uma árvore binária, um nó não pode ter mais de dois filhos. Em uma árvore binária, os filhos são nomeados como filhos “esquerdo” e “direito”. Os nós filho contêm uma referência ao pai. Uma árvore binária completa é uma árvore binária na qual todos os níveis da árvore binária são completamente preenchidos, exceto o último nível. No nível não preenchido, os nós são anexados a partir da posição mais à esquerda. Uma árvore binária completa é uma árvore na qual cada nó na árvore tem dois filhos, exceto as folhas da árvore.
O que é Árvore Binária Completa?
Árvore binária completa é uma árvore binária na qual cada nó na árvore tem exatamente zero ou dois filhos. Em outras palavras, cada nó na árvore, exceto as folhas, tem exatamente dois filhos. A Figura 1 abaixo mostra uma árvore binária completa. Em uma árvore binária completa, o número de nós (n), o número de laves (l) e o número de nós internos (i) estão relacionados de uma maneira especial, de modo que, se você conhecer qualquer um deles, poderá determinar os outros dois. valores da seguinte forma:
1. Se uma árvore binária completa tem i nós internos:
– Número de folhas l=i+1
– Número total de nós n=2i+1
2. Se uma árvore binária completa tem n nós:
– Número de nós internos i=(n-1)/2
– Número de folhas l=(n+1)/2
3. Se uma árvore binária completa tem l folhas:
– Número total de nós n=2l-1
– Número de nós internos i=l-1
O que é Árvore Binária Completa?
Como mostrado na figura 2, uma árvore binária completa é uma árvore binária na qual todos os níveis da árvore são completamente preenchidos, exceto o último nível. Além disso, no último nível, os nós devem ser anexados a partir da posição mais à esquerda. Uma árvore binária completa de altura h satisfaz as seguintes condições:
– A partir do nó raiz, o nível acima do último nível representa uma árvore binária completa de altura h-1
– Um ou mais nós no último nível podem ter 0 ou 1 filho
– Se a, b são dois nós no nível acima do último nível, então a tem mais filhos do que b se e somente se a estiver situado à esquerda de b
Qual é a diferença entre Árvore Binária Completa e Árvore Binária Completa?
Árvores binárias completas e árvores binárias completas têm uma clara diferença. Enquanto uma árvore binária completa é uma árvore binária na qual cada nó tem zero ou dois filhos, uma árvore binária completa é uma árvore binária na qual todos os níveis da árvore binária são completamente preenchidos, exceto o último nível. Algumas estruturas de dados especiais, como heaps, precisam ser árvores binárias completas, enquanto não precisam ser árvores binárias completas. Em uma árvore binária completa, se você souber o número de nós totais ou o número de laves ou o número de nós internos, poderá encontrar os outros dois com muita facilidade. Mas uma árvore binária completa não possui uma propriedade especial relacionando esses três atributos.
