Introdução às Árvores
Treeé uma estrutura discreta que representa relacionamentos hierárquicos entre elementos ou nós individuais. Uma árvore na qual um pai não tem mais do que dois filhos é chamada de árvore binária.
Árvore e suas propriedades
Definition- Uma árvore é um gráfico não direcionado acíclico conectado. Existe um caminho único entre cada par de vértices em $ G $. Uma árvore com N número de vértices contém $ (N-1) $ número de arestas. O vértice de 0 grau é denominado raiz da árvore. O vértice que é de 1 grau é chamado de nó folha da árvore e o grau de um nó interno é pelo menos 2.
Example - O seguinte é um exemplo de uma árvore -
Centros e Bi-Centros de uma Árvore
O centro de uma árvore é um vértice com excentricidade mínima. A excentricidade de um vértice $ X $ em uma árvore $ G $ é a distância máxima entre o vértice $ X $ e qualquer outro vértice da árvore. A excentricidade máxima é o diâmetro da árvore. Se uma árvore tiver apenas um centro, ela é chamada de Árvore Central e se uma árvore tiver apenas mais de um centro, ela é chamada de Árvore Bi-central. Cada árvore é central ou bicentral.
Algoritmo para encontrar centros e bicentros de uma árvore
Step 1 - Remova todos os vértices de grau 1 da árvore dada e também remova suas arestas incidentes.
Step 2- Repita a etapa 1 até que seja deixado um único vértice ou dois vértices unidos por uma aresta. Se um único vértice for deixado, então ele é o centro da árvore e se dois vértices unidos por uma aresta forem deixados, então ele é o bicentro da árvore.
Problem 1
Descubra o centro / bi-centro da seguinte árvore -
Solution
Em primeiro lugar, iremos remover todos os vértices de grau 1 e também remover suas arestas incidentes e obter a seguinte árvore -
Novamente, removeremos todos os vértices de grau 1 e também removeremos suas arestas incidentes e obteremos a seguinte árvore -
Finalmente temos um único vértice 'c' e paramos o algoritmo. Como há um único vértice, esta árvore possui um centro 'c' e a árvore é uma árvore central.
Problem 2
Descubra o centro / bi-centro da seguinte árvore -
Solution
Em primeiro lugar, iremos remover todos os vértices de grau 1 e também remover suas arestas incidentes e obter a seguinte árvore -
Novamente, removeremos todos os vértices de grau 1 e também removeremos suas arestas incidentes e obteremos a seguinte árvore -
Finalmente, temos dois vértices 'c' e 'd' restantes, portanto, paramos o algoritmo. Como dois vértices unidos por uma aresta são deixados, esta árvore tem 'cd' bicentral e a árvore é bicentral.
Árvores Rotuladas
Definition- Uma árvore rotulada é uma árvore cujos vértices são atribuídos a números únicos de 1 a n. Podemos contar essas árvores para pequenos valores de n manualmente, de modo a conjeturar uma fórmula geral. O número de árvores rotuladas de n número de vértices é $ n ^ {n-2} $. Duas árvores rotuladas são isomórficas se seus gráficos são isomórficos e os pontos correspondentes das duas árvores têm os mesmos rótulos.
Exemplo
Árvores não rotuladas
Definition- Uma árvore sem rótulo é uma árvore cujos vértices não são atribuídos a nenhum número. O número de árvores rotuladas de n número de vértices é $ \ frac {(2n)!} {(N + 1)! N! } $ ( enésimo número catalão)
Exemplo
Árvore Enraizada
Uma árvore com raiz $ G $ é um grafo acíclico conectado com um nó especial que é chamado de raiz da árvore e toda aresta direta ou indiretamente se origina da raiz. Uma árvore com raiz ordenada é uma árvore com raiz onde os filhos de cada vértice interno são ordenados. Se cada vértice interno de uma árvore enraizada não tiver mais do que m filhos, é chamado de árvore m-ária. Se cada vértice interno de uma árvore enraizada tiver exatamente m filhos, é chamado de árvore m-ária completa. Se $ m = 2 $, a árvore com raiz é chamada de árvore binária.
Árvore de pesquisa binária
A árvore de pesquisa binária é uma árvore binária que satisfaz a seguinte propriedade -
- $ X $ na subárvore esquerda do vértice $ V, Valor (X) \ le Valor (V) $
- $ Y $ na subárvore direita do vértice $ V, Valor (Y) \ Valor ge (V) $
Assim, o valor de todos os vértices da subárvore esquerda de um nó interno $ V $ são menores ou iguais a $ V $ e o valor de todos os vértices da subárvore direita do nó interno $ V $ são maiores ou iguais a $ V $. O número de links do nó raiz ao nó mais profundo é a altura da árvore de pesquisa binária.
Exemplo
Algoritmo para procurar uma chave no BST
BST_Search(x, k)
if ( x = NIL or k = Value[x] )
return x;
if ( k < Value[x])
return BST_Search (left[x], k);
else
return BST_Search (right[x], k)Complexidade da árvore de pesquisa binária
| Caso Médio | Pior caso | |
|---|---|---|
| Complexidade do Espaço | Em) | Em) |
| Complexidade de pesquisa | O (log n) | Em) |
| Complexidade de Inserção | O (log n) | Em) |
| Complexidade de exclusão | O (log n) | Em) |