Ai sim

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1086 palavras )
  • Download(s) : 0
  • Publicado : 28 de novembro de 2011
Ler documento completo
Amostra do texto
Árvore B (B-tree)

Introdução
O criador das árvores B, Rudolf Bayer, não definiu claramente de onde veio o B das árvores B. Ao que parece, o B vem de balanceamento onde todos os nós da árvore estão em um mesmo nível. Também é possível que o B tenha vindo de seu sobrenome Bayer, ou ainda do nome da empresa onde trabalhava, a Boeing Scientific Research Labs.
Suas principaiscaracterísticas são:
- Em uma árvore-B cada nó da árvore do pode conter um grande número de chaves (elementos).
- O número de sub-árvores de cada nó pode ser muito grande.
- A altura da árvore é geralmente muito pequena.
Estrutura do nó da árvore
Considerando X como um nó interno da árvore B e n o número de chaves (elementos) armazenadas em X:
- as n chaves (elementos) k1, k2...kn sãoarmazenadas em ordem crescente;
- e X possui n+1 ponteiros f1, f2...fn+1 para seus filhos

f1 |K1 |F2 |K2 |f3 |K3 |f4 |K4 |... |... |fn |Kn |fn + 1 | |
Em um nó, cada campo chave tem associado a ele um campo ponteiro para um nó filho, esse nó filho é a raiz de uma sub-árvore que contém nós com todos os valores de chave menores ou iguais ao valor da chave em questão no nó pai; emaiores do que o valor da chave anterior no nó pai.
Cada nó tem também um campo ponteiro adicional que indica o seu filho mais à direita, esse nó é a raiz de uma subárvore que contém nós com todos os valores de chave maiores do que todas as chaves do nó pai.
Exemplo de uma árvore B de ordem 3:
• ordem (m) = 3 (número de filhos em cada nó)
[pic]

Exemplo de uma árvore B deordem 5:
• m = 5 (ordem)
• n = 4 (elementos)
[pic]
Busca em Árvore B
Processo similar à busca em uma árvore binária. Comparação entre os valores da chave de busca e das chaves armazenadas na árvore B. Como as chaves estão ordenadas, pode-se realizar uma busca binária nos elementos de cada nó. Se a chave não for encontrada no nó em questão, continua-se a busca nos filhos destenó, realizando-se novamente a busca binária.
Inserção em Árvore B
- Localizar o nó folha X onde o novo elemento deve ser inserido.
- Se o nó X estiver cheio, realizar uma subdivisão (split) de nós:
▪ Passar o elemento mediano de X para seu pai;
▪ Inserir a nova chave.
- Se o pai de X também estiver cheio, repete-se recursivamente a subdivisão (split) acima para o pai de X.- No pior caso terá que aumentar a altura da árvore B para poder inserir o novo elemento
Exemplo:
m = 5
n = 4

|60 | |00 | |00 | |00 | | |- Inserir 40, 60:
|40 | |60 | |00 | |00 | | |- Inserir 90:
|40 | |60 | |90 | |00 | | |- Inserir 70:
|40 | |60 | |70 | |90 | | |- Inserir 92:
|40 | |60 | |70 | |90 | |92 |split | |
|70 | |00 | |00 | |00 | | ||40 | |60 | |00 | |00 | | |000000000000 | |90 | |92 | |00 | |00 | | |- Inserir 62 e 65:
|70 | |00 | |00 | |00 | | |
|40 | |60 | |62 | |65 | | |000000000000 | |90 | |92 | |00 | |00 | | |- Inserir 45:
|70 | |00 | |00 | |00 | | |
|40 | |45 | |60 | |62 | |65 |split000000000000 | |90 | |92 | |00 | |00 | | |

|60 | |70 | |00 | |00 | | ||40 | |45 | |60 | |62 | | | |60 | |65 | |00 | |00 | | | |90 | |92 | |00 | |00 | | |- Inserir 67 e 68:

|60 | |70 | |00 | |00 | | |
|40 | |45 | |60 | |62 | | | |60 | |65 | |67 | |68 | | | |90 | |92 | |00 | |00 | | |- Inserir 69:

|60 | |70 | |00 | |00 | | |
|40 | |45 | | | | | | | |60 | |65 | |67 | |68 | |69 |Split00| |90 | |92 | | | | | | |

|60 | |67 | |70 | |00 | | |
|40 | |45 | | | | | | | |60 | |65 | | | | | | | |67 | |68 | | | | | | | |90 | |92 | | | | | | |- Inserir 48, 50:

|60 | |67 | |70 | |00 | | |
|40 | |45 | |48 | |50 | | | |60 | |65 | | | | | | | |67 | |68 | | | | | | | |90 | |92 | | | | | | |-...
tracking img