Á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 processador2 .


Wikitext.svg
Este artigo ou seção precisa ser wikificado (desde outubro de 2012).
Por favor ajude a formatar este artigo de acordo com as diretrizes estabelecidas no livro de estilo.

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:

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:

Ela possui um melhor desempenho em busca do que a arvore B já que não precisa visitar tantas chaves como na arvore 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:

Possui a inserção e remoção ligeiramente mais rápida do que dá arvore B pois sua busca é bem mais rápida que a dá arvore B, embora sua atualização (balanceamento) seja mais complexa e custosa.
A arvore AVL tem o pior desempenho de inserção e remoção pois a cada operação tem que atualizar índices de balanceamento e se necessário realizar rotações.




Estrutura de um nó de uma Árvore T pode ser representado pelo desenho a baixo onde:


Nó ÁRVORE T
Nó arvore T prara wikipedia.jpg

PONTEIROS:

DADO CHAVE(T) 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.

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 a esquerda do nó. Se não houver subárvore ele aponta para NULL.

DIREITA(T) é um ponteiro que aponta para a subárvore a 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 arvores AVL, estando balanceadas possuem valor 1, 0 ou -1 qualquer valor diferente indica que a arvore precisa ser balanceada.


A ESTRUTURA IMPLEMENTADA EM C:















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)


PERCURSO VISITA NÓ:

PERCURSO ÁRVORE T


ORDEM arvore T wikipedia.jpg




IMAGINANDO A VISITA(T)


PREORDEM(T):

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


EMORDEM(T):

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


POSORDEM(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



TRABALHO ESTRUTURA DE DADOS I, UFES - CEUNES 2012


1


2

Ícone de esboço Este artigo sobre Software é um esboço. Você pode ajudar a Wikipédia expandindo-o.


Erro de citação: existem marcas <ref>, mas falta adicionar a predefinição {{referências}} no final da página