SóProvas

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

Considere uma árvore B de grau mínimo igual a 2 (o que significa que cada nó pode ter, no máximo, 3 chaves) inicialmente vazia, na qual são inseridas as chaves N, D, T, B, Z, K, R, F, G, nesta ordem, as quais são comparadas com base na ordem do alfabeto. Considerando o algoritmo de inserção em uma única passagem, conclui-se que

Alternativas
Comentários
  • O enunciado diz que o grau mínimo é t=2, portanto cada nó não folha pode ter até 2t filhos, ou seja, 4 filhos. Cada nó pode conter até 2t-1 chaves, ou seja, 3 chaves.A árvore resultante ficou: DN (raiz), B (1º nó folha), FGK (2º nó folha) e RTZ (3º nó folha).Assim: a) Falsa, pois a altura da árvore é 2 (só raiz e folhas)b) Falsa, pois B está em um nó folhac) Falsa, pois K está em um nó folhad) Falsa, pois só há 3 nós folhas.e) Correta, F e G estão no segundo nó folha.
  • Propriedades de uma árvore B de grau mínimo t:
    - t tem que ser maior ou igual a 2;
    - Todo nó deve ter no mínimo t filhos e no máximo 2t filhos;
    - Todo nó deve ter no mínimo (t-1) chaves e no máximo (2t -1) chaves;
     
    Na questão t=2, então essa árvore deve ter no mínimo 2 filhos e no máximo 4 filhos. E deve ter, no mínimo 1 chave e no máximo 3 chaves. Sabendo disso devemos realizar as inserções:



    Agora é só analisar as alternativas. 
     
    A) Errado. Altura = 1.
    B) Errado. B é nó folha.
    C) Errado. O nó raiz possui somente as chaves D e N.
    D) Errado. A árvore final possui 3 nós folhas.
    E) Correto.
  • Simonne,

    Por que ao inserir o B, vc subiu a letra N e não a letra D? Na minha resolução subi a letra D.


    inserindo N, D e T:

                        DNT

    inserindo B:

                      BDNT
    cisão:

                      D
                B         NT

    inserindo Z:

                      D
                B         NTZ

    inserindo K:

                      D
                B         KNTZ

    cisão:

                      DN
                B     K     TZ

     inserindo R:

                      DN
                B     K     RTZ

    inserindo F:

                        DN
                B     FK    RTZ

    inserindo G:

                         DN
                B     FGK   RTZ

    a)Altura da árvore é 2 não é 1. :)
    b)B é folha
    c)Nó raiz não tem chave K
    d)3 nós folhas
    e)F e G pertencem a mesma folha.

    Resp: letra e
  • Frederico,

    quando o nó está cheio, vc passa o elemento do meio do nó para seu pai. Então quando estamos com DNT e queremos inserir o B, pegamos o N que é o elemento do meio e colocamos para ser o pai.

    B -> DNT

          N
    BD     T

    http://pt.wikipedia.org/wiki/%C3%81rvore_B#Inser.C3.A7.C3.A3o
  • Segui o seguinte raciocínio:
    Foram inseridos os nós na sequencia: N, D, T, B, Z, K, R, F, G
    Atribui um número a cada letra ordenadamente.
    N=6,D=2,T=8,B=1,Z=9,K=5,R=7,F=3,G=4
    A minha árvore B ficou diferente da considerada como certa pela banca e por vocês. Ao invés de subir com o D, eu subi
    com o F. gerando a árvore abaixo:
    http://img855.imageshack.us/img855/2323/imgvb.png
     
    Resolvi tirar a prova no site abaixo que tem um applet para mostrar o funcionamento:
    http://people.ksp.sk/~kuko/bak/
     
    O site deu o mesmo resultado que eu encontrei...
  • Galera achei que quando tivesse cheio poderia colocar qualquer chave central, mas me parece que subindo com chaves diferentes a arvore fica diferente....

    por exemplo em  KNTZ => se eu subir com o T não vai dar certo.....

    tem o jeito de certo de fazer ?    


    aguardo. abs ! 
  • Marco Aurelio,

    O jeito certo eh o seguinte:

    De acordo com o livro "Algoritmos: Teoria e Prática", o processo de inserir um noh eh recursivo, de forma q ele segue uma logica similar a seguinte:

    inserir_noh (T,x) {
       r = raiz[T]
       if ( "r é noh completo" )  { ## completo significa ter o numero maximo de chaves (3, no caso)
            T= quebrar (T, r)  ## quebra o noh, fazendo a altura aumentar. E como o numero maximo é 3 (2t-1 --> sempre IMPAR), PEGA SEMPRE O ELEMENTO DO MEIO
            Inserir_com_raiz_nao_completa( T, x )
       } else {
            Inserir_com_raiz_nao_completa( T, x )
       }
    }

    Da mesma forma, a rotina (RECURSIVA) "Inserir_com_raiz_nao_completa":
       A cada nivel que desce, a primeira coisa q ela faz eh conferir s o noh corrente eh completo. Se for, ela também dah logo um jeito de "quebrar" esse noh, "bombeando SEMPRE O ELEMENTO DO MEIO para o noh de cima (QUE, por sua vez, NAO EH COMPLETO, POIS JA FOI VISITADO NA RECURSAO ANTERIOR À CORRENTE).
       se o noh corrente for folha
           FINALMENTE INSERE A CHAVE x
       else
           continua descendo na árvore por meio da rotina recursiva "Inserir_com_raiz_nao_completa"