SóProvas

ID
17818
Banca
CESGRANRIO
Órgão
BNDES
Ano
2008
Provas
Disciplina
Algoritmos e Estrutura de Dados

Considere uma árvore B de ordem 2 inicialmente vazia.
Os números abaixo são inseridos na seguinte ordem:

10, 15, 8, 3, 4, 12, 20, 9.

Que número(s) compõe(m) o nó raiz?

Alternativas
Comentários
  • http://slady.net/java/bt/view.php
  • Ingrid, muito obrigado pela seu post. Muito bom o programa. Esclareceu todas as dúvidas. Valeu mesmo. Deus te abençoe.
  • Introduzi os números em http://groups.engin.umd.umich.edu/CIS/course.des/cis350/treetool/index.html ehttp://slady.net/java/bt/view.phpe obtive:Nível 0, Nó 1: 10Nível 1, Nó 1: 4; Nó 2: 15Nível 2, Nó 1: 3; Nó 2: 8, 9; Nó 3: 12; Nó 4: 20Logo a resposta seriab)
  • A árvore b-tree de orden 2 tem até 4 elementos em cada nó, no caso a inserção ficaria assim:1010,15inserindo sempre de forma ordenada8,10,153,8,10,15quando o nó está cheio, o elemento é inserido, o elemento do meio é passado para a raiz da árvore, e as partes restantes se tornam filhos do elementopromovido. deste modo:3,4,8,10,15(o 8 é o elemento do meio)----8-------|-----|-3,4--10,15a próxima inserção vai para o nó correspondente:----8-----|------|-3,4--10,12,15----8-----|------|-3,4--10,12,15,20 (o nó da direita está cheio)----8-----|------|-3,4--9,10,12,15,20 (acontece da mesma forma que antes)o elemento 12 sobe para o nó raiz e a folha da direita se divide em duas.----8--,--12-------|----|----|-----3,4--9,10--15,20
  • Como a ordem é 2  (seja d a ordem), temos as seguintes propriedades:
    1.  d <= número de chaves <= 2d
      --> exceto a raiz que tem entre 1 e 2d
    2.  d+1 <= número de ponteiros <=  2d +1
      --> exceto a raiz que tem entre 2 e 2d +1 ponteiros.

    Logo, a resposta é realmente a letra D. A letra B dá quando se usa a ordem igual a 1, porém a ordem dado na questão é 2.
  • Apenas colando uma imagem para que fique mais rápida a compreensão da resposta:


    Excelente link enviado pela Ingrid Lotfi.

  • O número máximo de ponteiros em um nó é a ordem da árvore!
    Porém, existem controvérsias, alguns autores definem que o número de elementos será 2ordem, ou seja, para ordem=2, teremos 4 elementos e para ordem=3, teremos 8 elementos. Essa posição minoritária é adotada pela CESGRANRIO!
  • -> 10, 15, 8, 3, 4, 12, 20, 9
    ---------------------------
    []
     
    -> 10, 15, 8, 3
    ---------------------------
    [3 8 10, 15]
     
    -> 4
    ---------------------------
            [8]
    [3 4]       [10, 15]
     
    -> 12, 20
    ---------------------------
            [8]
    [3 4]      [10, 12 15 20]
     
    -> 9
    ---------------------------
            [8           12]
    [3 4]      [9 10]       [15 20]
    ---------------------------

  • Como se usa esse SLADY.NET?
    Pra mim apareceu uma página esquisita. Onde insiro os números?

  • Conceito de ORDEM: Número de elementos minímo que uma página deve possuir, que é sempre 50% do seu tamanho máximo.

     

    Se a questão diz que a árvore tem ordem 2, quer dizer que seu tamanho máximo é 4.

     

    Inserimos inicialmente os 4 números, de forma ordenada: (3, 8, 10, 15).

     

    - Para inserir o nº 4, teremos que subdividir a árvore em duas, promovendo o item do meio (3, 4, 8, 10, 15) para a raiz, ficando:

     

    Raiz: (8)

    Página 1: (3, 4)

    Página 2: (10,15)

     

    - Podemos inserir o 12 e o 20 normalmente, pois cabem na página 2, ficando então:

     

    Raiz: (8)

    Página 1: (3, 4)

    Página 2: (10,12,15, 20)

     

     

    - Finalmente, precisamos inserir o 9. Para mantermos a propriedade binária de busca, é necessário inserir na página 2, que contém números à direita da raiz, ou seja, maiores que 8.

    Então subdividimos a página 2, promovendo o item do meio (9, 10, 12, 15, 20) para a raiz, ficando então:

     

    Raiz: (8, 12)

    Página 1: (3, 4)

    Página 2: (9, 10,15, 20).

     

    GABARITO: D)