[PosComp] [2016] Questão 26



QUESTÃO 26 – Uma árvore balanceada T que armazena n chaves é uma árvore binária de pesquisa
na qual
A) a diferença entre as alturas de suas subárvores permanece constante em todo o caso, após
inserções ou remoções de chaves.
B) as operações de inserção e remoção de chaves em nodos internos v de T seguem um padrão linear
de tempo de execução.
C) a propriedade da altura/balanceamento é determinada pela extensão do caminho mais curto entre
um nodo interno v até o nodo raiz de T.
D) a variação da altura dos nodos filhos de cada nodo interno v de T é de, no máximo, uma unidade.
E) o tempo de execução para todas as operações fundamentais sobre cada nodo interno v de T se
mantém constante.


Resposta

Uma árvore binária é uma estrutura de dados caracterizada por:

  • Ou não tem elemento algum (árvore vazia).
  • Ou tem um elemento distinto, denominado raiz, com dois ponteiros para duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita.


Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores binárias de busca

Uma Árvore Binária de Busca possui as mesmas propriedades de uma AB, acrescida da seguinte propriedade: Para todo nó da árvore, se seu valor é X, então: 
 Os nós pertencentes a sua sub-árvore esquerda possuem valores menores do que X; 
 Os nós pertencentes a sua sub-árvore direita possuem valores maiores do que X. 
 Um percurso em in-ordem nessa árvore resulta na seqüência de valores em ordem crescente

Arvores Balanceadas (AVL)

Uma árvore binária T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade.


Portanto: 
D) a variação da altura dos nodos filhos de cada nodo interno v de T é de, no máximo, uma unidade.

[PosComp] [2016] Questão 26 [PosComp] [2016] Questão 26 Reviewed by Vinicius dos Santos on 16:21:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!