1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [이진 검색]

2
00:00:02,000 --> 00:00:04,000
[패트릭 슈 미드 - 하버드 대학]

3
00:00:04,000 --> 00:00:07,000
[이 CS50입니다. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> 나는 알파벳 순서 당신에게 디즈니 캐릭터 이름의 목록을 줬 경우

5
00:00:09,000 --> 00:00:11,000
그리고, 미키 마우스를 찾아 보라고 했잖아

6
00:00:11,000 --> 00:00:13,000
어떻게이 일을 어떻게해야합니까?

7
00:00:13,000 --> 00:00:15,000
확실한 방법은 처음부터 목록을 검색하는 것

8
00:00:15,000 --> 00:00:18,000
하고 미키 있는지 볼 수있는 모든 이름을 확인합니다.

9
00:00:18,000 --> 00:00:22,000
하지만 당신이 등등 알라딘, 앨리스, 에리얼을 읽고으로,

10
00:00:22,000 --> 00:00:25,000
당신은 신속하게 목록의 앞에 시작하는 것은 좋은 생각이 아니었다는 걸 수 있습니다.

11
00:00:25,000 --> 00:00:29,000
그래, 아마도 당신은 목록의 끝에서부터 거꾸로 작업을 시작해야합니다.

12
00:00:29,000 --> 00:00:33,000
이제 당신은 타잔, 스티치, 백설 공주, 등등을 읽어보십시오.

13
00:00:33,000 --> 00:00:36,000
그러나,이 그것에 대해 이동하는 가장 좋은 방법은 아닌 것 같은데.

14
00:00:36,000 --> 00:00:38,000
>> 음, 당신이이 일을에 대해 갈 수있는 또 다른 방법은 범위를 좁힐하려고하는 것입니다

15
00:00:38,000 --> 00:00:41,000
당신이 볼해야하는 이름의 목록입니다.

16
00:00:41,000 --> 00:00:43,000
당신이이 사람들 알파벳 순서 것을 알고 있기 때문에,

17
00:00:43,000 --> 00:00:45,000
당신은 목록의 중간에 이름을 볼 수 있었다

18
00:00:45,000 --> 00:00:49,000
미키 마우스는 이름 앞이나 뒤에있는 경우 및 확인합니다.

19
00:00:49,000 --> 00:00:51,000
두 번째 열에서 마지막 이름을 보면

20
00:00:51,000 --> 00:00:54,000
당신은 그 미키에 대한 M 재스민에 대한 J 이후에 제공한다는 걸

21
00:00:54,000 --> 00:00:57,000
그래서 당신은 단순히 목록의 첫 번째 절반을 무시 할.

22
00:00:57,000 --> 00:00:59,000
그런 다음 당신은 아마 마지막 열의 맨 위에있는 거 같아

23
00:00:59,000 --> 00:01:02,000
하고 라푼젤로 시작을 참조하십시오.

24
00:01:02,000 --> 00:01:06,000
미키는 라푼젤 앞에 오는, 우리는뿐만 아니라 마지막 열을 무시할 수 것 같습니다.

25
00:01:06,000 --> 00:01:08,000
검색 전략을 계속, 당신은 신속하게 볼 수 있습니다 그 미키

26
00:01:08,000 --> 00:01:11,000
이름의 나머지 목록 상반기에

27
00:01:11,000 --> 00:01:14,000
그리고 마지막으로 미키는 멀린와 미니 사이에 숨어 찾으십시오.

28
00:01:14,000 --> 00:01:17,000
>> 당신이 한 일에 기본적으로 이진 검색했습니다.

29
00:01:17,000 --> 00:01:22,000
이 이름에서 알 수 있듯이, 그것은 바이너리 문제에 자사의 검색 전략을 수행합니다.

30
00:01:22,000 --> 00:01:24,000
이것은 무엇을 의미할까요?

31
00:01:24,000 --> 00:01:27,000
음, 정렬 된 항목의 목록 제공, 이진 검색 알고리즘은 이진 결정을합니다 -

32
00:01:27,000 --> 00:01:33,000
왼쪽 또는 오른쪽으로,보다 크거나 적은 전이나 후에 순으로보다 - 각 지점에서.

33
00:01:33,000 --> 00:01:35,000
이제이 검색 알고리즘과 함께 어울리는 이름을 가지고,

34
00:01:35,000 --> 00:01:38,000
의 다른 예를 살펴 보자,이 시간이 정렬 숫자의 목록.

35
00:01:38,000 --> 00:01:43,000
우리가 분류 번호 목록에있는 번호 144를 찾고 있습니다 말해봐.

36
00:01:43,000 --> 00:01:46,000
전 맘에 들어요, 우리는 중간에 숫자를 찾아 -

37
00:01:46,000 --> 00:01:50,000
이는이 경우에는 13합니다 - 144보다 크거나 13보다 작은 경우를 참조하십시오.

38
00:01:50,000 --> 00:01:54,000
그 13보다 명확하게 큰 관계로, 우리는 13 이하 모든 무시할 수 있습니다

39
00:01:54,000 --> 00:01:57,000
불과 나머지 부분에 집중.

40
00:01:57,000 --> 00:01:59,000
이제 남은 항목의 짝수을 가지고 있기 때문에

41
00:01:59,000 --> 00:02:01,000
우리는 단순히 중간에 인접 번호를 선택합니다.

42
00:02:01,000 --> 00:02:03,000
이 경우 우리는 55을 선택합니다.

43
00:02:03,000 --> 00:02:06,000
우리는 쉽게 89 선택한 수 있습니다.

44
00:02:06,000 --> 00:02:11,000
좋아요. 다시, 144 55보다 큰, 그래서 우리는 오른쪽으로 이동합니다.

45
00:02:11,000 --> 00:02:14,000
다행히도, 다음 중간 번호, 144입니다

46
00:02:14,000 --> 00:02:16,000
우리가 찾고있는 한.

47
00:02:16,000 --> 00:02:21,000
이진 검색을 사용하여 144을 찾을 수 있도록 위해, 우리는 3 단계에서 찾을 수있게되었습니다.

48
00:02:21,000 --> 00:02:24,000
우리가 여기서 선형 검색을 사용했을 경우, 우리 12 조치를 취 것이다.

49
00:02:24,000 --> 00:02:28,000
사실, 이후이 검색 방법은 항목의 수를 절반

50
00:02:28,000 --> 00:02:31,000
이는 각 단계에서 살펴 있고, 그것이 검색하는 항목을 찾을 수 있습니다

51
00:02:31,000 --> 00:02:35,000
목록에서 항목의 수의 로그에 대한 인치

52
00:02:35,000 --> 00:02:37,000
이제 우리는이 사례를 본 적이있는, 어디를 살펴 보자

53
00:02:37,000 --> 00:02:41,000
이진 검색을 구현​​하는 재귀 함수에 대한 일부 의사.

54
00:02:41,000 --> 00:02:44,000
상단에있는 시작, 우리는 4 인수를 함수를 찾을해야한다는 참조하십시오

55
00:02:44,000 --> 00:02:47,000
키, 배열, 분, 및 최대.

56
00:02:47,000 --> 00:02:51,000
키는 우리가 앞의 예에서 너무 144, 찾고있는 번호입니다.

57
00:02:51,000 --> 00:02:54,000
배열은 우리가 검색하는 숫자의 목록입니다.

58
00:02:54,000 --> 00:02:57,000
최소 및 최대 최소 및 최대 위치의 인덱스 아르

59
00:02:57,000 --> 00:02:59,000
현재보고있는 것을.

60
00:02:59,000 --> 00:03:03,000
그래서 우리가 시작할 때, 분 제로되며 최대 배열의 최대 인덱스 될 것입니다.

61
00:03:03,000 --> 00:03:07,000
우리가 검색 범위를 좁히려면, 우리는 분, 최대를 업데이트합니다

62
00:03:07,000 --> 00:03:10,000
우리가 아직 인치 찾고있는 단지 범위를 할 수

63
00:03:10,000 --> 00:03:12,000
>> 의 처음 흥미로운 부분을 건너 보자.

64
00:03:12,000 --> 00:03:14,000
우리가 가장 먼저하는 일이, 중간 지점을 찾을 수 있습니다

65
00:03:14,000 --> 00:03:19,000
중간 우리가 아직 고려하고있는 배열의 분, 최대 사이 색인을 생성합니다.

66
00:03:19,000 --> 00:03:22,000
그리고 우리는 그 중간 지점에 위치에 배열의 값을 살펴

67
00:03:22,000 --> 00:03:25,000
우리가 찾고있는 번호가 해당 키보다 작다면보고.

68
00:03:25,000 --> 00:03:27,000
그 위치에서 숫자가 적은 경우,

69
00:03:27,000 --> 00:03:31,000
다음은 키가 그 자리의 왼쪽에있는 숫자보다 큰 의미합니다.

70
00:03:31,000 --> 00:03:33,000
그래서 우리는 다시 이진 검색 함수를 호출 할 수 있습니다

71
00:03:33,000 --> 00:03:36,000
하지만이 시간은 반을 읽어 분, 최대 매개 변수를 업데이트

72
00:03:36,000 --> 00:03:40,000
그보다 크거나 우리가 바라 보았다 값이 동일합니다.

73
00:03:40,000 --> 00:03:44,000
한편, 키가 배열의 현재 중간 지점에있는 수보다 적은 경우는,

74
00:03:44,000 --> 00:03:47,000
우리는 왼쪽으로 가서 큰 모든 숫자를 무시하고 싶습니다.

75
00:03:47,000 --> 00:03:52,000
다시 말하지만, 우리는 분, 최대 업데이트 된 범위에 이진 검색하지만이 시간 전화

76
00:03:52,000 --> 00:03:54,000
단지 아래쪽 포함 할 수 있습니다.

77
00:03:54,000 --> 00:03:57,000
배열에서 현재 중간 지점에있는 값도 인 경우

78
00:03:57,000 --> 00:04:01,000
보다 큰 나 키보다 작 다음은 키 같아야합니다.

79
00:04:01,000 --> 00:04:05,000
따라서, 우리는 단순히 현재의 중간 지점 인덱스를 반환 할 수 있으며, 우리는 끝났어.

80
00:04:05,000 --> 00:04:09,000
마지막으로, 여기에서이 검사는 사건에 대해입니다 수

81
00:04:09,000 --> 00:04:11,000
우리가 검색 숫자의 배열에서 실제로하지 않습니다.

82
00:04:11,000 --> 00:04:14,000
만약 우리가 찾고있는 범위의 최대 인덱스

83
00:04:14,000 --> 00:04:17,000
최소 때보 다 적은, 우리가 너무 멀리 갔다 있다는 것을 의미합니다.

84
00:04:17,000 --> 00:04:20,000
번호가 입력 배열에서가 아니었기 때문에, 우리는 -1 반환

85
00:04:20,000 --> 00:04:24,000
아무것도를 표시하지하는 것은 발견되었다.

86
00:04:24,000 --> 00:04:26,000
>> 당신은이 알고리즘이 작동하는 것을 보셨을 것

87
00:04:26,000 --> 00:04:28,000
숫자의 목록을 정렬 할 수 있습니다.

88
00:04:28,000 --> 00:04:31,000
즉, 우리는 이진 검색을 사용하여 144을 찾을 수 있습니다

89
00:04:31,000 --> 00:04:34,000
모든 숫자가 낮은에서 높은 주문하는 경우.

90
00:04:34,000 --> 00:04:38,000
이 경우이 아니었다면, 우리는 각 단계에서의 숫자의 절반을 제외 할 수 없습니다 것입니다.

91
00:04:38,000 --> 00:04:40,000
그래서 우리는 두 가지 옵션이 있습니다.

92
00:04:40,000 --> 00:04:43,000
어느 우리는 이진 검색을 사용하기 전에 정렬되지 않은 목록을 가져 가서 정렬 할 수 있습니다

93
00:04:43,000 --> 00:04:48,000
또는 우리는 여기에 번호를 추가 할 번호의 목록이 정렬되어 있는지 확인 할 수 있습니다.

94
00:04:48,000 --> 00:04:50,000
따라서, 대신 우리가 검색 할 수있는 걸 때 정렬의,

95
00:04:50,000 --> 00:04:53,000
왜 항상 정렬 목록을 보관하지?

96
00:04:53,000 --> 00:04:57,000
>> 동시에 허용하면서 숫자의 목록을 유지하는 방법 중 하나는 정렬

97
00:04:57,000 --> 00:04:59,000
하나는이 목록에서 번호를 추가하거나 이동

98
00:04:59,000 --> 00:05:02,000
이진 검색 트리라는 걸를 사용하는 것입니다.

99
00:05:02,000 --> 00:05:05,000
이진 검색 트리 3 속성을 가진 데이터 구조입니다.

100
00:05:05,000 --> 00:05:09,000
첫째, 모든 노드의 왼쪽 하위 트리가보다 만 값을 포함

101
00:05:09,000 --> 00:05:11,000
또는 노드의 값과 동일.

102
00:05:11,000 --> 00:05:15,000
둘째, 노드의 오른쪽 하위 트리 만보다 큰 값을 포함

103
00:05:15,000 --> 00:05:17,000
또는 노드의 값과 동일.

104
00:05:17,000 --> 00:05:20,000
모든 노드의 그리고 마지막으로, 왼쪽과 오른쪽 하위 트리 모두

105
00:05:20,000 --> 00:05:23,000
또한 이진 검색 나무입니다.

106
00:05:23,000 --> 00:05:26,000
우리가 이전에 사용 된 것과 동일한 번호를 예를 들어 살펴 보자.

107
00:05:26,000 --> 00:05:30,000
컴퓨터 과학의 나무 한 번도 본 적이없는 분들을 위해,

108
00:05:30,000 --> 00:05:34,000
내가 컴퓨터 과학 나무가 아래쪽으로 성장된다는하여 시작합시다.

109
00:05:34,000 --> 00:05:36,000
예,에게 익숙한 나무는 달리,

110
00:05:36,000 --> 00:05:38,000
컴퓨터 과학 트리의 루트는 상단에 있습니다

111
00:05:38,000 --> 00:05:41,000
그리고 잎은 하단에 있습니다.

112
00:05:41,000 --> 00:05:45,000
각각의 작은 상자는 노드라고하며, 노드가 가장자리에 의해 서로 연결되어 있습니다.

113
00:05:45,000 --> 00:05:48,000
따라서이 트리의 루트는 값이 13 노드 값입니다

114
00:05:48,000 --> 00:05:52,000
이는 값 5 34 어린이 2 인 노드가 있습니다.

115
00:05:52,000 --> 00:05:57,000
하위 트리는 전체 트리의 하위 섹션을보고에 의해 형성되는 나무입니다.

116
00:05:57,000 --> 00:06:03,000
>> 예를 들어, 노드 3의 왼쪽 하위 트리의 노드 0, 1, 2에 의해 생성 된 나무입니다.

117
00:06:03,000 --> 00:06:06,000
그래서, 우리는 이진 검색 트리의 속성에 돌아 가면,

118
00:06:06,000 --> 00:06:09,000
우리는 트리의 각 노드 즉 모든 3 속성에 부합 것을 볼

119
00:06:09,000 --> 00:06:15,000
왼쪽 하위 트리 만보다 작거나 노드의 값 같은 값이 포함되어 있습니다;

120
00:06:15,000 --> 00:06:16,000
모든 노드의 오른쪽 하위 트리

121
00:06:16,000 --> 00:06:19,000
만보다 크거나 노드의 값과 같다 값을 포함하고,

122
00:06:19,000 --> 00:06:25,000
모든 노드의 왼쪽과 오른쪽 모두 하위 트리도 이진 검색 나무입니다.

123
00:06:25,000 --> 00:06:28,000
이 나무가 다른 보이지만이 유효한 이진 검색 트리입니다

124
00:06:28,000 --> 00:06:30,000
숫자의 동일한 집합에 대한.

125
00:06:30,000 --> 00:06:32,000
사실, 당신이 만들 수있는 여러 가지 방법이 있습니다

126
00:06:32,000 --> 00:06:35,000
이 숫자에서 유효한 이진 검색 트리입니다.

127
00:06:35,000 --> 00:06:38,000
음, 우리가 만든 첫 번째로 돌아가 보자.

128
00:06:38,000 --> 00:06:40,000
그래서 우리는이 나무가 무엇을 할 수 있습니까?

129
00:06:40,000 --> 00:06:44,000
음, 우리는 아주 간단히 최소 및 최대 값을 찾을 수 있습니다.

130
00:06:44,000 --> 00:06:46,000
최소 값은 항상 왼쪽으로 이동하여 찾을 수 있습니다

131
00:06:46,000 --> 00:06:48,000
방문 할 더 이상 노드가 될 때까지.

132
00:06:48,000 --> 00:06:53,000
반대로, 최대 하나를 찾기 위해 단순히 단지마다에서 오른쪽으로 내려갑니다.

133
00:06:54,000 --> 00:06:56,000
>> 다른 번호를 찾는 것은 최소 또는 최대가되지는

134
00:06:56,000 --> 00:06:58,000
마찬가지로 간단합니다.

135
00:06:58,000 --> 00:07:00,000
우리는 숫자 89을 찾고 말해.

136
00:07:00,000 --> 00:07:03,000
우리는 단순히 각 노드의 값을 확인하고 왼쪽 또는 오른쪽으로 이동

137
00:07:03,000 --> 00:07:06,000
노드의 값보다 작거나보다 큰인지에 따라

138
00:07:06,000 --> 00:07:08,000
우리가 찾고있는 한.

139
00:07:08,000 --> 00:07:11,000
따라서, 13의 루트에서 시작, 우리는, 89가 큰 것을 알

140
00:07:11,000 --> 00:07:13,000
그래서 우리는 오른쪽으로 이동합니다.

141
00:07:13,000 --> 00:07:16,000
그럼 우리가 34의 노드를 확인하고 다시 우리는 오른쪽으로 이동합니다.

142
00:07:16,000 --> 00:07:20,000
89 여전히 55보다 큰, 그래서 우리는 오른쪽으로 계속.

143
00:07:20,000 --> 00:07:24,000
우리는 144의 값이있는 노드와 올라 와서 왼쪽으로 이동합니다.

144
00:07:24,000 --> 00:07:26,000
ro와 보라, 89 바로이 있습니다.

145
00:07:26,000 --> 00:07:31,000
>> 우리가 할 수있는 또 다른 것은 inorder 순회를 수행하여 모든 숫자를 인쇄합니다.

146
00:07:31,000 --> 00:07:35,000
inorder 순회는 왼쪽 하위 트리에 모든 출력을 의미합니다

147
00:07:35,000 --> 00:07:37,000
노드 자체를 인쇄하여 다음

148
00:07:37,000 --> 00:07:40,000
다음 오른쪽 하위 트리에 모든 출력이 나타납니다.

149
00:07:40,000 --> 00:07:43,000
예를 들어, 우리가 제일 좋아하는 이진 검색 트리를 봅시다

150
00:07:43,000 --> 00:07:46,000
그리고 정렬 순서 번호를 인쇄 할 수 있습니다.

151
00:07:46,000 --> 00:07:49,000
우리는 13 루트에서 시작하지만, 인쇄 13 전에 우리는 인쇄해야

152
00:07:49,000 --> 00:07:51,000
왼쪽 하위 트리의 모든.

153
00:07:51,000 --> 00:07:55,000
그래서 우리는 5로 이동합니다. 우리는 여전히 우리가 가장 왼쪽에있는 노드를 찾을 때까지 트리에서 깊이 내려 가야

154
00:07:55,000 --> 00:07:57,000
이는 0입니다.

155
00:07:57,000 --> 00:08:00,000
인쇄 제로 후, 우리는 1 돌아가서 그 아웃을 인쇄 할 수 있습니다.

156
00:08:00,000 --> 00:08:03,000
그럼 우리는 2 인, 오른쪽 하위 트리로 이동하여 그 곳을 인쇄 할 수 있습니다.

157
00:08:03,000 --> 00:08:05,000
이젠 우리는 그 하위 트리와 함께 완료

158
00:08:05,000 --> 00:08:07,000
우리는 3 다시 올라 가야지하고 인쇄 할 수 있습니다.

159
00:08:07,000 --> 00:08:11,000
백업 계속, 우리는 8 다음 5 인쇄합니다.

160
00:08:11,000 --> 00:08:13,000
이제 우리는 전체를 완료 한이 하위 트리를 왼쪽으로

161
00:08:13,000 --> 00:08:17,000
우리는 13를 인쇄하고 오른쪽 하위 트리 작업을 시작할 수 있습니다.

162
00:08:17,000 --> 00:08:21,000
우리는 34 아래로 뛰어 있지만, 인쇄 34 전에 우리는 왼쪽 하위 트리를 인쇄해야합니다.

163
00:08:21,000 --> 00:08:27,000
그래서 우리는 21를 인쇄 한 후 우리는 34 인쇄 및 오른쪽 하위 트리를 방문하게.

164
00:08:27,000 --> 00:08:31,000
55도 왼쪽 하위 트리가 없기 때문에, 우리는 그것을 인쇄하고 오른쪽 하위 트리에 계속합니다.

165
00:08:31,000 --> 00:08:36,000
144 왼쪽 하위 트리를 가지고 있으며, 그래서 우리는 144에 이어, 89 인쇄

166
00:08:36,000 --> 00:08:39,000
233의 마지막으로 가장 오른쪽 노드.

167
00:08:39,000 --> 00:08:44,000
당신이 그걸 가져가, 모든 번호가 낮은에서 높은 순서로 인쇄됩니다.

168
00:08:44,000 --> 00:08:47,000
>> 나무에 뭔가를 추가하는 것은 물론 상대적으로 통증이 있습니다.

169
00:08:47,000 --> 00:08:51,000
우리가해야 할 일은 우리 3 이진 검색 트리 속성을 준수인지 확인

170
00:08:51,000 --> 00:08:53,000
공간이있는 다음 값을 삽입합니다.

171
00:08:53,000 --> 00:08:55,000
자, 우리는 7의 값을 삽입 할 말한다.

172
00:08:55,000 --> 00:08:58,000
7 이하 13이기 때문에, 우리는 왼쪽으로 이동합니다.

173
00:08:58,000 --> 00:09:01,000
그러나 5보다 큰 해, 그래서 우리는 오른쪽으로 트래버스.

174
00:09:01,000 --> 00:09:04,000
그 8 8 잎 노드 미만입니다 때문에, 우리는 8 왼쪽 자녀 7 추가합니다.

175
00:09:04,000 --> 00:09:09,000
짜잔! 우리는 우리의 이진 검색 트리에 번호를 추가했습니다.

176
00:09:09,000 --> 00:09:12,000
>> 우리가 물건을 추가 할 수있는 경우, 우리는 더 나은뿐만 아니라 물건을 삭제할 수 있습니다.

177
00:09:12,000 --> 00:09:14,000
불행하게도 우리,​​ 삭제는 조금 더 복잡합니다 -

178
00:09:14,000 --> 00:09:16,000
많이하지만 조금 없습니다.

179
00:09:16,000 --> 00:09:18,000
우리가 생각해야하는 3 가지 시나리오가 있습니다

180
00:09:18,000 --> 00:09:21,000
이진 검색 나무에서 요소를 삭제합니다.

181
00:09:21,000 --> 00:09:24,000
첫째, 가장 쉬운 경우는 요소가 잎 노드이라는 것입니다.

182
00:09:24,000 --> 00:09:27,000
이 경우, 우리는 간단히 삭제하고 우리의 사업을 계속 이동합니다.

183
00:09:27,000 --> 00:09:30,000
우리가 방금 추가 한 7 삭제하려는 말해.

184
00:09:30,000 --> 00:09:34,000
음, 우리가 단순히 그것을 찾아 그것을 제거하고 그게 다에요.

185
00:09:35,000 --> 00:09:37,000
노드 만 어린이 1가있는 경우 다음 경우입니다.

186
00:09:37,000 --> 00:09:40,000
여기 노드를 삭제할 수 있지만, 우리가 처음 확인해야합니다

187
00:09:40,000 --> 00:09:42,000
지금 parentless 남아 그 하위 트리를 연결하는

188
00:09:42,000 --> 00:09:44,000
노드의 부모 우린 그냥 삭제되었습니다.

189
00:09:44,000 --> 00:09:47,000
우리는 나무에서 3 삭제하려는 말해.

190
00:09:47,000 --> 00:09:50,000
우리는 노드의 자식 요소를 가지고 노드의 부모에 첨부합니다.

191
00:09:50,000 --> 00:09:54,000
이 경우, 우리는 이제 5 1 장착하고 있습니다.

192
00:09:54,000 --> 00:09:57,000
우리가 알고 있기 때문에, 이진 검색 트리 속성에 따라 문제없이 작동

193
00:09:57,000 --> 00:10:01,000
3 왼쪽 하위 트리의 모든 것은보다 5 살.

194
00:10:01,000 --> 00:10:05,000
3의 하위 트리가 처리 할 수​​ 있기 때문에 이젠, 우리가 삭제할 수 있습니다.

195
00:10:05,000 --> 00:10:08,000
세 번째이자 마지막 경우가 가장 복잡합니다.

196
00:10:08,000 --> 00:10:11,000
우리가 삭제하려는 노드가 어린이 2 인이 때 경우가 있습니다.

197
00:10:11,000 --> 00:10:15,000
이 작업을 수행하기 위해, 우리는 먼저 다음 큰 값을 가진 노드를 찾아야 해

198
00:10:15,000 --> 00:10:18,000
두를 교체 한 후 문제의 노드를 삭제합니다.

199
00:10:18,000 --> 00:10:22,000
다음 가장 큰 값이 어린이 2 명 자체를 가질 수있는 노드를 확인합니다

200
00:10:22,000 --> 00:10:26,000
그 왼쪽의 아이가 다음 큰 더 나은 후보가 될 것입니다 때문입니다.

201
00:10:26,000 --> 00:10:30,000
따라서, 어린이 2 명으로 노드를 삭제하면, 2 노드의 교환을 보냈다

202
00:10:30,000 --> 00:10:33,000
그리고 삭제는 2 상기 규칙 1에 의해 처리됩니다.

203
00:10:33,000 --> 00:10:37,000
예를 들어, 우리는 루트 노드, 13를 삭제하려면 말한다.

204
00:10:37,000 --> 00:10:39,000
우리가 가장 먼저하는 일이 우리가 트리의 다음 큰 값을 찾을 수 있습니다

205
00:10:39,000 --> 00:10:41,000
이는,이 경우에는, 21입니다.

206
00:10:41,000 --> 00:10:46,000
우리는 13 잎 21 중앙 그룹 노드를 만드는 2 노드를 스왑.

207
00:10:46,000 --> 00:10:49,000
이제 우리는 단순히 13 삭제할 수 있습니다.

208
00:10:50,000 --> 00:10:53,000
>> 앞에서 언급에, 유효한 이진 검색 트리를 만드는 여러 가지 방법이 있습니다.

209
00:10:53,000 --> 00:10:56,000
불행하게도 우리,​​ 일부는 다른 것보다 더 있습니다.

210
00:10:56,000 --> 00:10:59,000
우리는 이진 검색 트리를 빌드 할 때 예를 들어, 어떤 현상이 발생

211
00:10:59,000 --> 00:11:01,000
숫자의 정렬 목록에서?

212
00:11:01,000 --> 00:11:04,000
모든 번호는 단지 각 단계에서 오른쪽에 추가됩니다.

213
00:11:04,000 --> 00:11:06,000
우리가 번호를 검색 할 때,

214
00:11:06,000 --> 00:11:08,000
우리는 선택의 여지가 없습니다 만 각 단계에 적절한 보는.

215
00:11:08,000 --> 00:11:11,000
이 전혀 선형 검색보다 더하지 않습니다.

216
00:11:11,000 --> 00:11:13,000
우리가 여기에 포함되지는 않지만, 더 복잡한, 기타 있습니다

217
00:11:13,000 --> 00:11:16,000
이런 일이 있지 않은지 확인하십시오 데이터 구조.

218
00:11:16,000 --> 00:11:18,000
그러나, 이러한 일을 방지하기 위해 수행 할 수있는 하나 간단한 일입니다

219
00:11:18,000 --> 00:11:21,000
그냥 무작위로 섞어 입력 값을합니다.

220
00:11:21,000 --> 00:11:26,000
그것은 임의 우연히 번호 질질 목록이 정렬되어 매우 가능성이 있습니다.

221
00:11:26,000 --> 00:11:29,000
이 경우라면, 카지노는 오랫동안 사업을 유지 않습니다.

222
00:11:29,000 --> 00:11:31,000
>> 당신이 그걸 있습니다.

223
00:11:31,000 --> 00:11:34,000
이제 이진 검색과 이진 검색 나무에 대해 알고.

224
00:11:34,000 --> 00:11:36,000
나는 패트릭 슈미트, 그리고이 CS50입니다.

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
확실한 방법은에서 목록을 검색하는 것 ... [신호음]

227
00:11:43,000 --> 00:11:46,000
... 항목의 수 ... 옙

228
00:11:46,000 --> 00:11:50,000
[웃음]

229
00:11:50,000 --> 00:11:55,000
... 234 ... augh의 노드를 게시 할 수 있습니다.

230
00:11:55,000 --> 00:11:58,000
>> 야호! 그건 -