1 - Uma árvore binária é uma árvore onde cada nó tem no máximo 2 filhos. Uma árvore binária de busca é uma árvore binária onde os elementos da subárvore esquerda são menores que a raiz e os elementos da subárvore direita são maiores que a raíz. Portanto explique como serão inseridos os elementos 10, 20, 15, 18, 30, 40 e 13 numa árvore binária de busca.
R: Insere o 10 como raiz, 20 a direita, o 15 a esquerda do 20, o 30 a direita do 20, 13 a esquerda do 15, 18 a direita do 15 e 40 a direita do 30.
2 - Sabendo que podemos inserir elementos numa árvore binária e que isso é uma operação básica das árvores, indique e explique quais são as operações básicas de uma árvore binária?
R: Inserção – é quando se insere novo item na arvore seguindo a regra esquerdo menor e direito maior e sempre nas extremidades (folhas).
Exclusão – é quando se exclui um item existente, que pode não conter filhos, conter somente um filho ou conter dois filhos.
3 - Sabendo que as árvores binárias podem ser cheias e completas e que uma árvore otimal é uma árvore completa que a operação de inserção segue a regra de inserção por ordem das chaves. Como as inserções sempre ocorrem à nível de folha, deve-se primeiro inserir as chaves que ficarão mais perto da raíz. Se temos um conjunto de chaves {c1,..,ci} tal que c1<...<ci, deve se inserir o valor médio das chaves, inserir o conjunto das chaves inferior a esse valor, e inserir o conjunto das chaves superior a esse valor. Portanto no conjunto de chaves K={1,2,3,4,5,6,7}. Uma ordem de inserção otimal seria o 4, 2, 6, 1, 7, 5 e 3. Explique como ficaria uma inserção otimal do conjunto K={2,4,6,8,10,12,14}.
R: Como raiz usaremos o nurmero 8 pois o mesmo é o numero médio (existem três algarismo tanto a esquerda quanto a direita), o numero 4 será o filho a esquerda e o 12 o filho a direita (pois os mesmo são números médios em relação a 2 e 6, e, 10 e 14, respectivamente). 2 será a esquerda de 4 e 6 a direita, 10 a esquerda de 12 e 14 a direita.
4 - Uma das operações mais úteis das ABB é a localização, outra característica desse tipo de árvore são os chamados percursos que mostram os elementos que a árvore contém e que são classificados em pré-fixado/pré-ordem, pós-fixado/pós-ordem e in-ordem/em ordem. Explique como funciona o procedimento para realizar cada percurso considerando as subárvores. Existe alguma diferença com relação às árvores binárias comuns?
R: Basicamente a diferença está na forma de inserção e busca dos elementos, enquanto as arvores binárias comuns insere elementos sem necessidade de verificar qual elemento é maior ou menor (dificultando a busca de elementos), a arvore de busca insere raiz-(menor) à esquerda e (maior) à direita (facilitando a busca dos elementos).
Nenhum comentário:
Postar um comentário