10-29 Árvore Binária de Busca

Prévia do material em texto

Árvore Binária de Busca. 
 
A Altura(h) mínima de uma árvore completa é (log n)+1 onde “n” representa a quantidade de nós. 
 
complexidade - ​O​​ (log n) 
 - 
u 
onde “​O​​” (​big o​​) significa “o pior caso”, ou seja, a 
maior quantidade de tentativas para encontrar o 
que se procura. 
 
 
h = [log n]+1 
 
Altura Máxima de uma Árvore Zigue-zague(Todo nó tem apenas 1 filho) 
 
Complexidade - ​O​​(n) 
 
 
Exercício: Dado o conjunto de chaves {1,2,3,4,5,6,7} apresente 3 sequências distintas que: 
a) Produza uma ABB (Árvore Binária de Busca ) com altura máxima 
1) 1,2,3,4,5,6,7 
2) 6,7,5,4,3,2,1) 
3) 1,2,3,4,5,7,6 
 
 
b) Produza uma ABB (Árvore Binária de Busca ) com altura mínima 
 
4,2,6,1,3,5,7 
4,6,2,1,3,5,7 
4,2,6,7,1,5,3 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
05 de novembro 
remover da ABB (Árvore Binária de Busca) 
 
1ª situação:​​ Se ​“X”​​ é uma folha, basta remover a folha ​“X”​​ ​ }O(log n) 
 
2ª situação:​​ Se ​“X”​​ possui 1 filho, basta apontar o ​“pai de X”​​ para o ​“filho de X”​​.​ }O(log n) 
 
3ª situação​​: Substitui o ​“rótulo de X”​​ pelo nó mais à direita da subárvore esquerda ; ou pelo nó mais à 
esquerda da subárvore direita. Em seguida, remove o elemento ​“X” ​​como no caso 1 ou caso 2 
 
. 
 
 
ÁRVORES AVL 
 
Dado um nó ​“X”​​ em uma árvore AVL. 
O nó ​“X”​​ é dito balanceado se a diferença entre as alturas de suas subárvores direita e esquerda 
é ​menor ou igual a 1​​. 
 
|h esq(x) - h dir(x)| <= 1 
 
Se todos os nós de uma árvore são balanceados a árvore é dita balanceada. 
 
 
 
 
 
 
 
 
 
_____________________________________________________________________________ 
12/11/2018 
 
 
 
 
Exercício 1 
 
Construa uma árvore AVL com a sequência dada S{ 20,30,40,25,10,29} 
Apresente passo a passo a construção 
 
 
 
Árvores ​Rubro-Negras​​ OU ​Graduadas 
Propriedades: 
1. Todo nó externo é negro. 
2. A raiz é negra. 
3. Pai de nó rubro é negro. 
4. Todo caminho de um nó qualquer até uma folha possui a mesma quantidade de nós negros. 
 
 
Ex.: 
 
 
 
Conceito: Um lado da árvore pode ter no máximo o dobro do outro