[Powered by Google Translate] [Busca Binario] [Patrick Schmid - Harvard University] [Esta é CS50. - CS50.TV] 

Se eu lle dei unha lista de nomes de personaxes de Disney en orde alfabética e pediu-lle para atopar o Mickey Mouse, como é que vai facer sobre iso? Unha forma obvia sería a de examinar a lista desde o inicio e comprobar cada nome para ver se é Mickey. Pero cando le Aladdin, Alicia, Ariel, e así por diante, vai logo entender que a partir da fronte da lista non foi unha boa idea. Ok, quizais ten que comezar a traballar cara atrás a partir do final da lista. Agora ler Tarzan, Stitch, Brancaneves, e así por diante. Aínda así, esta non parece ser a mellor maneira de ir sobre el. 

Ben, outra forma que pode facer sobre iso é para tentar diminuír a lista de nomes que ten que mirar. Como vostede sabe que eles están en orde alfabética, pode só ollar para os nomes no medio da lista e comproba que o Mickey Mouse é antes ou despois deste nome. Mirando para o último nome na segunda columna vostede entendería que a M para Mickey vén despois J para Jasmine, así que simplemente ignorar a primeira metade da lista. Entón probablemente ollar para arriba da última columna e ver que comeza con Rapunzel. Mickey vén antes de Rapunzel, parece que podemos ignorar a última columna tamén. Continuando a estratexia de busca, podes ver rapidamente que Mickey está na primeira metade do resto lista de nomes e, finalmente, atopar Mickey oculto entre Merlin e Minnie. 

O que fixo foi basicamente busca binaria. Como este nome indica, el executa a súa estratexia de busca en cuestión binario. O que significa isto? Ben, dada unha lista de elementos clasificados, o algoritmo de procura binaria fai unha decisión binaria - cara á esquerda ou á dereita, maior ou menor que, por orde alfabética, antes ou despois - en cada punto. Agora que temos un nome que vai xunto con este algoritmo de procura, Vexamos outro exemplo, pero esta vez con unha lista de números ordenados. Dicir que estamos ollando para o número 144 na lista de números ordenados. Así como antes, atopamos o número que está no medio - que neste caso é de 13 - 144 para ver se é maior que ou menor que 13. Unha vez que é claramente maior que 13, podemos ignorar todo o que é de 13 ou menos e concentrar só na metade restante. Unha vez que agora teñen un número par de elementos da esquerda, nós simplemente escoller un número que está preto da media. Neste caso, nós escoller 55. Nós poderiamos ter facilmente seleccionados 89. Okay. Unha vez máis, 144 é maior que 55, por tanto, desprácese á dereita. Afortunadamente para nós, o número do medio próximo e 144, o que estamos a buscar. Polo tanto, a fin de atopar 144 usando investigación binaria, somos capaces de atopalo en só 3 pasos. Se tivésemos usado busca lineal aquí, tería nos levou 12 pasos. Por unha cuestión de feito, unha vez que este método de investigación metades do número de elementos ten que ollar a cada paso, vai atopar o elemento que está á procura de en sobre o logaritmo do número de elementos na lista. Agora que xa vimos dous exemplos, imos dar un ollo un pseudocódigo para unha función recursiva que aplica busca binaria. Comezando polo principio, vemos que temos que atopar unha función que recibe 4 argumentos: clave, matriz min, e Max. A clave é o número que nós estamos a buscar, de xeito 144 no exemplo anterior. Matriz é unha lista de números que estamos a buscar. Mínimo e máximo son os índices das posicións mínimas e máximas que actualmente estamos mirando. Así, cando se inicia, min será cero e max será o índice máximo da matriz. Como se restrinxir a busca a abaixo, imos actualizar min e max para ser só a franxa que aínda estamos mirando para dentro 

Imos saltar cara á parte interesante en primeiro lugar. O primeiro que facemos é atopar o punto medio, o índice que está a medio camiño entre o mínimo eo máximo da matriz que aínda estamos considerando. Entón, miramos para o valor da matriz en que a situación do punto medio e ver se o número que estamos a buscar é menor que a clave. O número no que a posición é menos entón iso significa que a clave é maior que todos os números á esquerda desa posición. Así, podemos chamar a función de busca binaria, de novo, pero esta vez, a actualizar o min e max parámetros de ler só a metade que é maior que ou igual ao valor que acabamos de ver. Por outra banda, a clave é menor que o número actual no punto medio da matriz, queremos ir á esquerda e ignorar todos os números que son maiores. Unha vez máis, chamamos busca binaria, pero esta vez coa gama de min e max updated para incluír só a metade inferior. Se o valor no punto medio actual na matriz non é nin maior que ou menor que a clave, entón ten que ser igual á chave. Así, podemos simplemente devolver o índice punto medio actual, e estamos a facer. Finalmente, esta verificación aquí é para o caso en que o número non é, en realidade, na matriz de números que estamos a buscar. Se o índice máximo do intervalo que estamos a buscar sempre menor que o mínimo, o que significa que nós fomos demasiado lonxe. Como o número non estaba na matriz de entrada, nós voltar -1 para indicar que nada se atopou. 

Debe ter notado que a este algoritmo para traballar, a lista de números ten que ser resolto. Noutras palabras, só podemos atopar 144 usando busca binaria todos os números son ordenadas de menor a maior. Se non fose este o caso, non sería capaz de eliminar a metade dos números en cada etapa. Polo tanto, temos dúas opcións. Ou podemos ter unha lista non ordenada e clasificalos lo antes de empregar busca binaria, ou podemos estar seguro de que a lista de números é clasificada como engadir números a el. Así, en vez de clasificar só cando temos que buscar, Por que non manter a lista de clasificados en todos os tempos? 

Unha forma de manter unha lista de números ordenados ao mesmo tempo, permitindo que unha para engadir ou cambiar os números da lista é usando algo chamado unha árbore de busca binaria. Unha árbore de busca binaria é unha estrutura de datos que ten tres propiedades. En primeiro lugar, a subárvore esquerda de calquera nodo contén só os valores que son menos de ou igual ao valor do nodo. En segundo lugar, o dereito subárvore dun nodo contén só valores que son maiores do que ou igual ao valor do nodo. E, finalmente, as subárvores esquerda e dereita de todo nós tamén son árbores de busca binaria. Vexamos un exemplo cos mesmos números que usamos anteriormente. Para aqueles de vostedes que nunca vin unha árbore de ciencia da computación antes, deixe-me comezar por lle dicir que unha árbore de informática medra para abaixo. Si, ao contrario de árbores que está acostumado, a raíz dunha árbore de informática e na parte superior, e as follas están na parte inferior. Cada caixa pequena chámase un nó e os nós son conectados uns a outros por arestas. Así, a raíz desta árbore é un valor do nodo co valor de 13, que ten dous fillos cos valores 5 e 34. Unha subárvore é a árbore que está formada só de ollar a unha subseção da árbore enteira. 

Por exemplo, a sub-árbore esquerda do apartado 3 é a árbore creada polos nós de 0, 1 e 2. Entón, se volver para as propiedades dunha árbore de busca binaria, vemos que cada nodo da árbore está de acordo con todas as tres propiedades, é dicir, subárvore esquerda contén só valores que son menos que ou igual ao valor do nodo; subárvore dereita de todo nós contén só valores que son maiores do que ou igual ao valor do nodo, e subárvores esquerda e dereita de todos os nós tamén son árbores de busca binaria. Aínda que esta árbore parece diferente, esta é unha árbore de busca binaria válido para o mesmo conxunto de números. Por unha cuestión de feito, hai moitas formas posibles que pode crear unha árbore de busca binaria válida a partir destes números. Ben, imos volver para o primeiro que creou. Entón o que podemos facer con esas árbores? Ben, podemos moi simplemente atopar os valores mínimo e máximo. Os valores mínimos poden ser atopados por sempre vai cara á esquerda ata que non haxa ningún nodo para visitar. Por outra banda, para atopar o máximo simplemente vai para abaixo á dereita en cada momento. 

Atopou calquera outro número que non sexa o mínimo ou máximo é tan fácil. Dicir que estamos a buscar o número 89. Nós simplemente comprobar o valor de cada nodo e vaia á esquerda ou á dereita, dependendo de se o valor do nó é menor ou maior que o que estamos a buscar. Así, a partir da raíz de 13, vemos que 89 é maior, e así imos cara á dereita. A continuación, vemos o nó para 34, e, de novo, vaia á dereita. 89 aínda é superior a 55, polo que seguimos indo cara á dereita. Nós entón chegar a un nodo co valor de 144 e vai cara á esquerda. Velaí que, 89 e logo alí. 

Outra cousa que podemos facer é imprimir todos os números a través da realización dun percorrido en inordem. Un percorrido en inordem significa imprimir todo na subárvore esquerda seguida de estampación o propio nodo e despois seguiu imprimindo todo na subárvore dereita. Por exemplo, imos tomar a nosa árbore binaria de procura favorito e imprimir os números en orde de clasificación. Comezamos a raíz do 13, pero antes de imprimir 13 temos para imprimir todo na subárvore esquerda. Entón imos para a 5. Aínda temos que ir máis fondo na árbore ata atopar o nodo máis á esquerda, que é igual a cero. Tras a impresión cero, volverse para o 1 e imprimir iso. Entón imos para a subárvore dereita, que é 2, e imprimir iso. Agora que estamos a facer que subárvore podemos volver-se para o 3 e imprimir lo. Continuando cara arriba, nós imprimimos a 5 e logo o 8. Agora que xa completou toda a subárvore esquerda, podemos imprimir a 13 e comezar a traballar na subárvore dereita. Nós descenda para 34, pero antes de imprimir 34 temos que imprimir a súa subárvore esquerda. Así, imprimir 21; entón nós comezamos a imprimir 34 e visitar a súa subárvore dereita. Desde 55 non subárvore esquerda, imprimir-lo e continuar a súa subárvore dereita. 144 ten unha sub-árbore da esquerda, e polo tanto, imprimir a 89, seguíndose a 144, e finalmente o no máis á dereita de 233. Alí tes, todos os números son impresos en orde da menor á maior. 

Engadir algo para a árbore é relativamente indolora tamén. Todo o que temos que facer é estar seguro de que nós seguimos tres binarios propiedades da árbore de busca e insira o valor onde hai espazo. Imos dicir que quere inserir o valor de 7. Dende 7 é menor que 13, imos cara á esquerda. Pero é maior que 5, así que atravesan a dereita. Dende que é menos de 8 e 8 é un nodo folla, nós engadimos 7 para o fillo esquerdo de 8. Listo! Nós engadimos un número para a nosa árbore de busca binaria. 

Se pudermos engadir cousas, o mellor é ser capaz de eliminar as cousas tan ben. Desafortunadamente para nós, a exclusión é un pouco máis complicado - non moito, pero un pouco. Hai tres escenarios diferentes que temos que considerar ao eliminar elementos de árbores de busca binaria. En primeiro lugar, o caso máis sinxelo é a de que o elemento é un nodo folla. Neste caso, nós simplemente apaga-lo e continuar co noso negocio. Dicir que queremos eliminar o 7 que acaba de engadir. Ben, nós simplemente atopalo, eliminar-lo, e é iso. O seguinte caso é o nó ten só un fillo. Aquí podemos eliminar o nodo, pero primeiro temos que ter seguro para conectar a subárvore que é deixada sen pais para o pai do nodo que acabou eliminada. Dicir que queremos borrar 3 da nosa árbore. Tomamos o elemento fillo dese nó e anexo-lo ao pai do nodo. Neste caso, estamos agora a poñer o 1 ao 5. Isto funciona sen ningún problema, xa sabemos, de acordo coa propiedade de árbore binaria de procura, que todo na subárvore esquerda de 3 era inferior a 5. Agora que 3 do sub é de tomar coidado, podemos excluílo. O terceiro e último caso é o máis complexo. Este é o caso cando o nodo que desexa eliminar ten dous nenos. Co fin de facer iso, primeiro temos que atopar o nodo que ten o valor máis grande máis próximo, intercambiar os dous, e despois eliminar o nodo en cuestión. Teña en conta o nodo que ten o valor máis grande máis próximo non pode ter dous nenos en si dende o seu fillo esquerdo sería un candidato mellor para o maior seguinte. Polo tanto, a exclusión dun nodo con dous fillos equivale a cambio de 2 nós, e despois borrar é tratado por unha das dúas modalidades anteriormente mencionadas. Por exemplo, imos dicir que queremos borrar o nodo raíz de 13. O primeiro que facemos é o seguinte maior valor na árbore que, nese caso, é de 21. A continuación, cambiar os 2 nós, facendo unha folla 13 e 21 do nó do grupo central. Agora podemos simplemente eliminar 13. 

Como mencionado anteriormente, hai moitas formas posibles para facer unha árbore de busca binaria válido. Desafortunadamente para nós, algúns son peores que outros. Por exemplo, o que acontece cando nós construímos unha árbore de busca binaria a partir dunha lista ordenada de números? Todos os números son só engadidos á dereita en cada etapa. Cando queremos buscar un número, non temos elección, pero só de ollar para a dereita en cada etapa. Isto non é mellor que a procura lineal de todo. A pesar de non cobre-los aquí, hai outra, máis complexa, estruturas de datos que asegurarse de que isto non aconteza. Con todo, unha cousa simple que se pode facer para evitar isto é só para embaralhar chou os valores de entrada. É altamente improbable que por casualidade unha lista de números embaralhados está clasificada. Se este fose o caso, os casinos non permanecer na empresa por moito tempo. 

Alí ten. Xa sabe sobre a investigación binaria e árbores de busca binaria. Son Patrick Schmid, e este é CS50. [CS50.TV] Unha forma obvia sería a de comprobar a lista de ... [bip] ... O número de elementos ... si [Risas] Publicar ... nó de 234 ... Augh. >> Yay! Que foi -