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
看時間大幅增加，如果樹對數據進行排序。

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
Alice的節點有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
在這裡，它是一個int，但它可以是任何東西。

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的結構。

61
00:02:46,880 --> 00:02:48,410
請注意，如果一個孩子失踪，

62
00:02:48,410 --> 00:02:50,340
指針為空。

63
00:02:50,340 --> 00:02:53,270
我們如何檢查，看看在樹上嗎？

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
>> 請記住，是不是在樹中。

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
我們的二叉搜索樹，有2個孩子。

105
00:04:44,120 --> 00:04:46,370
通過這種方式，插入，刪除和搜索

106
00:04:46,370 --> 00:04:50,190
所做的那樣，在最壞的情況下，O（log 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。