Diferença Entre árvore Binária Completa E árvore Binária Completa

2024 Autor: Mildred Bawerman | [email protected]. Última modificação: 2023-12-16 08:41

Árvore Binária Completa vs. Árvore Binária Completa

A árvore binária é uma árvore em que 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 filhos contêm uma referência a seus pais. 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 começando da posição mais à esquerda. Uma árvore binária completa é aquela em que cada nó da árvore possui dois filhos, exceto as folhas da árvore.

O que é árvore binária completa?

A árvore binária completa é uma árvore binária na qual cada nó da á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 descreve 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 forma especial de forma que se você conhece qualquer um deles, você pode determinar os outros dois valores da seguinte forma:

1. Se uma árvore binária completa tiver i nós internos:

- Número de folhas l = i + 1

- Número total de nós n = 2 * i + 1

2. Se uma árvore binária completa tiver 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 tiver l folhas:

- Número total de nós n = 2 * l-1

- Número de nós internos i = l-1

O que é árvore binária completa?

Conforme 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 começando da posição mais à esquerda. Uma árvore binária completa de altura h satisfaz as seguintes condições:

- 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 diferença clara. 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 total de nós ou o número de laves ou o número de nós internos, poderá encontrar os outros dois facilmente. Mas uma árvore binária completa não tem uma propriedade especial relacionando esses três atributos.