{"id":71,"date":"2017-06-22T17:05:12","date_gmt":"2017-06-22T20:05:12","guid":{"rendered":"http:\/\/web.inf.ufpr.br\/didonet2\/?page_id=71"},"modified":"2017-06-22T17:05:18","modified_gmt":"2017-06-22T20:05:18","slug":"exercicios-bst","status":"publish","type":"page","link":"https:\/\/web.inf.ufpr.br\/didonet\/teaching-disciplinas\/exercicios-bst\/","title":{"rendered":"Exerc\u00edcios BST"},"content":{"rendered":"

1) <\/b>Represente a \u00e1rvore bin\u00e1ria de busca abaixo usando a nota\u00e7\u00e3o com par\u00eanteses aninhados<\/p>\n

——————– 20
\n——————- \/ \u00a0\u00a0 \\
\n—————- 10 \u00a0 \u00a0 30
\n————————- \/\u00a0 \\
\n———————– 25 \u00a0\u00a0 35
\n——————— \/ \u00a0\u00a0 \\
\n——————– 21\u00a0\u00a0 27<\/p>\n

2)<\/b> Defina uma estrutura de dados para representar uma \u00e1rvore bin\u00e1ria de busca, armazenando um conte\u00fado (character) e uma chave (inteira).<\/p>\n

3)<\/b> Descreva vantagens e desvantagens de implementar \u00e1rvores bin\u00e1rias de busca usando vetores ou ponteiros.<\/p>\n

4)<\/b> Implementar uma fun\u00e7\u00e3o para inser\u00e7\u00e3o em \u00e1rvore bin\u00e1ria de busca, usando o m\u00e9todo iterativo (i.e., sem recurs\u00e3o). N\u00e3o \u00e9 necess\u00e1rio ter ponteiro \u201cpai\u201d.<\/p>\n

5)<\/b> Implemente uma fun\u00e7\u00e3o que calcule a altura de uma \u00e1rvore bin\u00e1ria de busca. Qual \u00e9 o tipo de percurso usado na implementa\u00e7\u00e3o?<\/p>\n

6) <\/b> Mostre passo a passo a \u00e1rvore bin\u00e1ria de busca resultante das seguintes opera\u00e7\u00f5es:
\na) Inser\u00e7\u00e3o de 5, 9, 7, 4, 12, 15, 11
\nb) A \u00e1rvore resultante pode ser considerada uma \u00e1rvore AVL? Justifique:
\nc) Remo\u00e7\u00e3o do 9.
\n7) Dada a \u00e1rvore 2-3-4 abaixo, insira a chave 25. A \u00e1rvore resultante deve ser uma \u00e1rvore 2-3-4.
\n———20
\n——-\/\u00a0\u00a0\u00a0\u00a0\u00a0 \\
\n—–17\u00a0\u00a0\u00a0 22 \u2013 24 \u2013 29<\/p>\n

\u00a07)<\/strong> Explique uma vantagem de incluir elementos na raiz de uma arvore bin\u00e1ria de busca.<\/p>\n

\u00a08)<\/strong> Crie uma \u00e1rvore rubro-negra (RN), inclu\u00edndo as chaves 20, 7, 12, 30, 22, nesta ordem, e mostre a \u00e1rvore RN resultante ap\u00f3s cada inser\u00e7\u00e3o. Usar as regras de ajuste aprendidas em aula.<\/p>\n

\u00a09)<\/strong> Usando a \u00e1rvore rubro negra acima, crie uma arvore 2-3-4 correspondente.<\/p>\n

\u00a010) <\/b>Dada a \u00e1rvore B abaixo, de grau m\u00ednimo (t) igual a 2.<\/p>\n

a) inclua as chaves, 20, 21, 28 e 31, nesta ordem, e mostre a \u00e1rvore B resultante ap\u00f3s cada inser\u00e7\u00e3o. A \u00e1rvore poder\u00e1 ser dividida antes da inclus\u00e3o, para que os n\u00f3s abriguem as chaves corretas.<\/p>\n

\u00a0———————————– 26
\n————————–\/ \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \\
\n———12 \u2013 17 \u2013 22\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 29
\n—— \/\u00a0\u00a0\u00a0\u00a0\u00a0 | \u00a0 \u00a0 \u00a0 \u00a0 |\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \\\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \\
\n7-9\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 13\u00a0\u00a0\u00a0\u00a0 18-19\u00a0\u00a0 23-24\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 27\u00a0\u00a0\u00a0\u00a0 30-34-35<\/p>\n

\u00a0b) Porque n\u00e3o podemos incluir o elemento 25 direto na raiz, mesmo que o n\u00f3 possua espa\u00e7os livres?<\/p>\n

\u00a011) <\/b>Considere a estrutura abaixo para representar uma \u00e1rvore bin\u00e1ria de busca.<\/p>\n

typedef struct tNo {<\/p>\n

int chave;<\/p>\n

tNo *esq, *dir, *pai;<\/p>\n

} tNo;<\/p>\n

\u00a0Escreva um algoritmo em C ou em pseudoc\u00f3digo semelhante a C que insira uma nova chave na raiz de uma \u00e1rvore. Seu algoritmo deve receber como entrada um apontador para o n\u00f3 ra\u00edz de uma \u00e1rvore e uma chave, e ap\u00f3s incluir esta chave na raiz da \u00e1rvore de bin\u00e1ria de busca, o algoritmo deve retornar um ponteiro para o nova raiz da \u00e1rvore.<\/p>\n

As fun\u00e7\u00f5es abaixo podem ser utilizadas em seu algorimo:<\/p>\n

tNo* rotacaoDir(tNo *no)<\/p>\n

tNo* rotacaoEsq(tNo *no)<\/p>\n

estas fun\u00e7\u00f5es recebem como par\u00e2metro um ponteiro para um n\u00f3, raiz de uma sub\u00e1rvore, e retornam um ponteiro para a nova raiz da sub\u00e1rvore ap\u00f3s a rota\u00e7\u00e3o para direita ou para a esquerda, respectivamente.<\/p>\n

12) <\/b>Considere uma \u00e1rvore bin\u00e1ria de busca onde os n\u00f3s cont\u00e9m um campo informando a cor do n\u00f3 (preto ou vermelho). Implemente uma fun\u00e7\u00e3o de valida\u00e7\u00e3o que receba uma \u00e1rvore bin\u00e1ria com estas caracter\u00edsticas e verifique se esta \u00e1rvore \u00e9 ou n\u00e3o uma \u00e1rvore rubro-negra.<\/p>\n

Fonte:<\/b> os exerc\u00edcios s\u00e3o fonte pr\u00f3pria, e adapta\u00e7\u00f5es de exerc\u00edcios dos livros da bibliografia do curso, como Cormen et. al, Ziviani et.atl.<\/p>\n","protected":false},"excerpt":{"rendered":"

1) Represente a \u00e1rvore bin\u00e1ria de busca abaixo usando a nota\u00e7\u00e3o com par\u00eanteses aninhados ——————– 20 ——————- \/ \u00a0\u00a0 \\ —————- 10 \u00a0 \u00a0 30 ————————- \/\u00a0 \\ ———————– 25 \u00a0\u00a0 35 ——————— \/ \u00a0\u00a0 \\ ——————– 21\u00a0\u00a0 27 2) Defina uma estrutura de dados para representar uma \u00e1rvore bin\u00e1ria de busca, armazenando um conte\u00fado…<\/p>\n","protected":false},"author":21,"featured_media":0,"parent":31,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-71","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/71","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/comments?post=71"}],"version-history":[{"count":2,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/71\/revisions"}],"predecessor-version":[{"id":75,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/71\/revisions\/75"}],"up":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/31"}],"wp:attachment":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/media?parent=71"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}