Á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.
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ó.
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.
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.
A estrutura de um nó de uma Árvore T pode ser representado pelo desenho abaixo onde:
typedef arvore_T arvore_T, *arvore;
typedef int dado;
typedef struct celula celula, *no;
struct celula
{
dado conteudo;
no posterior;
};
struct arvore_T
{
no chave;
dado numerochaves;
dado indice;
arvore pai;
arvore esquerda;
arvore direita;
};
#define MAX() //MAX sendo o limite de chaves que pode conter em um nó da Árvore T
#define NC(T) ((T)-> numerochaves)
#define CHAVE(T) ((T)->conteudo)
#define POST(T) ((T)->posterior)
#define ESQUERDA(T) ((T)->esquerda)
#define DIREITA(T) ((T)->direita)
#define PAI(T) ((T)->pai)
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) |