Estrutura de dados tipo arovore

1.

Estrutura de dados do tipo árvore – Definição.

2.

Árvore Binária – Definição.

3.

Árvore Binária – Propriedades.

4.

Árvore Binária – Análise de Complexidade.

5.

Operações com arvore binária.

6.

Árvore AVL – Definição.

7.

Bibliografia

Uma Arvore é uma estrutura de dados bidimensional, não-linear, que possui propriedades espaciais e admite muitas operações de conjunto dinâmicos, tais como: pesquisa, inserção, remoção, entre outros. Árvores binárias são árvores que ou são nulas ou são constituídas por um nó raiz e duas sub-árvores binárias, a sub-árvore esquerda e a sub-árvore direita. Árvores binárias são especiais porque, quando ordenadas, permitem pesquisas, inserções e exclusões rápidas.

Representação esquemática da definição da estrutura de árvore binária.

Representação esquemática da definição da estrutura de árvore binária.

Toda árvore binária possui as seguintes propriedades:
a) Todos os nós da sub-árvore direita são maiores que o nó raiz.
b) Todos os nós da sub-árvore esquerda são maiores que o nó raiz.

c) Cada sub-árvore é uma árvore binária.

d) O grau de um nó representa é o seu número de sub-árvores. e) Em uma árvore binaria, o grau máximo de

um nó é 2.
f) O grau de uma árvore é igual ao máximo dos graus de todos os seus nós.
g) Uma arvore binária tem grau máximo igual a 2.

h) Nó pai: nó acima e com ligação direta a outro nó. i) Nó filho: nó abaixo e com ligação direta a outro nó. São os nós raízes das sub-árvores.
j) Nós irmãos: nós que possuem o mesmo nó pai.
k) Nó folha ou terminal: nó que não possui filhos.
l) Nó ancestral: são os nós que estão acima de um nó e possuem ligação direta ou indireta.

m) Nó descendente: são os nós que estão abaixo de um nó e possuem ligação direta ou indireta.
n) Nó descendente direito: são os nós que estão abaixo de um nó e possuem ligação direta ou indireta e fazem parte da sub-árvore direita.
o)