{"id":77,"date":"2017-06-22T17:06:26","date_gmt":"2017-06-22T20:06:26","guid":{"rendered":"http:\/\/web.inf.ufpr.br\/didonet2\/?page_id=77"},"modified":"2017-06-22T17:08:59","modified_gmt":"2017-06-22T20:08:59","slug":"exercicios-rbt","status":"publish","type":"page","link":"https:\/\/web.inf.ufpr.br\/didonet\/teaching-disciplinas\/exercicios-rbt\/","title":{"rendered":"Exerc\u00edcios RBT"},"content":{"rendered":"
\n
\n

1) <\/b>Crie uma \u00e1rvore bin\u00e1ria para armazenar a seguinte express\u00e3o aritm\u00e9tica: (14 – (12 -25) * (32-47) % 6 ). A prioridade entre os operadores deve ser respeitada.<\/p>\n

2) C<\/b>rie tr\u00eas fun\u00e7\u00f5es de busca em \u00e1rvore bin\u00e1ria de busca que:<\/p>\n

a) encontre uma chave K, percorrendo a \u00e1rvore em pr\u00e9-ordem;<\/p>\n

b) encontre uma chave K, percorrendo a \u00e1rvore em ordem;<\/p>\n

c) encontre uma chave K, percorrendo a \u00e1rvore em p\u00f3s-ordem.<\/p>\n

Para cada uma das fun\u00e7\u00f5es, imprimir os n\u00f3s percorridos.<\/p>\n

3)<\/b> Escreva o resultado da execu\u00e7\u00e3o da aplica\u00e7\u00e3o das fun\u00e7\u00f5es do exerc\u00edcio (2) para a \u00e1rvore abaixo, seguindo os crit\u00e9rios:<\/p>\n

a) chave 30, fun\u00e7\u00e3o (a)<\/p>\n

b) chave 35, fun\u00e7\u00e3o (b)<\/p>\n

c) chave 25, fun\u00e7\u00e3o (c)<\/p>\n

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

4)<\/b> Implemente uma fun\u00e7\u00e3o que some os elementos pares de uma \u00e1rvore bin\u00e1ria de busca.<\/p>\n

5)<\/b> Implementar uma fun\u00e7\u00e3o que, dada uma chave K, busque o seu elemento sucessor. Usar m\u00e9todo iterativo.<\/p>\n

6)<\/b> Explique a diferen\u00e7a entre o m\u00e9todo de balanceamento de uma \u00e1rvore AVL e uma \u00e1rvore rubro-negra. Existe uma das duas em que o fator de balanceamento \u00e9 menor (\u00e1rvore mais balanceada)?<\/p>\n

7) <\/b>Dada a \u00e1rvore abaixo:<\/p>\n

a) Descreva o fator de balanceamento de cada n\u00f3.<\/p>\n

b) Insira o elemento 8 na raiz, e mostre as \u00e1rvores resultantes ap\u00f3s cada rota\u00e7\u00e3o, at\u00e9 o resultado final.<\/p>\n

c) Explique como podemos adaptar de maneira simples o algoritmo de inser\u00e7\u00e3o em \u00e1rvore bin\u00e1ria de busca para suportar inser\u00e7\u00e3o na raiz.<\/p>\n

– \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 40
\n– \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \/ \u00a0 \u00a0\u00a0 \\
\n– \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0 10 \u00a0 \u00a0\u00a0 \u00a0 50
\n– \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0 \/\u00a0 \\
\n– \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 09 \u00a0 18
\n– \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0 \/\u00a0 \u00a0\u00a0 \\
\n– \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0 15 \u00a0 20<\/p>\n

8) <\/b>Como modificar a fun\u00e7\u00e3o de rota\u00e7\u00e3o \u00e0 esquerda abaixo para suportar um ponteiro para o n\u00f3 pai?<\/p>\n

– tNo rotEsq( tNo no ){<\/p>\n

–\u00a0\u00a0\u00a0 tNo aux;<\/p>\n

–\u00a0\u00a0\u00a0 aux = no->dir;<\/p>\n

–\u00a0\u00a0\u00a0 no->dir = aux->esq;<\/p>\n

–\u00a0\u00a0\u00a0 aux->esq = no;<\/p>\n

–\u00a0\u00a0\u00a0 return aux;<\/p>\n

}<\/p>\n

9)<\/b> Explique quais s\u00e3o as propriedades de uma \u00e1rvore para ser uma \u00e1rvore 2-3-4.<\/p>\n

10) <\/b> O c\u00f3digo abaixo foi projetado para buscar chaves em uma \u00e1rvore 2-3-4. Por\u00e9m, ele cont\u00e9m um problema. Explique qual \u00e9 o problema e como corrigi-lo.<\/p>\n

tNo busca (tNo *no, int chave) {
\n–\u00a0\u00a0 if( no != NULL ){
\n–\u00a0\u00a0\u00a0\u00a0\u00a0 for( i=0; i < no.tam; i++)
\n–\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if( no.chave[i] == chave )
\n–\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return no;
\n–\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 else if( chave < no.chave[i] )
\n–\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return busca( no.p [i], chave );
\n–\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return no;
\n–\u00a0\u00a0\u00a0 }
\n}<\/p>\n

11) <\/b>Porque usar a t\u00e9cnica de inclus\u00e3o na folha \u00e9 vantajosa em \u00e1rvores 2-3-4?<\/p>\n

12)<\/b> Dada a \u00e1rvore 2-3-4, represente uma \u00e1rvore rubro-negra equivalente.<\/p>\n

———– \u00a0 25
\n——–\u00a0 \/\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \\
\n—20-22-24 \u00a0\u00a0 26 \u2013 27<\/p>\n

13)<\/b> Crie uma \u00e1rvore rubro-negra incluindo os seguintes elementos, nesta ordem: 10, 2, 3, 12, 11. Mostrar as \u00e1rvores resultantes ap\u00f3s cada inser\u00e7\u00e3o.<\/p>\n

14) <\/b>A altura m\u00ednima de uma \u00e1rvore \u00e9 o n\u00famero de n\u00f3s pretos a partir da raiz. Implemente um algoritmo que calcule a altura m\u00ednima de uma \u00e1rvore rubro-negra.<\/p>\n

15) <\/b>Dada a \u00e1rvore rubro negra abaixo:<\/p>\n

a) exclua o 16.<\/p>\n

–\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 16
\n–\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <b>
\n–\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\u00a0\u00a0\u00a0 \u00a0 \\
\n–\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 12\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 18
\n–\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <b>\u00a0\u00a0\u00a0\u00a0\u00a0 <b>
\n–\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\u00a0\u00a0\u00a0 \u00a0 \u00a0\u00a0 \/\u00a0\u00a0\u00a0\u00a0 \\
\n–\u00a0\u00a0\u00a0\u00a0 11 \u00a0\u00a0\u00a0\u00a0 17 \u00a0\u00a0\u00a0\u00a0\u00a0 22
\n–\u00a0\u00a0\u00a0 <b> \u00a0\u00a0 <b>\u00a0\u00a0\u00a0\u00a0\u00a0 <r>
\n–\u00a0\u00a0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0 \u00a0\u00a0 \u00a0\u00a0\u00a0 \/\u00a0\u00a0\u00a0 \\
\n–\u00a0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0 \u00a0\u00a0\u00a0 20 \u00a0\u00a0\u00a0 25
\n– \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0 \u00a0 <b>\u00a0\u00a0 <b><\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

1) Crie uma \u00e1rvore bin\u00e1ria para armazenar a seguinte express\u00e3o aritm\u00e9tica: (14 – (12 -25) * (32-47) % 6 ). A prioridade entre os operadores deve ser respeitada. 2) Crie tr\u00eas fun\u00e7\u00f5es de busca em \u00e1rvore bin\u00e1ria de busca que: a) encontre uma chave K, percorrendo a \u00e1rvore em pr\u00e9-ordem; b) encontre uma chave K,…<\/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-77","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/77","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=77"}],"version-history":[{"count":1,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/77\/revisions"}],"predecessor-version":[{"id":78,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/77\/revisions\/78"}],"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=77"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}