Conceito de árvores em Estrutura de Dados

11 dezembro 2010



Bom, não vou falar sobre árvores daquelas que se plantam e elas crescem e aproveitando esse tempo de fim-de-ano, não vou falar sobre pinheirinhos de Natal. Estou escrevendo este Post porque preciso estudar para minha prova de exame na Faculdade, (pois é, eu fiquei em exame L). O título ficou meio tosco também, comentem o que acharam... (Mudado o título que era antes "Conceito de Árvores"). Bom então sobre o que eu vou falar? Sobre árvores em Estrutura de Dados.
Então vamos entender um pouco sobre essas árvores. Basicamente, esse nome “árvores” teve origem por causa da estrutura física de um objeto que se assemelha muito com uma árvore, em que suas ramificações tende a se convergir a uma raiz. Espero que eu consiga explicar sobre este assunto.


Nós ou Nodos: São os itens guardados na árvore.
Raiz: É o primeiro nó e o nó principal da árvore. Há somente um nó em cada árvore, conforme mostra a figura abaixo:

Pais: São nós que vem antes de outros nós;
Filhos: São os nós que vem depois dos nós pais. Um filho precisa de um pai para ser filho, entendeu ? =P
Folhas: São nós que não tem filhos. Eles são os últimos das árvores. Ex.: Um caminho como C:\XXX\YYY\ZZZ.doc, corresponde ao caminho da raiz ao nó folha ZZZ.doc.
Um exemplo está na árvore abaixo:

Grau de um nó: Números de filhos de cada nó;
Nível de um nó: Por definição, é zero para a raiz, e, para os demais nós, é o número de “linhas” que ligam o nó à raiz;
Altura de árvore: É o nível mais alto da árvore;
Floresta: Conjunto de árvores disjuntas;
Galhos: Quaisquer nodos que não são raiz e nem folhas de árvore;
Aresta: É a linha que liga dois nodos da árvore;
Caminho: Diz-se que existe um caminho entre dois nodos A e B de uma árvore, se a partir do nodo A pode-se chegar ao nodo B percorrendo-se as arestas que ligam os nodos intermediários entre A e B.


Abaixo vou falar sobre os tipos de árvores:
Árvores Binárias e de Busca:
Essa árvore se caracteriza por não ter elemento nenhum ou tem um elemento distinto denominado raiz com dois ponteiros  para uma sub-árvore a direita e outra para a esquerda. Sua definição é que seus graus estão entre 0, 1 e 2. Cada nó só pode ter dois filhos



 As três maneiras mais usuais para percorrer os nós são:

Caminhamento Pré-fixado
Visita a raiz
Percorre a sub-árvore da esquerda
Percorre a sub-árvore da direita

Caminhamento In-fixado
Percorre a sub-árvore da esquerda
Visita a raiz
Percorre a sub-árvore da direita

Caminhamento Pós-fixado
Percorre a sub-árvore da esquerda
Percorre a sub-árvore da direita
Visita à raiz

Arvores AVL:
São árvores balanceadas pela altura. É uma árvore binária auto-balanceada. Uma árvore AVL é dita balanceada quando, para cada nó da árvore, a diferença entre as alturas das suas sub-árvores (direita e esquerda) não é maior do que um. Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de inserção e remoção de elementos. Para definir o balanceamento é utilizado um fator específico para nós.
O fator de balanceamento de um nó é dado pelo seu peso em relação a sua sub-árvore. Um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator. Um nó com fator de balanceamento diferente dos citados é considerado uma árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.



Arvores B e B+
Uma árvore B de ordem "m" (máximo de filhos para cada nó) é uma árvore que atende as seguintes propriedades:
  1. Cada nó tem no máximo "m" filhos
  2. Cada nó (exceto a raíz e as folhas) tem pelo menos "m/2" filhos
  3. A raiz tem pelo menos dois filhos se a mesma não for uma folha
  4. Todas as folhas aparecem no mesmo nível e carregam informação
  5. Um nó não-folha com "k" filhos deve ter k-1 chaves
Uma árvore B+ é uma variação da árvore B. Numa árvore-B+, contrastando com uma árvore-B, todos os dados são gravados nas folhas. Os nodos internos contêm apenas chaves e apontadores da árvore. Todas as folhas estão no mesmo nível mais baixo. Os nodos das folhas também estão ligados entre si como uma lista de ligações para efectuar consultas facilmente.


Arvores Red-Black.
Características
As árvores Red-Black foram inventadas em 1972, por Bayer sob o nome B-árvores binárias simétricas. As árvores red-black são também árvores binárias de busca balanceadas que tem algoritmos de inserção e remoção de complexidade logarítmica no número de nós. Porém, elas são geralmente mais usadas, pois tem implementações mais eficientes.

Em uma árvore red-black o equilíbrio é conseguido durante a inserção. Quando um item está sendo inserido a rotina de inserção verifica que certas características da árvore não sejam violadas. Se forem, ela toma a atitude de correção e reestruturando da árvore, conforme o necessário. Mantendo estas características, a árvore fica equilibrada.
A principal característica das árvores red-black é que seus nós são coloridos (negros ou vermelhos) e durante os processo de inserção e inclusão as regras são seguidas para que se preserve o ajuste destas cores.


Propriedades
1. Cada nó tem uma cor que é vermelha ou negro. Por convenção, uma árvore não vazia (ou sub-árvore) tem a cor de sua raiz e uma árvore vazia é negra.
2. A raiz é negra.
3. Qualquer caminho da raiz até uma sub-árvore vazia tem um número igual de nós negros.
4. As sub-árvores de um nó vermelho são negros.

Uma propriedade óbvia resultando da quarta condição é que num caminho da raiz até uma sub-árvore vazia não pode haver dois nós vermelhos consecutivos.



Por enquanto é isso. Isto foi um conceito básico de árvores. Comente, se estiver errado alguma coisa aqui encima, corrija-me por favor... E desculpe meus erros gramaticais! Gostou? Comente também!!! =D

7 comentários :

{ Bruno Barbosa } at: 11 dezembro, 2010 22:22 disse...

Olá Guilherme,

Parabéns pelo artigo e pelo blog, realmente está muito bom!

Quanto ao título do artigo, acredito que se você colocar do que se trata realmente o artigo, você vai conseguir chamar mais atenção dos leitores e ganhar um rankeamento melhor no Google... #ficadica

Até mais.
Bruno Barbosa

{ Guilherme Pedroso } at: 11 dezembro, 2010 22:59 disse...

Vlw Bruno. Obrigado por comentar aqui. Eu acompanho o Algoritmizando há um bom tempo e gostei da idéia de vocês.
Quanto ao nome, vou deixar por enquanto como está... Depois eu vou mudar para um que condiz melhor o artigo.
Obrigado.

{ Unknown } at: 25 março, 2011 21:12 disse...

Mto bom. Este também é introduzido para os conceitos na área de Tecnologia da Informação(T.I.)

{ Léo } at: 29 novembro, 2011 12:53 disse...

cara, essa primeira árvore não esta errada ? pois a raiz é 2 e o numero que vai pra esquerda tinha que ser menor, e na sua árvore está aparecendo o 7 que é maior que o 2, no caso o 7 iria para a direita.
obs: estou aprendendo essa materia agr, e não estou querendo te corrigir, na verdade é mais uma duvida minha mesmo. se puder responder,fico feliz! abrss

{ Léo } at: 29 novembro, 2011 12:57 disse...

encontrei outro problema, o nó folha 4 ele é maio que a raiz então foi para a direita, porém o proximo nó depois do raiz é o nó 5, e 4 é menor que 5, então ele deveria ir para a esquerda. estou certo ?
desculpa ai cara, é pq tenho uma prova hj e estou com algumas duvidas.

{ Léo } at: 29 novembro, 2011 13:02 disse...

caara, mais um! percebi também que o numero 2 esta se repetindo na árvore, pelo o que eu entendo "não pode"!
e outra, indo pra esquerda do nó raiz, se encontra o nó 7, e logo abaixo encontra-se o nó 6, la na arvore ele esta indo para a direito, mais pelo que eu saiba os numeros menores vão indo para esquerda!
por favor, s eeu estiver errado me responda e me corrija" agradeço desde já ;D

{ Guilherme Pedroso } at: 11 dezembro, 2011 12:24 disse...

Corrigido =D