[Powered by Google Translate] [이진 검색] [패트릭 슈 미드 - 하버드 대학] [이 CS50입니다. - CS50.TV] 

나는 알파벳 순서 당신에게 디즈니 캐릭터 이름의 목록을 줬 경우 그리고, 미키 마우스를 찾아 보라고 했잖아 어떻게이 일을 어떻게해야합니까? 확실한 방법은 처음부터 목록을 검색하는 것 하고 미키 있는지 볼 수있는 모든 이름을 확인합니다. 하지만 당신이 등등 알라딘, 앨리스, 에리얼을 읽고으로, 당신은 신속하게 목록의 앞에 시작하는 것은 좋은 생각이 아니었다는 걸 수 있습니다. 그래, 아마도 당신은 목록의 끝에서부터 거꾸로 작업을 시작해야합니다. 이제 당신은 타잔, 스티치, 백설 공주, 등등을 읽어보십시오. 그러나,이 그것에 대해 이동하는 가장 좋은 방법은 아닌 것 같은데. 

음, 당신이이 일을에 대해 갈 수있는 또 다른 방법은 범위를 좁힐하려고하는 것입니다 당신이 볼해야하는 이름의 목록입니다. 당신이이 사람들 알파벳 순서 것을 알고 있기 때문에, 당신은 목록의 중간에 이름을 볼 수 있었다 미키 마우스는 이름 앞이나 뒤에있는 경우 및 확인합니다. 두 번째 열에서 마지막 이름을 보면 당신은 그 미키에 대한 M 재스민에 대한 J 이후에 제공한다는 걸 그래서 당신은 단순히 목록의 첫 번째 절반을 무시 할. 그런 다음 당신은 아마 마지막 열의 맨 위에있는 거 같아 하고 라푼젤로 시작을 참조하십시오. 미키는 라푼젤 앞에 오는, 우리는뿐만 아니라 마지막 열을 무시할 수 것 같습니다. 검색 전략을 계속, 당신은 신속하게 볼 수 있습니다 그 미키 이름의 나머지 목록 상반기에 그리고 마지막으로 미키는 멀린와 미니 사이에 숨어 찾으십시오. 

당신이 한 일에 기본적으로 이진 검색했습니다. 이 이름에서 알 수 있듯이, 그것은 바이너리 문제에 자사의 검색 전략을 수행합니다. 이것은 무엇을 의미할까요? 음, 정렬 된 항목의 목록 제공, 이진 검색 알고리즘은 이진 결정을합니다 - 왼쪽 또는 오른쪽으로,보다 크거나 적은 전이나 후에 순으로보다 - 각 지점에서. 이제이 검색 알고리즘과 함께 어울리는 이름을 가지고, 의 다른 예를 살펴 보자,이 시간이 정렬 숫자의 목록. 우리가 분류 번호 목록에있는 번호 144를 찾고 있습니다 말해봐. 전 맘에 들어요, 우리는 중간에 숫자를 찾아 - 이는이 경우에는 13합니다 - 144보다 크거나 13보다 작은 경우를 참조하십시오. 그 13보다 명확하게 큰 관계로, 우리는 13 이하 모든 무시할 수 있습니다 불과 나머지 부분에 집중. 이제 남은 항목의 짝수을 가지고 있기 때문에 우리는 단순히 중간에 인접 번호를 선택합니다. 이 경우 우리는 55을 선택합니다. 우리는 쉽게 89 선택한 수 있습니다. 좋아요. 다시, 144 55보다 큰, 그래서 우리는 오른쪽으로 이동합니다. 다행히도, 다음 중간 번호, 144입니다 우리가 찾고있는 한. 이진 검색을 사용하여 144을 찾을 수 있도록 위해, 우리는 3 단계에서 찾을 수있게되었습니다. 우리가 여기서 선형 검색을 사용했을 경우, 우리 12 조치를 취 것이다. 사실, 이후이 검색 방법은 항목의 수를 절반 이는 각 단계에서 살펴 있고, 그것이 검색하는 항목을 찾을 수 있습니다 목록에서 항목의 수의 로그에 대한 인치 이제 우리는이 사례를 본 적이있는, 어디를 살펴 보자 이진 검색을 구현​​하는 재귀 함수에 대한 일부 의사. 상단에있는 시작, 우리는 4 인수를 함수를 찾을해야한다는 참조하십시오 키, 배열, 분, 및 최대. 키는 우리가 앞의 예에서 너무 144, 찾고있는 번호입니다. 배열은 우리가 검색하는 숫자의 목록입니다. 최소 및 최대 최소 및 최대 위치의 인덱스 아르 현재보고있는 것을. 그래서 우리가 시작할 때, 분 제로되며 최대 배열의 최대 인덱스 될 것입니다. 우리가 검색 범위를 좁히려면, 우리는 분, 최대를 업데이트합니다 우리가 아직 인치 찾고있는 단지 범위를 할 수 

의 처음 흥미로운 부분을 건너 보자. 우리가 가장 먼저하는 일이, 중간 지점을 찾을 수 있습니다 중간 우리가 아직 고려하고있는 배열의 분, 최대 사이 색인을 생성합니다. 그리고 우리는 그 중간 지점에 위치에 배열의 값을 살펴 우리가 찾고있는 번호가 해당 키보다 작다면보고. 그 위치에서 숫자가 적은 경우, 다음은 키가 그 자리의 왼쪽에있는 숫자보다 큰 의미합니다. 그래서 우리는 다시 이진 검색 함수를 호출 할 수 있습니다 하지만이 시간은 반을 읽어 분, 최대 매개 변수를 업데이트 그보다 크거나 우리가 바라 보았다 값이 동일합니다. 한편, 키가 배열의 현재 중간 지점에있는 수보다 적은 경우는, 우리는 왼쪽으로 가서 큰 모든 숫자를 무시하고 싶습니다. 다시 말하지만, 우리는 분, 최대 업데이트 된 범위에 이진 검색하지만이 시간 전화 단지 아래쪽 포함 할 수 있습니다. 배열에서 현재 중간 지점에있는 값도 인 경우 보다 큰 나 키보다 작 다음은 키 같아야합니다. 따라서, 우리는 단순히 현재의 중간 지점 인덱스를 반환 할 수 있으며, 우리는 끝났어. 마지막으로, 여기에서이 검사는 사건에 대해입니다 수 우리가 검색 숫자의 배열에서 실제로하지 않습니다. 만약 우리가 찾고있는 범위의 최대 인덱스 최소 때보 다 적은, 우리가 너무 멀리 갔다 있다는 것을 의미합니다. 번호가 입력 배열에서가 아니었기 때문에, 우리는 -1 반환 아무것도를 표시하지하는 것은 발견되었다. 

당신은이 알고리즘이 작동하는 것을 보셨을 것 숫자의 목록을 정렬 할 수 있습니다. 즉, 우리는 이진 검색을 사용하여 144을 찾을 수 있습니다 모든 숫자가 낮은에서 높은 주문하는 경우. 이 경우이 아니었다면, 우리는 각 단계에서의 숫자의 절반을 제외 할 수 없습니다 것입니다. 그래서 우리는 두 가지 옵션이 있습니다. 어느 우리는 이진 검색을 사용하기 전에 정렬되지 않은 목록을 가져 가서 정렬 할 수 있습니다 또는 우리는 여기에 번호를 추가 할 번호의 목록이 정렬되어 있는지 확인 할 수 있습니다. 따라서, 대신 우리가 검색 할 수있는 걸 때 정렬의, 왜 항상 정렬 목록을 보관하지? 

동시에 허용하면서 숫자의 목록을 유지하는 방법 중 하나는 정렬 하나는이 목록에서 번호를 추가하거나 이동 이진 검색 트리라는 걸를 사용하는 것입니다. 이진 검색 트리 3 속성을 가진 데이터 구조입니다. 첫째, 모든 노드의 왼쪽 하위 트리가보다 만 값을 포함 또는 노드의 값과 동일. 둘째, 노드의 오른쪽 하위 트리 만보다 큰 값을 포함 또는 노드의 값과 동일. 모든 노드의 그리고 마지막으로, 왼쪽과 오른쪽 하위 트리 모두 또한 이진 검색 나무입니다. 우리가 이전에 사용 된 것과 동일한 번호를 예를 들어 살펴 보자. 컴퓨터 과학의 나무 한 번도 본 적이없는 분들을 위해, 내가 컴퓨터 과학 나무가 아래쪽으로 성장된다는하여 시작합시다. 예,에게 익숙한 나무는 달리, 컴퓨터 과학 트리의 루트는 상단에 있습니다 그리고 잎은 하단에 있습니다. 각각의 작은 상자는 노드라고하며, 노드가 가장자리에 의해 서로 연결되어 있습니다. 따라서이 트리의 루트는 값이 13 노드 값입니다 이는 값 5 34 어린이 2 인 노드가 있습니다. 하위 트리는 전체 트리의 하위 섹션을보고에 의해 형성되는 나무입니다. 

예를 들어, 노드 3의 왼쪽 하위 트리의 노드 0, 1, 2에 의해 생성 된 나무입니다. 그래서, 우리는 이진 검색 트리의 속성에 돌아 가면, 우리는 트리의 각 노드 즉 모든 3 속성에 부합 것을 볼 왼쪽 하위 트리 만보다 작거나 노드의 값 같은 값이 포함되어 있습니다; 모든 노드의 오른쪽 하위 트리 만보다 크거나 노드의 값과 같다 값을 포함하고, 모든 노드의 왼쪽과 오른쪽 모두 하위 트리도 이진 검색 나무입니다. 이 나무가 다른 보이지만이 유효한 이진 검색 트리입니다 숫자의 동일한 집합에 대한. 사실, 당신이 만들 수있는 여러 가지 방법이 있습니다 이 숫자에서 유효한 이진 검색 트리입니다. 음, 우리가 만든 첫 번째로 돌아가 보자. 그래서 우리는이 나무가 무엇을 할 수 있습니까? 음, 우리는 아주 간단히 최소 및 최대 값을 찾을 수 있습니다. 최소 값은 항상 왼쪽으로 이동하여 찾을 수 있습니다 방문 할 더 이상 노드가 될 때까지. 반대로, 최대 하나를 찾기 위해 단순히 단지마다에서 오른쪽으로 내려갑니다. 

다른 번호를 찾는 것은 최소 또는 최대가되지는 마찬가지로 간단합니다. 우리는 숫자 89을 찾고 말해. 우리는 단순히 각 노드의 값을 확인하고 왼쪽 또는 오른쪽으로 이동 노드의 값보다 작거나보다 큰인지에 따라 우리가 찾고있는 한. 따라서, 13의 루트에서 시작, 우리는, 89가 큰 것을 알 그래서 우리는 오른쪽으로 이동합니다. 그럼 우리가 34의 노드를 확인하고 다시 우리는 오른쪽으로 이동합니다. 89 여전히 55보다 큰, 그래서 우리는 오른쪽으로 계속. 우리는 144의 값이있는 노드와 올라 와서 왼쪽으로 이동합니다. ro와 보라, 89 바로이 있습니다. 

우리가 할 수있는 또 다른 것은 inorder 순회를 수행하여 모든 숫자를 인쇄합니다. inorder 순회는 왼쪽 하위 트리에 모든 출력을 의미합니다 노드 자체를 인쇄하여 다음 다음 오른쪽 하위 트리에 모든 출력이 나타납니다. 예를 들어, 우리가 제일 좋아하는 이진 검색 트리를 봅시다 그리고 정렬 순서 번호를 인쇄 할 수 있습니다. 우리는 13 루트에서 시작하지만, 인쇄 13 전에 우리는 인쇄해야 왼쪽 하위 트리의 모든. 그래서 우리는 5로 이동합니다. 우리는 여전히 우리가 가장 왼쪽에있는 노드를 찾을 때까지 트리에서 깊이 내려 가야 이는 0입니다. 인쇄 제로 후, 우리는 1 돌아가서 그 아웃을 인쇄 할 수 있습니다. 그럼 우리는 2 인, 오른쪽 하위 트리로 이동하여 그 곳을 인쇄 할 수 있습니다. 이젠 우리는 그 하위 트리와 함께 완료 우리는 3 다시 올라 가야지하고 인쇄 할 수 있습니다. 백업 계속, 우리는 8 다음 5 인쇄합니다. 이제 우리는 전체를 완료 한이 하위 트리를 왼쪽으로 우리는 13를 인쇄하고 오른쪽 하위 트리 작업을 시작할 수 있습니다. 우리는 34 아래로 뛰어 있지만, 인쇄 34 전에 우리는 왼쪽 하위 트리를 인쇄해야합니다. 그래서 우리는 21를 인쇄 한 후 우리는 34 인쇄 및 오른쪽 하위 트리를 방문하게. 55도 왼쪽 하위 트리가 없기 때문에, 우리는 그것을 인쇄하고 오른쪽 하위 트리에 계속합니다. 144 왼쪽 하위 트리를 가지고 있으며, 그래서 우리는 144에 이어, 89 인쇄 233의 마지막으로 가장 오른쪽 노드. 당신이 그걸 가져가, 모든 번호가 낮은에서 높은 순서로 인쇄됩니다. 

나무에 뭔가를 추가하는 것은 물론 상대적으로 통증이 있습니다. 우리가해야 할 일은 우리 3 이진 검색 트리 속성을 준수인지 확인 공간이있는 다음 값을 삽입합니다. 자, 우리는 7의 값을 삽입 할 말한다. 7 이하 13이기 때문에, 우리는 왼쪽으로 이동합니다. 그러나 5보다 큰 해, 그래서 우리는 오른쪽으로 트래버스. 그 8 8 잎 노드 미만입니다 때문에, 우리는 8 왼쪽 자녀 7 추가합니다. 짜잔! 우리는 우리의 이진 검색 트리에 번호를 추가했습니다. 

우리가 물건을 추가 할 수있는 경우, 우리는 더 나은뿐만 아니라 물건을 삭제할 수 있습니다. 불행하게도 우리,​​ 삭제는 조금 더 복잡합니다 - 많이하지만 조금 없습니다. 우리가 생각해야하는 3 가지 시나리오가 있습니다 이진 검색 나무에서 요소를 삭제합니다. 첫째, 가장 쉬운 경우는 요소가 잎 노드이라는 것입니다. 이 경우, 우리는 간단히 삭제하고 우리의 사업을 계속 이동합니다. 우리가 방금 추가 한 7 삭제하려는 말해. 음, 우리가 단순히 그것을 찾아 그것을 제거하고 그게 다에요. 노드 만 어린이 1가있는 경우 다음 경우입니다. 여기 노드를 삭제할 수 있지만, 우리가 처음 확인해야합니다 지금 parentless 남아 그 하위 트리를 연결하는 노드의 부모 우린 그냥 삭제되었습니다. 우리는 나무에서 3 삭제하려는 말해. 우리는 노드의 자식 요소를 가지고 노드의 부모에 첨부합니다. 이 경우, 우리는 이제 5 1 장착하고 있습니다. 우리가 알고 있기 때문에, 이진 검색 트리 속성에 따라 문제없이 작동 3 왼쪽 하위 트리의 모든 것은보다 5 살. 3의 하위 트리가 처리 할 수​​ 있기 때문에 이젠, 우리가 삭제할 수 있습니다. 세 번째이자 마지막 경우가 가장 복잡합니다. 우리가 삭제하려는 노드가 어린이 2 인이 때 경우가 있습니다. 이 작업을 수행하기 위해, 우리는 먼저 다음 큰 값을 가진 노드를 찾아야 해 두를 교체 한 후 문제의 노드를 삭제합니다. 다음 가장 큰 값이 어린이 2 명 자체를 가질 수있는 노드를 확인합니다 그 왼쪽의 아이가 다음 큰 더 나은 후보가 될 것입니다 때문입니다. 따라서, 어린이 2 명으로 노드를 삭제하면, 2 노드의 교환을 보냈다 그리고 삭제는 2 상기 규칙 1에 의해 처리됩니다. 예를 들어, 우리는 루트 노드, 13를 삭제하려면 말한다. 우리가 가장 먼저하는 일이 우리가 트리의 다음 큰 값을 찾을 수 있습니다 이는,이 경우에는, 21입니다. 우리는 13 잎 21 중앙 그룹 노드를 만드는 2 노드를 스왑. 이제 우리는 단순히 13 삭제할 수 있습니다. 

앞에서 언급에, 유효한 이진 검색 트리를 만드는 여러 가지 방법이 있습니다. 불행하게도 우리,​​ 일부는 다른 것보다 더 있습니다. 우리는 이진 검색 트리를 빌드 할 때 예를 들어, 어떤 현상이 발생 숫자의 정렬 목록에서? 모든 번호는 단지 각 단계에서 오른쪽에 추가됩니다. 우리가 번호를 검색 할 때, 우리는 선택의 여지가 없습니다 만 각 단계에 적절한 보는. 이 전혀 선형 검색보다 더하지 않습니다. 우리가 여기에 포함되지는 않지만, 더 복잡한, 기타 있습니다 이런 일이 있지 않은지 확인하십시오 데이터 구조. 그러나, 이러한 일을 방지하기 위해 수행 할 수있는 하나 간단한 일입니다 그냥 무작위로 섞어 입력 값을합니다. 그것은 임의 우연히 번호 질질 목록이 정렬되어 매우 가능성이 있습니다. 이 경우라면, 카지노는 오랫동안 사업을 유지 않습니다. 

당신이 그걸 있습니다. 이제 이진 검색과 이진 검색 나무에 대해 알고. 나는 패트릭 슈미트, 그리고이 CS50입니다. [CS50.TV] 확실한 방법은에서 목록을 검색하는 것 ... [신호음] ... 항목의 수 ... 옙 [웃음] ... 234 ... augh의 노드를 게시 할 수 있습니다. >> 야호! 그건 -