Aula 07 – 12/04
Continuação árvores binárias – Informações sobre o 1º TAE
Livro
http://www.casadocodigo.com.br/products/l
ivro-programador-apaixonado
•
História de produtos inovadores
•
Dicas de empreendedorismo
•
Dicas para carreira em desenvolvimento
de software
•
São capítulos curtos com de 2 a 4 páginas
•
De fácil leitura
codecademy
http://www.codecademy.com/
•
JavaScript
•
HTML/CSS
•
PHP
•
Python
•
Ruby
•
APIs
Tipos especiais de árvores
Árvores estritamente binarias
• Cada nó possui 0(folha) ou 2 filhos
Árvores binaria cheia
• Todas as sub arvores vazias se localizam no último nível
Árvore binaria completa
• É cheia até o penúltimo nível, ou seja, o último ou penúltimo nível
tem sub arvores vazias
Árvore Ziguezague
• É quando os nós que não são folhas possuem somente um filho
(esquerdo ou direito).
• As arvores ziguezague são estrutura que devem ser evitadas pois se
assemelham a lista.
TAE
Conceitos de balanceamento
• O custo de aceso a uma chave que pertence a árvore depende da
altura da arvore. A busca em uma árvore inicia pela raiz, e a partir do
nó raiz o caminho possui um direcionamento com base na chave
• A situação em questão é percorrer um caminho da raiz até a chave
desejado, tanto para operações de busca, inserção exclusão e edição
de registos.
• É desejável que a altura de uma arvores de busca seja o menor
possível.
• A ideia do balanceamento e deixar o custo de acesso ao nó desejado
o menor possível.
• São exemplo de árvores balanceadas as árvores completas e as
arvores cheias.
• A ideia das arvores AVL é que a altura dos nós da esquerda e da direta
sejam iguais ou difiram em nó máximo uma unidade
• O balanceamento é feito através de rotações dos nós.
• Na imagens abaixo um exemplo de rotação em árvores.