[Powered by Google Translate] [Pesquisa Binário] [Patrick Schmid - Harvard University] [Esta é CS50. - CS50.TV] 

Se eu lhe dei uma lista de nomes de personagens da Disney em ordem alfabética e pediu-lhe para encontrar o Mickey Mouse, como é que você vai fazer sobre isso? Uma maneira óbvia seria a de examinar a lista desde o início e verificar cada nome para ver se é Mickey. Mas quando você lê Aladdin, Alice, Ariel, e assim por diante, você vai logo perceber que a partir da frente da lista não foi uma boa idéia. Ok, talvez você deve começar a trabalhar para trás a partir do final da lista. Agora você ler Tarzan, Stitch, Branca de Neve, e assim por diante. Ainda assim, esta não parece ser a melhor maneira de ir sobre ele. 

Bem, outra maneira que você pode fazer sobre isso é para tentar diminuir a lista de nomes que você tem que olhar. Como você sabe que eles estão em ordem alfabética, você pode apenas olhar para os nomes no meio da lista e verifique se o Mickey Mouse é antes ou depois deste nome. Olhando para o último nome na segunda coluna você perceberia que a M para Mickey vem depois J para Jasmine, assim que você simplesmente ignorar a primeira metade da lista. Então você provavelmente olhar para o topo da última coluna e ver que ele começa com Rapunzel. Mickey vem antes de Rapunzel, parece que podemos ignorar a última coluna também. Continuando a estratégia de busca, você verá rapidamente que Mickey está na primeira metade do restante lista de nomes e, finalmente, encontrar Mickey escondido entre Merlin e Minnie. 

O que você fez foi basicamente busca binária. Como este nome indica, ele executa sua estratégia de busca em questão binário. O que isso significa? Bem, dada uma lista de itens classificados, o algoritmo de busca binária faz uma decisão binária - para a esquerda ou para a direita, maior ou menor do que, por ordem alfabética, antes ou depois - em cada ponto. Agora que temos um nome que vai junto com este algoritmo de busca, Vejamos outro exemplo, mas desta vez com uma lista de números ordenados. Dizer que estamos olhando para o número 144 na lista de números ordenados. Assim como antes, encontramos o número que está no meio - que neste caso é de 13 - 144 para ver se é maior do que ou menor do que 13. Uma vez que é claramente maior do que 13, podemos ignorar tudo o que é de 13 ou menos e nos concentrar apenas na metade restante. Uma vez que agora têm um número par de itens à esquerda, nós simplesmente escolher um número que está perto da média. Neste caso, nós escolhemos 55. Nós poderíamos ter facilmente escolhidos 89. Okay. Mais uma vez, 144 é maior que 55, portanto, vá para a direita. Felizmente para nós, o número do meio próximo é 144, o que estamos procurando. Portanto, a fim de encontrar 144 usando pesquisa binária, somos capazes de encontrá-lo em apenas 3 passos. Se tivéssemos usado busca linear aqui, teria nos levado 12 passos. Por uma questão de facto, uma vez que este método de pesquisa metades do número de itens tem que olhar a cada passo, ele vai encontrar o item que está à procura de em sobre o logaritmo do número de itens na lista. Agora que nós vimos dois exemplos, vamos dar uma olhada um pseudocódigo para uma função recursiva que implementa busca binária. Começando pelo topo, vemos que temos de encontrar uma função que recebe 4 argumentos: chave, matriz min, e max. A chave é o número que nós estamos procurando, de forma 144 no exemplo anterior. Matriz é a lista de números que estamos procurando. Mínimo e máximo são os índices das posições mínimas e máximas que atualmente estamos olhando. Assim, quando se iniciar, min será zero e max será o índice máximo da matriz. Como se restringir a pesquisa para baixo, vamos atualizar min e max para ser apenas a faixa que ainda estamos olhando para dentro 

Vamos pular para a parte interessante em primeiro lugar. A primeira coisa que fazemos é encontrar o ponto médio, o índice que está a meio caminho entre o mínimo eo máximo da matriz que ainda estamos considerando. Então, olhamos para o valor da matriz em que a localização do ponto médio e ver se o número que estamos procurando é menor do que a chave. Se o número em que a posição é menos, então isso significa que a chave é maior do que todos os números à esquerda dessa posição. Assim, podemos chamar a função de busca binária, novamente, mas desta vez, atualizando o min e max parâmetros de ler apenas a metade que é maior do que ou igual ao valor que acabamos de ver. Por outro lado, se a chave é menor do que o número actual no ponto médio da matriz, queremos ir para a esquerda e ignorar todos os números que são maiores. Mais uma vez, chamamos de busca binária, mas desta vez com a gama de min e max updated para incluir apenas a metade inferior. Se o valor no ponto médio actual na matriz não é nem maior do que ou menor do que a chave, então ele tem de ser igual à chave. Assim, podemos simplesmente retornar o índice ponto médio atual, e estamos a fazer. Finalmente, esta verificação aqui é para o caso em que o número não é, na verdade, na matriz de números que estamos procurando. Se o índice máximo do intervalo que estamos procurando é sempre menor que o mínimo, o que significa que nós fomos longe demais. Como o número não estava na matriz de entrada, nós retornar -1 para indicar que nada foi encontrado. 

Você deve ter notado que para este algoritmo para trabalhar, a lista de números tem que ser resolvido. Em outras palavras, só podemos encontrar 144 usando busca binária se todos os números são ordenados do menor para o maior. Se não fosse este o caso, não seria capaz de excluir metade dos números em cada etapa. Portanto, temos duas opções. Ou podemos ter uma lista não ordenada e classificá-lo antes de usar busca binária, ou podemos ter certeza de que a lista de números é classificada como adicionar números a ele. Assim, em vez de classificar apenas quando temos que procurar, Por que não manter a lista de classificados em todos os tempos? 

Uma forma de manter uma lista de números ordenados ao mesmo tempo, permitindo que uma para adicionar ou mudar os números da lista é usando algo chamado uma árvore de busca binária. Uma árvore de busca binária é uma estrutura de dados que tem três propriedades. Primeiro, a subárvore esquerda de qualquer nó contém apenas os valores que são menos de ou igual ao valor do nó. Em segundo lugar, o direito subárvore de um nó contém apenas valores que são maiores do que ou igual ao valor do nó. E, finalmente, tanto as subárvores esquerda e direita de todos os nós também são árvores de busca binária. Vejamos um exemplo com os mesmos números que usamos anteriormente. Para aqueles de vocês que nunca vi uma árvore de ciência da computação antes, deixe-me começar por lhe dizer que uma árvore de informática cresce para baixo. Sim, ao contrário de árvores que está acostumado, a raiz de uma árvore de informática é na parte superior, e as folhas estão na parte inferior. Cada caixa pequena é chamado um nó e os nós são conectados uns aos outros por arestas. Assim, a raiz dessa árvore é um valor do nó com o valor de 13, que tem dois nós filhos com os valores 5 e 34. Uma subárvore é a árvore que é formada só de olhar para uma subseção da árvore inteira. 

Por exemplo, a sub-árvore esquerda do nó 3 é a árvore criada pelos nós de 0, 1, e 2. Então, se voltar para as propriedades de uma árvore de busca binária, vemos que cada nó da árvore está em conformidade com todas as três propriedades, ou seja, subárvore esquerda contém apenas valores que são menos do que ou igual ao valor do nó; subárvore direita de todos os nós contém apenas valores que são maiores do que ou igual ao valor do nó, e subárvores esquerda e direita de todos os nós também são árvores de busca binária. Embora esta árvore parece diferente, esta é uma árvore de busca binária válido para o mesmo conjunto de números. Por uma questão de fato, há muitas formas possíveis que você pode criar uma árvore de busca binária válida a partir desses números. Bem, vamos voltar para o primeiro que criou. Então o que podemos fazer com essas árvores? Bem, podemos muito simplesmente encontrar os valores mínimo e máximo. Os valores mínimos podem ser encontrados por sempre vai para a esquerda até que não haja mais nenhum nó para visitar. Por outro lado, para encontrar o máximo simplesmente vai para baixo para a direita em cada momento. 

Encontrando qualquer outro número que não seja o mínimo ou máximo é tão fácil. Dizer que estamos procurando o número 89. Nós simplesmente verificar o valor de cada nó e vá para a esquerda ou direita, dependendo se o valor do nó é menor ou maior do que o que estamos procurando. Assim, a partir da raiz de 13, vemos que 89 é maior, e assim vamos para a direita. Em seguida, vemos o nó para 34, e, novamente, vá para a direita. 89 ainda é superior a 55, por isso continuamos indo para a direita. Nós então chegar a um nó com o valor de 144 e vá para a esquerda. Eis que, 89 é logo ali. 

Outra coisa que podemos fazer é imprimir todos os números através da realização de um percurso em inordem. Um percurso em inordem significa imprimir tudo na subárvore esquerda seguida de estampagem o próprio nó e depois seguiu imprimindo tudo na subárvore direita. Por exemplo, vamos tomar nossa árvore binária de busca favorito e imprimir os números em ordem de classificação. Começamos a raiz de 13, mas antes de imprimir 13 temos para imprimir tudo na subárvore esquerda. Então vamos para a 5. Nós ainda temos que ir mais fundo na árvore até encontrar o nó mais à esquerda, que é igual a zero. Após a impressão zero, voltar-se para o 1 e imprimir isso. Então vamos para a subárvore direita, que é 2, e imprimir isso. Agora que estamos a fazer com que subárvore podemos voltar-se para o 3 e imprimi-lo. Continuando para cima, nós imprimimos a 5 e depois o 8. Agora que já completou toda a subárvore esquerda, nós podemos imprimir a 13 e começar a trabalhar na subárvore direita. Nós desça para 34, mas antes de imprimir 34 temos de imprimir sua subárvore esquerda. Assim, imprimir 21; então nós começamos a imprimir 34 e visitar a sua subárvore direita. Desde 55 não tem subárvore esquerda, imprimi-lo e continuar a sua subárvore direita. 144 tem uma sub-árvore da esquerda, e portanto, imprimir a 89, seguindo-se a 144, e finalmente o nó mais à direita de 233. Lá você tem, todos os números são impressos em ordem da menor para a maior. 

Acrescentar algo para a árvore é relativamente indolor também. Tudo o que temos a fazer é ter certeza de que nós seguimos três binários propriedades da árvore de busca e insira o valor onde há espaço. Vamos dizer que deseja inserir o valor de 7. Desde 7 é menor que 13, vamos para a esquerda. Mas é maior do que 5, de modo que atravessam para a direita. Desde que é menos de 8 e 8 é um nó folha, nós adicionamos 7 para o filho esquerdo de 8. Voila! Nós adicionamos um número para nossa árvore de busca binária. 

Se pudermos acrescentar coisas, é melhor ser capaz de apagar as coisas tão bem. Infelizmente para nós, a exclusão é um pouco mais complicado - não muito, mas um pouco. Há três cenários diferentes que temos de considerar ao excluir elementos de árvores de busca binária. Em primeiro lugar, o caso mais fácil é a de que o elemento é um nó de folha. Neste caso, nós simplesmente excluí-lo e continuar com o nosso negócio. Dizer que queremos excluir o 7 que acabou de adicionar. Bem, nós simplesmente encontrá-lo, removê-lo, e é isso. O próximo caso é se o nó tem apenas um filho. Aqui podemos excluir o nó, mas primeiro temos que ter certeza para ligar a subárvore que é deixada sem pais para o pai do nó que acabou excluída. Dizer que queremos apagar 3 da nossa árvore. Tomamos o elemento filho desse nó e anexá-lo ao pai do nó. Neste caso, estamos agora a colocar o 1 ao 5. Isso funciona sem nenhum problema, pois sabemos, de acordo com a propriedade de árvore binária de busca, que tudo na subárvore esquerda de 3 era inferior a 5. Agora que 3 do sub é de tomar cuidado, podemos excluí-lo. O terceiro e último caso é o mais complexo. Este é o caso quando o nó que pretende eliminar tem duas crianças. A fim de fazer isso, primeiro temos que encontrar o nó que tem o valor maior mais próximo, trocar os dois, e depois excluir o nó em questão. Observe o nó que tem o valor maior mais próximo não pode ter duas crianças em si desde o seu filho esquerdo seria um candidato melhor para o maior seguinte. Portanto, a exclusão de um nó com dois filhos equivale a troca de 2 nós, e depois apagar é tratado por uma das duas regras acima mencionadas. Por exemplo, vamos dizer que queremos excluir o nó raiz de 13. A primeira coisa que fazemos é encontrar o próximo maior valor na árvore que, nesse caso, é de 21. Em seguida, trocar os 2 nós, fazendo uma folha 13 e 21 do nó do grupo central. Agora podemos simplesmente apagar 13. 

Como mencionado anteriormente, existem muitas formas possíveis para fazer uma árvore de busca binária válido. Infelizmente para nós, alguns são piores que outros. Por exemplo, o que acontece quando nós construímos uma árvore de busca binária a partir de uma lista ordenada de números? Todos os números são apenas adicionados à direita em cada etapa. Quando queremos procurar um número, não temos escolha, mas só de olhar para a direita em cada etapa. Isto não é melhor do que a busca linear de todo. Apesar de não cobri-los aqui, há outra, mais complexa, estruturas de dados que se certificar de que isso não aconteça. No entanto, uma coisa simples que pode ser feito para evitar isso é apenas para embaralhar aleatoriamente os valores de entrada. É altamente improvável que por acaso uma lista de números embaralhados está classificada. Se este fosse o caso, os casinos não permanecer na empresa por muito tempo. 

Lá você tem. Você já sabe sobre a pesquisa binária e árvores de busca binária. Sou Patrick Schmid, e este é CS50. [CS50.TV] Uma maneira óbvia seria a de verificar a lista de ... [bip] ... O número de itens ... sim [Risos] Postar ... nó de 234 ... Augh. >> Yay! Que foi -