Árvore T

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Árvore T é em ciência da computação uma estrutura de dados empregada principalmente em bancos de dados em memória principal e alguns bancos de dados convencionais como índice. É uma estrutura baseada na árvore AVL, herdando dela a propriedade de ser uma árvore binária e auto-balanceada e possibilitando economia no uso de memória.[1] Além disso é uma estrutura de índice que toma vantagem das características próprias da memória principal, como faz a árvore B+ mas para acesso a disco.

Apesar das vantagens demonstradas, a árvore T pode ter problemas de desempenho em hardware moderno por não aproveitar adequadamente o espaço da memória cache do processador[2]. A árvore T é uma árvore binária balanceada que busca obter benefícios de desempenho de estruturas tais como árvores AVL e árvores B.

Balanceamento[editar | editar código-fonte]

O balanceamento é feito usando rotações semelhantes aos da árvore AVL, no entanto ele é feito com muito menos frequência do que em uma árvore AVL. Devido a possibilidade de movimentação de dados dentro do nó.

Busca[editar | editar código-fonte]

Ela possui um melhor desempenho em busca do que a árvore B já que não precisa visitar tantas chaves como na árvore B, no entanto seu desempenho é um pouco pior que a arvore AVL que visita apenas uma chave por nó e corta caminhos pela busca binária.

Inserção e Remoção[editar | editar código-fonte]

Possui a inserção e remoção ligeiramente mais rápida do que a árvore B pois sua busca é bem mais rápida que a desta árvore, embora o seu balanceamento seja mais complexo e custoso. A árvore AVL tem o pior desempenho de inserção e remoção pois a cada operação tem que atualizar os índices de balanceamento e se necessário realizar rotações.

Construção[editar | editar código-fonte]

Representação de um nó em uma árvore T

A estrutura de um nó de uma Árvore T pode ser representado pelo desenho abaixo onde:

  • Ponteiros:
    • Chaves: são os dados (valores) armazenados no nó. O número máximo de chaves que pode conter num nó é definido por um valor MAX. A chave mais a ESQUERDA do nó possui o menor valor nele armazenado, os valores vão crescendo a medida que vamos para DIREITA. Dispostos como numa lista ordenada.
    • Ponteiro Pai(T): é um ponteiro que aponta para nó pai logo acima. Se o nó for raiz, aponta para NULL.
    • Esquerda(T): é um ponteiro que aponta para a subárvore à esquerda do nó. Se não houver subárvore ele aponta para NULL.
    • Direita(T): é um ponteiro que aponta para a subárvore à direita do nó. Se não houver subárvore ele aponta para NULL.
    • Post(T) é o ponteiro que aponta para a próxima chave que armazena um valor maior que o da chave anterior.
    • Ant(T) é o ponteiro que aponta para a chave antecessora que armazena um valor menor que o da chave atual.
  • Controle:
    • dado N_CHAVE, campo que armazena o número de chaves contidos em um nó, que deve sempre ser menor que MAX.
    • dado INDICE, campo que armazena o índice de balanceamento da árvore assim como nas árvores AVL, estando balanceadas possuem valor 1, 0 ou -1 qualquer valor diferente indica que a árvore precisa ser balanceada.

Implementação em C[editar | editar código-fonte]

 1 typedef arvore_T arvore_T, *arvore;
 2 
 3 typedef int dado;
 4 
 5 typedef struct celula celula, *no;
 6 
 7 
 8 struct celula
 9 {
10 
11 	dado conteudo;
12 
13 	no posterior;
14 };
15 
16 struct arvore_T
17 
18 {
19 
20 	no chave;
21 
22 	dado numerochaves;
23 
24 	dado indice;
25 
26 arvore pai;
27 
28 	arvore esquerda;
29 
30 	arvore direita;
31 
32 };
33 
34 #define MAX() //MAX sendo o limite de chaves que pode conter em um nó da Árvore T
35 
36 #define NC(T)             ((T)-> numerochaves)
37 
38 #define CHAVE(T)          ((T)->conteudo)
39 
40 #define POST(T)           ((T)->posterior)
41 
42 #define ESQUERDA(T)       ((T)->esquerda)
43 
44 #define DIREITA(T)        ((T)->direita)
45 
46 #define PAI(T)            ((T)->pai)

Percurso de travessia na árvore[editar | editar código-fonte]

Percurso de visita na árvore T

Pré-ordem:

(29 35 37) (10 12 15) (1 5 7) (16 20 23) (60 65 66) (40 41 58) (67 72 80)

Em-ordem(T):

(1 5 7) (10 12 15) (16 20 23) (29 35 37) (40 41 58) (60 65 66)

Pós-ordem(T):

(1 5 7) (16 20 23) (10 12 15) (40 41 58) (67 72 80) (60 65 66) (29 35 37)

Referências

  1. Artigo A Study of Index Structures for Main Memory Database Management Systems de Tobin J. Lehman e Michael J. Carey, 1986
  2. Artigo Cache Conscious Indexing for Decision-Support in Main Memory de Jun Rao e Kenneth A. Ross, 1999
Ícone de esboço Este artigo sobre software é um esboço. Você pode ajudar a Wikipédia expandindo-o.