1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] 당신은 컴퓨터에 모든 가족을 어떻게 대표까요?

2
00:00:10,790 --> 00:00:12,390
우리는 단순히 목록을 사용할 수

3
00:00:12,390 --> 00:00:14,400
하지만 명확한 계층 구조가 있어요.

4
00:00:14,400 --> 00:00:17,110
>> 자, 우리가 네 증조 할머니 앨리스로 시작하고 있다고 가정 해 보겠습니다.

5
00:00:17,110 --> 00:00:19,030
그녀는 두 아들 밥이

6
00:00:19,030 --> 00:00:21,310
할아버지와 찰리.

7
00:00:21,310 --> 00:00:23,190
찰리는 3 명

8
00:00:23,190 --> 00:00:26,730
삼촌이, 데이브, 이모, 이브, 그리고 아버지 프레드.

9
00:00:26,730 --> 00:00:28,750
당신은 프레드의 유일한 아이입니다.

10
00:00:28,750 --> 00:00:30,950
>> 왜 이런 방식으로 귀하의 가족을 조직 것

11
00:00:30,950 --> 00:00:34,010
간단한 목록 표현보다 더 나은?

12
00:00:34,010 --> 00:00:36,630
이유 중 하나는 그이 계층 구조,

13
00:00:36,630 --> 00:00:39,660
라는 '나무'를 간단한 목록보다 더 많은 정보가 포함되어 있습니다.

14
00:00:40,540 --> 00:00:43,520
우리는 모든 사람들 사이의 가족 관계를 알

15
00:00:43,520 --> 00:00:45,440
그냥 나무를 검토하여.

16
00:00:45,440 --> 00:00:47,250
또한, 그것은 속도를 높일 수 있습니다

17
00:00:47,250 --> 00:00:50,010
룩 - 업 (look-up) 시간 엄청난, 나무 데이터가 정렬되어있는 경우.

18
00:00:50,010 --> 00:00:53,850
>> 우리는 여기 활용할 수는 없지만, 우리는 곧이의 예를 볼 수 있습니다.

19
00:00:53,850 --> 00:00:56,150
각 사람은 트리에서 노드로 표시됩니다.

20
00:00:56,680 --> 00:00:58,370
노드는 자식 노드를 가질 수 있습니다

21
00:00:58,370 --> 00:01:00,350
뿐만 아니라 부모 노드 있습니다.

22
00:01:00,350 --> 00:01:02,390
다음은, 기술적 인 용어입니다

23
00:01:02,390 --> 00:01:05,220
가족 이외의 일을위한 나무를 사용하는 경우에도.

24
00:01:05,220 --> 00:01:07,940
앨리스의 노드는, 어린이 2 명없이 부모가

25
00:01:07,940 --> 00:01:11,500
찰리의 노드는 3 명이 1 부모가있을 때.

26
00:01:11,500 --> 00:01:14,330
>> 잎 노드는 아이가없는 하나입니다

27
00:01:14,330 --> 00:01:16,410
나무의 바깥 가장자리에.

28
00:01:16,410 --> 00:01:18,520
트리의 최상위 노드, 루트 노드,

29
00:01:18,520 --> 00:01:20,240
상위가 없습니다.

30
00:01:20,240 --> 00:01:23,170
>> 이진 트리, 트리의 특정 유형입니다

31
00:01:23,170 --> 00:01:26,720
어떤의 각 노드는 대부분에서 어린이 2 명이이 있습니다.

32
00:01:26,720 --> 00:01:30,490
여기 C.에있는 이진 트리의 노드의 구조체는

33
00:01:31,560 --> 00:01:34,530
모든 노드는 관련 일부 데이터가

34
00:01:34,530 --> 00:01:36,520
다른 노드와 2 개의 포인터.

35
00:01:36,520 --> 00:01:38,110
>> 우리 가족 트리에서

36
00:01:38,110 --> 00:01:40,900
관련 데이터는 각 사람의 이름이었다.

37
00:01:40,900 --> 00:01:43,850
그것은 아무 것도 될 수 있지만 여기가, 정수입니다.

38
00:01:44,510 --> 00:01:46,200
그것은 밝혀

39
00:01:46,200 --> 00:01:48,990
이진 나무, 가족에 대한 좋은 표현되지 않을 것

40
00:01:48,990 --> 00:01:51,960
사람들은 자주 이상 어린이 2 명을 가지고 있으니까.

41
00:01:51,960 --> 00:01:53,510
>> 이진 검색 트리

42
00:01:53,510 --> 00:01:56,380
이진 트리의 특별한 명령 유형

43
00:01:56,380 --> 00:01:58,090
그 우리는 신속하게 값을 볼 수 있습니다.

44
00:01:58,740 --> 00:02:00,050
알아 챘 수 있습니다

45
00:02:00,050 --> 00:02:02,010
그 트리의 루트 아래의 모든 노드

46
00:02:02,010 --> 00:02:04,620
다른 나무의 뿌리는 '하위 트리'이라고합니다.

47
00:02:04,960 --> 00:02:07,090
여기서, 트리의 루트는 6입니다

48
00:02:07,090 --> 00:02:09,860
와 자녀, 2, 하위 트리의 루트입니다.

49
00:02:09,860 --> 00:02:11,870
>> 이진 검색 트리에서

50
00:02:11,870 --> 00:02:15,790
노드의 모든 값은 오른쪽 하위 트리입니다

51
00:02:15,790 --> 00:02:18,690
노드의 값보다 큰 수 있습니다. 여기 : 6.

52
00:02:18,690 --> 00:02:22,640
음, 노드의 왼쪽 하위 트리의 값

53
00:02:24,540 --> 00:02:26,890
노드의 값보다 적습니다.

54
00:02:26,890 --> 00:02:28,620
우리는 중복 값을 처리해야하는 경우,

55
00:02:28,620 --> 00:02:31,760
우리는 느슨한 불평등에 두 사람들의 변경할 수 있습니다

56
00:02:31,760 --> 00:02:34,410
동일한 값이 왼쪽 또는 오른쪽에 하나 빠질 수 즉,

57
00:02:34,410 --> 00:02:37,400
오래 우리가 내내 그것에 대해 일관성 때문입니다.

58
00:02:37,400 --> 00:02:39,620
이 나무는 이진 검색 트리입니다

59
00:02:39,620 --> 00:02:41,540
그것은 다음과 같은 규칙을 따른다 때문입니다.

60
00:02:42,320 --> 00:02:46,020
>> 이것은 우리가 C의 structs에 모든 노드를 설정하는 경우는 표시 방식입니다.

61
00:02:46,880 --> 00:02:48,410
주의 그 아이가 누락 된 경우,

62
00:02:48,410 --> 00:02:50,340
포인터가 null입니다.

63
00:02:50,340 --> 00:02:53,270
우리가 어떻게 7 트리에 있는지 확인합니까?

64
00:02:53,270 --> 00:02:55,020
우리는 루트에서 시작합니다.

65
00:02:55,020 --> 00:02:58,690
이 트리에 있다면 세븐은 6보다 큰이기 때문에, 그것은 오른쪽에 있어야합니다.

66
00:02:59,680 --> 00:03:03,650
그런 다음 8 미만이므로 왼쪽으로해야합니다.

67
00:03:03,650 --> 00:03:06,210
여기, 우리는 7을 발견했습니다.

68
00:03:06,210 --> 00:03:08,160
이제, 우리는 5 확인합니다.

69
00:03:08,160 --> 00:03:11,500
다섯은 6 미만이므로 왼쪽에 있어야합니다.

70
00:03:11,500 --> 00:03:13,460
다섯는 2보다 큰 수 있습니다

71
00:03:13,460 --> 00:03:15,010
그래서, 오른쪽이어야합니다

72
00:03:15,010 --> 00:03:18,100
그리고 또한 4보다 큰 때문에 바로 다시해야합니다.

73
00:03:18,100 --> 00:03:20,300
그러나, 어떤 아이는 여기에 없습니다.

74
00:03:20,300 --> 00:03:22,000
포인터가 null입니다.

75
00:03:22,000 --> 00:03:24,270
이 5 우리 나무에없는 것을 의미합니다.

76
00:03:24,270 --> 00:03:27,250
>> 우리는 다음 코드와 바이너리 트리를 검색 할 수 있습니다 :

77
00:03:28,430 --> 00:03:31,140
모든 노드에서, 우리는 우리가 발견 한 경우 확인

78
00:03:31,140 --> 00:03:33,020
우리가 찾고있는 값입니다.

79
00:03:33,020 --> 00:03:35,740
우리가 찾을 수없는 경우가있을 경우, 우리는 결정

80
00:03:35,740 --> 00:03:38,990
왼쪽 또는 오른쪽에 그 하위 구조를 확인합니다.

81
00:03:38,990 --> 00:03:41,160
이 루프는 나무를 계속

82
00:03:41,160 --> 00:03:44,190
왼쪽 또는 오른쪽 중 하나에 자식 노드가 없을 때까지.

83
00:03:45,190 --> 00:03:48,600
>> 5 트리에 존재하지 않았을 기억하십시오.

84
00:03:48,600 --> 00:03:50,460
우리가 어떻게 그것을 삽입하려면 어떻게해야합니까?

85
00:03:50,460 --> 00:03:52,370
이 과정은 검색 유사 해 보입니다.

86
00:03:52,370 --> 00:03:54,830
우리는 6부터 나무를 반복

87
00:03:54,830 --> 00:03:57,040
2 왼쪽,

88
00:03:57,040 --> 00:03:59,140
4 자,

89
00:03:59,140 --> 00:04:02,500
오른쪽 다시하지만, 4 저쪽에 자식이 없습니다.

90
00:04:02,500 --> 00:04:06,090
이 5의 새로운 위치 될 것입니다

91
00:04:06,090 --> 00:04:08,500
그리고 아무 아이들과 함께 시작됩니다.

92
00:04:09,020 --> 00:04:12,220
>> 얼마나 빨리 이진 검색 트리에서 작업입니까?

93
00:04:12,220 --> 00:04:15,410
Bigohnotation가 상위 바운드를 제공하고자 기억하십시오.

94
00:04:15,410 --> 00:04:17,390
최악의 경우,

95
00:04:17,390 --> 00:04:19,480
우리 나무는 단순히 링크 된 목록이 될 수 있습니다

96
00:04:19,480 --> 00:04:22,220
그 삽입, 삭제, 검색을 의미

97
00:04:22,220 --> 00:04:25,380
트리의 노드의 수에 비례 시간이 걸릴 수 있습니다.

98
00:04:25,380 --> 00:04:27,380
이 O (n)이됩니다.

99
00:04:27,380 --> 00:04:30,690
>> 예를 들어, 다음은 올바른 이진 검색 트리입니다.

100
00:04:31,850 --> 00:04:34,020
그러나, 우리는 9 찾으려고하면

101
00:04:34,020 --> 00:04:36,760
우리는 모든 노드를 통과해야합니다.

102
00:04:36,760 --> 00:04:39,120
이 연결리스트보다 더 좋은하지 않습니다.

103
00:04:39,120 --> 00:04:41,410
이상적으로, 우리는 모든 노드를 원하는 것

104
00:04:41,410 --> 00:04:44,120
우리의 이진 검색 트리의 두 자녀가 있습니다.

105
00:04:44,120 --> 00:04:46,370
이 방법, 삽입, 삭제 및 검색

106
00:04:46,370 --> 00:04:50,190
, 최악의, O (로그 n)이 시간이 걸릴 것입니다.

107
00:04:50,190 --> 00:04:52,470
이전의 나무가 더 균형이 될 수 있습니다

108
00:04:52,470 --> 00:04:54,140
이처럼.

109
00:04:54,140 --> 00:04:57,980
이제 어떤 값을 찾는 것은 3 단계, 대부분의시 소요됩니다.

110
00:04:57,980 --> 00:04:59,460
이 나무는 균형이다

111
00:04:59,460 --> 00:05:01,190
이 의미는 최소한의 깊이가

112
00:05:01,190 --> 00:05:03,680
노드의 수를 기준으로.

113
00:05:03,680 --> 00:05:06,300
>> 균형 이진 검색 트리에서 값을 찾고

114
00:05:06,300 --> 00:05:09,540
정렬 배열에서 바이너리 검색 유사합니다.

115
00:05:09,540 --> 00:05:12,290
사실, 우리가 항목을 삽입하거나 삭제할 필요가없는 경우는,

116
00:05:12,290 --> 00:05:15,150
그들은 정확히 동일한 방식으로 동작합니다.

117
00:05:15,150 --> 00:05:17,600
그러나, 트리 구조가 더 좋아

118
00:05:17,600 --> 00:05:19,530
처리 삽입과 삭제에 대한

119
00:05:20,360 --> 00:05:22,670
>> 내 이름은 Bannus 반 데르 Kloot입니다.

120
00:05:22,670 --> 00:05:24,030
이 CS50입니다.