Marque a alternativa que apresenta propriedades características de uma Árvore de Busca Binária:
Respostas
Resposta:
Seja S = {s1, s2, ..., sn} um conjunto de chaves tais que s1 < s2 ... sn. Seja k um valor dados. Deseja-se verificar se k {\displaystyle \in }\in S e identificar o índice i tal que k = si.
A Árvore Binária de Busca (ABB) resolve os problemas propostos. A figura ilustra uma ABB.
Uma ABB é uma árvore binária rotulada T com as seguintes propriedades:
T possui n nós. Cada nó u armazena uma chave distinta sj {\displaystyle \in }\in S e tem como rótulo o valor r(u) = sj.
Para cada nó v de T r(v1) < r(v) e r(v2) > r(v), onde v1 pertence à subárvore esquerda de v e v2 pertence à subárvore direita de v.
Dado o conjunto S com mais de um elemento, existem várias ABB que resolvem o problema.
Elementos
Nós - são todos os itens guardados na árvore
Raiz - é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8)
Filhos - são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3)
Pais - são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14)
Folhas - são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13)
Complexidade[3]
A complexidade das operações sobre ABB depende diretamente da altura da árvore.
Uma árvore binária de busca com chaves aleatórias uniformemente distribuídas tem altura O(log n).
No pior caso, uma ABB poderá ter altura O(n). Neste caso a árvore é chamada de árvore zig-zag e corresponde a uma degeneração da árvore em lista encadeada.
Em função da observação anterior, a árvore binária de busca é de pouca utilidade para ser aplicada em problemas de busca em geral. Daí o interesse em árvores balanceadas, cuja altura seja O(log n) no pior caso
Explicação:
marca como melhor resposta pvf
Resposta:
Seja S = {s1, s2, ..., sn} um conjunto de chaves tais que s1 < s2 ... sn. Seja k um valor dados. Deseja-se verificar se k {\displaystyle \in }\in S e identificar o índice i tal que k = si.
A Árvore Binária de Busca (ABB) resolve os problemas propostos. A figura ilustra uma ABB.
Uma ABB é uma árvore binária rotulada T com as seguintes propriedades:
T possui n nós. Cada nó u armazena uma chave distinta sj {\displaystyle \in }\in S e tem como rótulo o valor r(u) = sj.
Para cada nó v de T r(v1) < r(v) e r(v2) > r(v), onde v1 pertence à subárvore esquerda de v e v2 pertence à subárvore direita de v.
Dado o conjunto S com mais de um elemento, existem várias ABB que resolvem o problema.
Elementos
Nós - são todos os itens guardados na árvore
Raiz - é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8)
Filhos - são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3)
Pais - são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14)
Folhas - são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13)
Complexidade[3]
A complexidade das operações sobre ABB depende diretamente da altura da árvore.
Uma árvore binária de busca com chaves aleatórias uniformemente distribuídas tem altura O(log n).
No pior caso, uma ABB poderá ter altura O(n). Neste caso a árvore é chamada de árvore zig-zag e corresponde a uma degeneração da árvore em lista encadeada.
Em função da observação anterior, a árvore binária de busca é de pouca utilidade para ser aplicada em problemas de busca em geral. Daí o interesse em árvores balanceadas, cuja altura seja O(log n) no pior caso
Leia mais em Brainly.com.br - https://brainly.com.br/tarefa/28885335#readmore
Explicação: