[Powered by Google Translate] Como você representar todos os membros de sua família em um computador?
Nós poderíamos simplesmente usar uma lista,
mas não há uma hierarquia clara aqui.
>> Vamos dizer que nós estamos começando com sua bisavó, Alice.
Ela tem dois filhos, Bob
e seu avô, Charlie.
Charlie tem 3 filhos,
seu tio, Dave, sua tia, Eva, e seu pai, Fred.
Você é filho único de Fred.
>> Por que organizar seus familiares, desta forma
ser melhor do que a representação da lista simples?
Uma razão é a de que esta estrutura hierárquica,
chamado de "árvore", contém mais informações do que uma simples lista.
Nós sabemos que as relações familiares entre todos
apenas através do exame da árvore.
Além disso, ele pode acelerar
look-up de tempo tremenda, se os dados da árvore está classificada.
>> Não podemos tirar vantagem de que aqui, mas vamos ver um exemplo disso em breve.
Cada pessoa é representada por um nó na árvore.
Nós pode ter nós filho
bem como um nó pai.
Estes são os termos técnicos,
mesmo quando se usa árvores para coisas além de famílias.
Nó de Alice tem dois filhos e não dos pais,
enquanto nó de Charlie tem 3 filhos e uma mãe.
>> Um nó folha é aquele que não tem filhos
na borda externa da árvore.
O nó mais alto da árvore, o nó raiz,
não tem pai.
>> Uma árvore binária é um tipo específico de árvore,
em que cada nó tem, no máximo, 2 crianças.
Aqui é a estrutura de um nó de uma árvore binária em C.
Cada nó tem alguns dados associados
e dois ponteiros para outros nós.
>> Na nossa árvore de família,
os dados associados era o nome de cada pessoa.
Aqui é um int, que poderia ser qualquer coisa.
Como se vê,
uma árvore binária não seria uma boa representação para uma família,
já que as pessoas muitas vezes têm mais de dois filhos.
>> Uma árvore de busca binária
é um tipo especial de árvore binária ordenada
que nos permite olhar para os valores rapidamente.
Você deve ter notado
que cada nó abaixo da raiz de uma árvore
é a raiz de outra árvore, chamado de "sub".
Aqui, a raiz da árvore é de 6,
e seu filho, 2, é a raiz de uma subárvore.
>> Em uma árvore de pesquisa binária
todos os valores de um nó é subárvore direita
são maiores do que o valor do nó. Aqui: 6.
Bem, os valores na subárvore esquerda de um nó
são menos do que o valor do nó.
Se precisamos de lidar com valores duplicados,
nós podemos mudar ou daqueles a uma desigualdade solto,
significa valores idênticos podem cair ou à esquerda ou à direita,
desde que sejam consistentes sobre ele todo.
Esta árvore é uma árvore de busca binária
porque segue essas regras.
>> Isto é como ficaria se transformou todos os nós em estruturas C.
Observe que, se uma criança está em falta,
o ponteiro é nulo.
Como podemos verificar, para ver se é 7 na árvore?
Começamos na raiz.
Sete é superior a 6, por isso, se ele está na árvore, ela deve ser para a direita.
Em seguida, é inferior a 8, de modo que deve ser deixado.
Aqui, nós descobrimos 7.
Agora, vamos verificar para 5.
Cinco é inferior a 6, por isso deve ser para a esquerda.
Cinco é maior do que 2,
então deve estar certo,
e também é maior do que 4, então deve estar certo de novo.
No entanto, não há nenhuma criança aqui.
O ponteiro é nulo.
Isto significa que, 5 não é na nossa árvore.
>> Podemos procurar a árvore binária com o seguinte código:
Em cada nó, vamos verificar para ver se temos encontrado
o valor que estamos procurando.
Se não encontrá-lo, vamos determinar se ele deve ser
sobre a esquerda ou direita e verificar que subárvore.
Este ciclo vai continuar a descer da árvore
até que não haja nenhum nó filho de ambos a esquerda ou para a direita.
>> Lembre-se que 5 não estava na árvore.
Como podemos inseri-lo?
O processo é semelhante para busca.
Repetimos a árvore a partir de 6 de
esquerda para a 2,
direita a 4,
e novamente à direita, mas 4 não tem filho deste lado.
Esta será a nova posição para 5,
e ele vai começar sem filhos.
>> O quão rápido são operações em uma árvore de busca binária?
Recordar que Bigohnotation procura fornecer um limite superior.
No pior dos casos,
nossa árvore poderia ser simplesmente uma lista encadeada
o que significa que a inserção, exclusão e pesquisa
pode levar tempo proporcional ao número de nós na árvore.
Este é O (n).
>> Por exemplo, o seguinte é uma árvore de pesquisa binária válido.
No entanto, se tentar encontrar 9,
temos que atravessam cada nó.
Ele não é melhor que uma lista ligada.
Idealmente, gostaríamos cada nó
da nossa árvore de busca binária de ter 2 filhos.
Desta forma, a inserção, exclusão e pesquisa
levaria, na pior das hipóteses, O (log n).
A árvore de antes poderia ser mais equilibrado,
como este.
Agora, olhando-se qualquer valor tem, no máximo, 3 passos.
Esta árvore é equilibrada,
o que significa que é, tem uma profundidade mínima
em relação ao número de nós.
>> À procura de um valor em uma árvore balanceada de busca binária
é semelhante ao de busca binária em um array ordenado.
Na verdade, se nós não precisamos inserir ou excluir itens,
eles se comportam exatamente da mesma maneira.
No entanto, a estrutura da árvore é melhor
para inserções e deleções de manipulação
>> Meu nome é Bannus Van der Kloot.
Este é CS50.