Prova3 Estrutura de Dados 2014/1

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

PROVA 02 – ESTRUTURA DE DADOS – 30/06/16
Prof Marcus Vinicius Alvim Andrade
RESOLUCAO:
01. a) template<class TC, class TE>
	class ArvBin{
	public:
		class NodoArv{
		private:
			TC chave;
			TE *pelem;
			ArvBin<TC, TE> esq dir;
		};
	private:
		Nodo Arv *raiz;
	}
b) void ArvBin<TC, TE> :: insere(TC k, TE &pe) throw (ErroArv){
	if(EstaVazia())
		raiz=new NodoArv(k, pe);
	elsee if(k< raiz->chave){
		raiz->esq.insere(k,pe);
	elsee if(k> raiz->chave){
		raiz->dir.insere(k,pe);
	elsee 
		throw ErroArv(“Elemento já existe”);
}
void ArvBin<TC, TE>::operator=(ArvBin &a const){
	if(this != a){
		if(a.EstaVazia)
			raiz=NULL;
		elsee
			delete raiz;
			raiz=new NodoArv(a.raiz->chave, a.raiz->pelem, a.raiz->esq, a.raiz->dir);
	}
}
void ArvBin<TC, TE> :: imprimeNivel(int n=1){
	if(!EstaVazia()){
		raiz->esq.imprimeNivel(n+1);
		raiz->dir.imprimeNivel(n+1);
		if(raiz->dir.EstaVazia() && raiz->esq.EstaVazia())
			cout<< (raiz->pelem)<< “no nivel” << n << endl;
	}
	n--;
}
02. a) e b) Conferir em: https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
c) i. CVTAFEQSMZHPK
ii. MESAPHVCFKQTZ
03. i) A altura maxima é n, e a minima é log n(se a arvore for balanceada).
ii) Nao necessariamente, pois em uma arvore pode existir algum elemento a direita q possui um filho a esquerda.
iii) Sim, se a arvore não possuir subarvore da direita, pois em pos-ordem, elas são impressas primeiro.
iv) O numero minimo é 17 pois cada folha tera duas chaves (exceto a raiz). E o numero maximo é 104 pois cada folha tera 4 chaves.
v) A altura maxima é 13 onde cada filho tera o minimo de chaves, e a altura minima e 2, com 4 chaves na raiz e o resto dividido entre as folhas.
vi) Porque a arvore patricia agrupa os nos em uma arvore trie que teria apenas um filho, desse modo, elas teriam, no maximo o mesmo tamanho.