Desenvolvimento de um SGBD - 06/02
10 pontos
- Criação de um programa em C que implemente CRUD
- Mostrar execução do código com as 4 funções implementadas
Questões:
- 1. Qual o custo do algoritmo?
- Um algoritmo deve:
- Funcionar corretamente
- Executar o mais rápido possível
- Utilizar a memória da melhor forma possível
- 2. Qual foi o percurso utilizado?
- Em nível: Neste tipo de percurso os nós são visitados de cima para baixo e da esquerda para a direita. Em relação ao exemplo, a ordem de visita dos nós seria: A B C D E F G H I. O algoritmo pode utilizar uma fila. A ideia é colocar a raiz da árvore binária na fila e, a partir daí, visitar o nó do início da fila, ao mesmo tempo em que se colocam seus filhos no final da mesma.
- Pré-ordem: Neste tipo de percurso visita-se prioritariamente a raiz, em seguida a subárvore da esquerda e, depois, a subárvore da direita. Para o exemplo adotado, a ordem de visita seria: A B D C E F G H I. O algoritmo pode utilizar uma pilha. A ideia é colocar a raiz na pilha e, a partir daí, visitar o nó do topo da pilha, ao mesmo tempo em que se empilham a raiz da subárvore direita e da subárvore esquerda
- Ordem simétrica: Neste tipo de percurso visita-se prioritariamente a subárvore da esquerda, em seguida a raiz e, finalmente, a subárvore da direita. No exemplo, teríamos: B D A E C H I G F. O algoritmo que será apresentado também utiliza uma pilha. A idéia é colocar, sucessivamente, a raiz da subárvore esquerda na pilha até se chegar a um link nulo, quando então se visita o topo da pilha, repetindo-se o processo para a subárvore da direita.
- Pós-ordem: Neste tipo de percurso visita-se prioritariamente a subárvore da esquerda, em seguida a subárvore da direita e, por fim, a raiz. Para o exemplo adotado, a ordem de visita seria: D B E I H G F C A. O algoritmo pode utilizar uma pilha e é um algoritmo de difícil entendimento, devendo ser verificado cuidadosamente. Cada nó é colocado na pilha duas vezes. A primeira quando se está empilhando ramos à esquerda da árvore; a segunda quando o empilhamento é pela direita. Um nó só é visitado quando ele é o topo da pilha e foi a segunda vez que entrou na mesma.
- Referência:
- Paulo Eustáquio Duarte Pinto
- Instituto de Matemática e Estatística
- Departamento de Informática e Ciência da Computação
- Universidade Estadual do Rio de Janeiro
- Agosto de 2002