• É conexa;
• Não possui ciclos;
• Tem apenas um caminho entre um nó e outro;
• Tem (n-1) arestas, sendo n o número de nós.
Como o próprio nome diz, a BST é uma árvore binária, ou seja, cada nó, além de ter seu valor, está ligado a outros dois nós (vamos chamá-los de filho à esquerda e filho à direita).
O primeiro nó a ser adicionado na árvore chama-se raiz.
Os nós sem filhos chamam-se folhas.
A única forma de percorrer a árvore é partindo da raiz.
VISUALIZAÇÃO DE UM NÓ:
struct no{
int val; no *left, *right;
no(){} no(int v){val = v, left = right = NULL;} }
A principal vantagem de se usar uma BST como estrutura ao invés de um array ou uma lista é que ela consegue achar mais rápido um elemento.
Numa lista, para achar um elemento, é preciso percorrer desde o início até esse elemento para saber onde ele está, e isso é O(n) no pior caso (elemento no fim da lista).
Já na BST, conseguimos encontrar esse elemento GERALMENTE em O(lg(n)).
Podemos representar uma BST assim:
struct BST{ no *root; BST(){root = NULL;} void add(int v){} void del(int n){} };
Analogamente, o ponteiro guarda onde está o nó que é a raiz da árvore.
Lembrando que quando mexemos com ponteiros, usamos -> ao invés de .
NULL equivale a 0, indicando que root aponta pra posição de memória 0, inicialmente.
INSERÇÃO
Seja n um nó, por definição:
• O valor do filho da esquerda de n é menor que o valor de n;
• O valor do filho da direita de n é maior que o valor de n;
Para inserir um nó e numa BST, seguimos o seguinte algoritmo:
(1) Se a raíz da árvore está vazia, modifique seu valor para e
(2) Caso contrário:
(2.1) se e for maior ou igual ao valor da raiz, repita (1) partindo de raiz.right
(2.1) senão, repita (1) partindo de raiz.left
Dessa forma, a árvore vai ser percorrida até que o local correto para inserir e seja encontrado. Se e for maior que o valor da raiz, ele vai pra direita, e se for menor, pra esquerda.
Exemplo: Inserções dos elementos 10, 5, 15, 8 e 18 nessa ordem:
struct BST{ no *root; BST(){root = NULL;} void add(int v){ root = add(v, root); } no *add(int v, no *n){ if(n == NULL) return new no(v); if(v >= n->val) n->right = add(v, n->right); else n->left = add(v, n->left); return n; } };
O que esse método faz é:
• Se n é nulo (ou seja, é a posição 0 da memória), aloca um novo nó na memória (usando o new, que já retorna o endereço do novo nó);
• Senão, caso v seja maior ou igual ao valor de n, o ponteiro de n para o filho da direita é atualizado, recebendo o "novo" endereço;
• Da mesma forma quando o valor é menor, com o ponteiro para o filho da esquerda.
Na verdade, o endereço só vai mudar quando n for NULL.
Suponha que adicionemos 10 a uma árvore de raiz 5. Os ponteiros dessa árvore até então são NULL.
Quando o add perguntar, a raiz não é NULL, então ele vai comparar para saber pra onde o 10 vai, e vai descobrir que é para a direita, então o ponteiro para a direita vai ser atualizado com o endereço de um novo nó de valor 10 que a próxima chamada ao método vai retornar.
Se fosse adicionado 20 a essa árvore, o ponteiro para a direita do 5 não iria mudar, ia continuar apontando para o 10, mas o do 10, que era NULL, ia apontar para um novo nó de valor 20.
Podemos perceber que, se adicionarmos elementos em ordem crescente, a árvore vai ficar no formato de uma lista, fazendo com que a inserção se torne O(n) no pior caso.
Complexidade da Inserção: O(n)
BUSCA
A busca é bem parecida com a inserção, percorrendo a ávore para a direita e esquerda de acordo com o valor recebido.
Ela termina quando acha o valor (retornando seu endereço) ou quando o nó sendo visto tem endereço NULL.struct BST{ no *root; BST(){root = NULL;} no *busca(int v){
return busca(v, root);
} no *busca(int v, no *n){ if(n == NULL) return NULL; if(n->val == v) return n; else if(v > n->val) return busca(v, n->right); return busca(v, n->left); } };
Pelo mesmo motivo da inserção, a busca também é O(n)
Complexidade da Busca: O(n)
REMOÇÃO
Quando vamos remover um elemento, temos que levar em conta 3 casos:
1 - O nó a ser removido é uma folha;
2 - O nó a ser removido tem um filho;
3 - O nó a ser removido tem dois filhos;
Para remover um valor v numa BST, seguimos o algoritmo:
(1) Busca nó n de valor v na árvore;
(2) Caso n seja folha, apenas remove.
(3) Caso n tenha apenas um filho, troca n por seu filho.
(4) Caso n tenha dois filhos, substitui n por seu sucessor.
O sucessor de n é o menor elemento da árvore cuja raiz é o filho à direita de n, ou seja, o elemento mais à esquerda dessa árvore, pois ele é menor que todos os outros elementos da árvore e portanto, quando for trocado por n, todos à sua direita vão continuar sendo maiores que ele.
struct BST{ no *root; BST(){root = NULL;} void del(int v){ root = del(v, root); } no *del(int v, no *n){ if(n == NULL) return NULL; if(v > n->val) n->right = del(v, n->right); else if(v < n->val ) n->left = del(v, n->left); else{ if(n->left == NULL){ //nenhum filho if(n->right == NULL) {delete n; n = NULL;} //so filho da direita else {no *aux = n; n = n->right; delete aux;} } //so filho da esquerda else if(n->right == NULL){ no *aux = n; n = n->left; delete aux; } //dois filhos else{ n->val = menor(n->right); n->right = del(n->val, n->right); } return n; } } int menor(no *n){ if(n->left == NULL) return n->val; return menor(n->left); } };
delete n limpa o espaço correspondente ao nó n na memória.
Também percorre toda a árvore no pior caso (em forma de lista).
Complexidade da Remoção: O(n)
EXTRAS
Calculando altura da árvore
A altura de uma árvore é equivalente à profundidade de seu ramo mais denso, ou seja, é o máximo entre as alturas de todos os seus ramos.
struct BST{ no *root; BST(){root = NULL;} int altura(no *n){ if(n == NULL) return -1; return 1 + max(altura(n->left), altura(n->right)); } };
Caso a árvore esteja vazia, retorna -1.
Se só tiver a raiz, retorna 0.
Complexidade O(n) no pior caso.
Percorrer todos os elementos da árvore
Existem três maneiras de se percorrer uma árvore: Pré-Ordem, Ordem e Pós-Ordem
O que muda entre eles é a ordem que os nós são visitados.
Eis a maneira em Ordem:
Eis a maneira em Ordem:
struct BST{ no *root; BST(){root = NULL;} void ordem(no *n){ if(n != NULL){ ordem(n->left); printf("%d ", n->val); ordem(n->right); } } };
Dessa maneira, sempre que se entra num nó, vão ser printados todos nós menor que ele, depois ele, e a seguir todos os maiores que ele, de forma que o resultado vai ser em ordem crescente.
Pré-Ordem chama o print antes de chamar os dois ordem, Pós-Ordem, depois.
Complexidade O(n) no pior caso.
------------------------------------------------------------------------------------------------------------
Exemplos de árvores balanceadas: AVL, Red-Black Tree.
Nenhum comentário:
Postar um comentário