1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Làm thế nào bạn sẽ đại diện cho tất cả các thành viên trong gia đình của bạn trong một máy tính?

2
00:00:10,790 --> 00:00:12,390
Chúng tôi chỉ đơn giản là có thể sử dụng một danh sách,

3
00:00:12,390 --> 00:00:14,400
nhưng có một hệ thống phân cấp rõ ràng ở đây.

4
00:00:14,400 --> 00:00:17,110
>> Hãy nói rằng chúng tôi đang bắt đầu với bà ngoại tuyệt vời của bạn, Alice.

5
00:00:17,110 --> 00:00:19,030
Cô có 2 con trai, Bob

6
00:00:19,030 --> 00:00:21,310
và ông nội của bạn, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie có 3 con,

8
00:00:23,190 --> 00:00:26,730
chú của bạn, Dave, cô, dì, Eve, và cha của bạn, Fred.

9
00:00:26,730 --> 00:00:28,750
Bạn là đứa con duy nhất của Fred.

10
00:00:28,750 --> 00:00:30,950
>> Tại sao tổ chức thành viên trong gia đình của bạn theo cách này

11
00:00:30,950 --> 00:00:34,010
là tốt hơn so với các đại diện danh sách đơn giản?

12
00:00:34,010 --> 00:00:36,630
Một lý do là cấu trúc phân cấp này,

13
00:00:36,630 --> 00:00:39,660
được gọi là một 'cây' chứa nhiều thông tin hơn một danh sách đơn giản.

14
00:00:40,540 --> 00:00:43,520
Chúng tôi biết các mối quan hệ gia đình giữa tất cả mọi người

15
00:00:43,520 --> 00:00:45,440
chỉ bằng cách kiểm tra các cây.

16
00:00:45,440 --> 00:00:47,250
Ngoài ra, nó có thể tăng tốc độ

17
00:00:47,250 --> 00:00:50,010
thời gian nhìn lên rất nhiều, nếu dữ liệu cây được sắp xếp.

18
00:00:50,010 --> 00:00:53,850
>> Chúng ta không thể tận dụng lợi thế của điều đó ở đây, nhưng chúng tôi sẽ sớm nhìn thấy một ví dụ về điều này.

19
00:00:53,850 --> 00:00:56,150
Mỗi người được đại diện bởi một nút trên cây.

20
00:00:56,680 --> 00:00:58,370
Nút có thể có các nút con

21
00:00:58,370 --> 00:01:00,350
cũng như một nút cha.

22
00:01:00,350 --> 00:01:02,390
Đây là những thuật ngữ kỹ thuật,

23
00:01:02,390 --> 00:01:05,220
ngay cả khi sử dụng cây cho những thứ bên cạnh gia đình.

24
00:01:05,220 --> 00:01:07,940
Alice của nút có 2 trẻ em và không có cha mẹ,

25
00:01:07,940 --> 00:01:11,500
trong khi Charlie nút có 3 trẻ em và cha mẹ 1.

26
00:01:11,500 --> 00:01:14,330
>> Một nút lá là một trong những mà không có bất kỳ trẻ em

27
00:01:14,330 --> 00:01:16,410
trên các cạnh bên ngoài của cây.

28
00:01:16,410 --> 00:01:18,520
Các nút trên cùng của cây, nút gốc,

29
00:01:18,520 --> 00:01:20,240
có không có cha mẹ.

30
00:01:20,240 --> 00:01:23,170
>> Một cây nhị phân là một loại hình cụ thể của cây,

31
00:01:23,170 --> 00:01:26,720
trong đó, nhiều nhất, mỗi node có 2 trẻ em.

32
00:01:26,720 --> 00:01:30,490
Dưới đây là cấu trúc của một nút của một cây nhị phân trong C.

33
00:01:31,560 --> 00:01:34,530
Mỗi nút có một số dữ liệu liên kết với nó

34
00:01:34,530 --> 00:01:36,520
và 2 con trỏ đến các nút khác.

35
00:01:36,520 --> 00:01:38,110
>> Trong cây gia đình của chúng tôi,

36
00:01:38,110 --> 00:01:40,900
các dữ liệu liên kết là tên của mỗi người.

37
00:01:40,900 --> 00:01:43,850
Ở đây nó là một int, mặc dù nó có thể là bất cứ điều gì.

38
00:01:44,510 --> 00:01:46,200
Khi nó quay ra,

39
00:01:46,200 --> 00:01:48,990
một cây nhị phân sẽ không được một đại diện tốt cho một gia đình,

40
00:01:48,990 --> 00:01:51,960
bởi vì người ta thường có nhiều hơn 2 trẻ em.

41
00:01:51,960 --> 00:01:53,510
>> Một cây nhị phân tìm kiếm

42
00:01:53,510 --> 00:01:56,380
là một loại lệnh đặc biệt của cây nhị phân

43
00:01:56,380 --> 00:01:58,090
cho phép chúng ta tìm một giá trị một cách nhanh chóng.

44
00:01:58,740 --> 00:02:00,050
Bạn có thể nhận thấy

45
00:02:00,050 --> 00:02:02,010
rằng tất cả các nút dưới gốc cây

46
00:02:02,010 --> 00:02:04,620
là gốc rễ của cây khác, được gọi là "cây con".

47
00:02:04,960 --> 00:02:07,090
Ở đây, gốc rễ của cây là 6,

48
00:02:07,090 --> 00:02:09,860
và con của nó, 2, là gốc rễ của một cây con.

49
00:02:09,860 --> 00:02:11,870
>> Trong một cây tìm kiếm nhị phân

50
00:02:11,870 --> 00:02:15,790
tất cả các giá trị của một nút bên phải subtree

51
00:02:15,790 --> 00:02:18,690
lớn hơn giá trị của nút. Ở đây: 6.

52
00:02:18,690 --> 00:02:22,640
Vâng, các giá trị trong trái cây con của một nút

53
00:02:24,540 --> 00:02:26,890
ít hơn giá trị của nút.

54
00:02:26,890 --> 00:02:28,620
Nếu chúng ta cần phải xử lý các giá trị nhân bản,

55
00:02:28,620 --> 00:02:31,760
chúng ta có thể thay đổi một trong những người đến sự bất bình đẳng lỏng lẻo,

56
00:02:31,760 --> 00:02:34,410
có nghĩa là giá trị giống nhau có thể rơi hoặc bên trái hoặc phải,

57
00:02:34,410 --> 00:02:37,400
miễn là chúng ta nhất quán về nó trong suốt.

58
00:02:37,400 --> 00:02:39,620
Cây này là một cây tìm kiếm nhị phân

59
00:02:39,620 --> 00:02:41,540
bởi vì nó theo các quy tắc này.

60
00:02:42,320 --> 00:02:46,020
>> Đây là cách nó sẽ xem xét nếu chúng tôi quay tất cả các nút vào cấu trúc của C.

61
00:02:46,880 --> 00:02:48,410
Chú ý rằng nếu một đứa trẻ bị mất tích,

62
00:02:48,410 --> 00:02:50,340
con trỏ là null.

63
00:02:50,340 --> 00:02:53,270
Làm thế nào để chúng tôi kiểm tra xem nếu 7 là trong cây?

64
00:02:53,270 --> 00:02:55,020
Chúng tôi bắt đầu ở gốc.

65
00:02:55,020 --> 00:02:58,690
Bảy là lớn hơn 6, vì vậy nếu nó trong cây, nó phải là bên phải.

66
00:02:59,680 --> 00:03:03,650
Sau đó, nó ít hơn 8, vì vậy nó phải được để lại.

67
00:03:03,650 --> 00:03:06,210
Ở đây, chúng tôi đã tìm thấy 7.

68
00:03:06,210 --> 00:03:08,160
Bây giờ, chúng tôi sẽ kiểm tra 5.

69
00:03:08,160 --> 00:03:11,500
Năm là ít hơn 6, vì vậy nó phải được bên trái.

70
00:03:11,500 --> 00:03:13,460
Năm là lớn hơn 2,

71
00:03:13,460 --> 00:03:15,010
vì vậy nó phải được quyền,

72
00:03:15,010 --> 00:03:18,100
và nó cũng là lớn hơn 4, vì vậy nó phải được đúng một lần nữa.

73
00:03:18,100 --> 00:03:20,300
Tuy nhiên, có không có trẻ em nào ở đây.

74
00:03:20,300 --> 00:03:22,000
Con trỏ là null.

75
00:03:22,000 --> 00:03:24,270
Điều này có nghĩa là 5 không phải là cây của chúng tôi.

76
00:03:24,270 --> 00:03:27,250
>> Chúng ta có thể tìm kiếm cây nhị phân với mã sau đây:

77
00:03:28,430 --> 00:03:31,140
Tại mỗi nút, chúng ta kiểm tra xem liệu chúng ta đã tìm thấy

78
00:03:31,140 --> 00:03:33,020
giá trị chúng tôi đang tìm kiếm.

79
00:03:33,020 --> 00:03:35,740
Nếu chúng ta không tìm thấy nó, chúng tôi xác định nếu nó phải là

80
00:03:35,740 --> 00:03:38,990
trên và sang trái hoặc phải kiểm tra xem cây con.

81
00:03:38,990 --> 00:03:41,160
Vòng lặp này sẽ tiếp tục xuống cây

82
00:03:41,160 --> 00:03:44,190
cho đến khi không có nút con ở hai bên trái hoặc phải.

83
00:03:45,190 --> 00:03:48,600
>> Hãy nhớ rằng 5 trong cây.

84
00:03:48,600 --> 00:03:50,460
Làm thế nào để chúng ta chèn nó?

85
00:03:50,460 --> 00:03:52,370
Quá trình này trông giống như để tìm kiếm.

86
00:03:52,370 --> 00:03:54,830
Chúng tôi lặp xuống cây bắt đầu từ 6,

87
00:03:54,830 --> 00:03:57,040
trái đến 2,

88
00:03:57,040 --> 00:03:59,140
quyền 4,

89
00:03:59,140 --> 00:04:02,500
và phải một lần nữa, nhưng 4 không có con bên này.

90
00:04:02,500 --> 00:04:06,090
Đây sẽ là vị trí mới cho 5,

91
00:04:06,090 --> 00:04:08,500
và nó sẽ bắt đầu không có con.

92
00:04:09,020 --> 00:04:12,220
>> Nhanh như thế nào là hoạt động trên một cây tìm kiếm nhị phân?

93
00:04:12,220 --> 00:04:15,410
Hãy nhớ rằng Bigohnotation tìm cách cung cấp một trên ràng buộc.

94
00:04:15,410 --> 00:04:17,390
Trong trường hợp xấu nhất,

95
00:04:17,390 --> 00:04:19,480
cây của chúng tôi chỉ đơn giản là có thể là một danh sách liên kết

96
00:04:19,480 --> 00:04:22,220
có nghĩa là chèn, xóa, và tìm kiếm

97
00:04:22,220 --> 00:04:25,380
có thể mất thời gian tỷ lệ thuận với số lượng các nút trong cây.

98
00:04:25,380 --> 00:04:27,380
Đây là O (n).

99
00:04:27,380 --> 00:04:30,690
>> Ví dụ, sau đây là một cây nhị phân tìm kiếm hợp lệ.

100
00:04:31,850 --> 00:04:34,020
Tuy nhiên, nếu chúng ta cố gắng để tìm 9,

101
00:04:34,020 --> 00:04:36,760
chúng ta phải đi qua tất cả các nút.

102
00:04:36,760 --> 00:04:39,120
Nó không phải là tốt hơn so với một danh sách liên kết.

103
00:04:39,120 --> 00:04:41,410
Lý tưởng nhất, chúng tôi muốn tất cả các nút

104
00:04:41,410 --> 00:04:44,120
của cây tìm kiếm nhị phân của chúng tôi có 2 con.

105
00:04:44,120 --> 00:04:46,370
Bằng cách này, chèn, xóa và tìm kiếm

106
00:04:46,370 --> 00:04:50,190
sẽ mất, lúc tồi tệ nhất, O (log n) thời gian.

107
00:04:50,190 --> 00:04:52,470
Cây từ trước khi có thể được cân bằng hơn,

108
00:04:52,470 --> 00:04:54,140
như thế này.

109
00:04:54,140 --> 00:04:57,980
Bây giờ, nhìn lên bất kỳ giá trị nào có, nhiều nhất là 3 bước.

110
00:04:57,980 --> 00:04:59,460
Cây này là cân bằng,

111
00:04:59,460 --> 00:05:01,190
có nghĩa là có độ sâu tối thiểu

112
00:05:01,190 --> 00:05:03,680
liên quan đến số lượng các nút.

113
00:05:03,680 --> 00:05:06,300
>> Tìm kiếm một giá trị trong một cây tìm kiếm nhị phân cân bằng

114
00:05:06,300 --> 00:05:09,540
tương tự như tìm kiếm nhị phân trên một mảng được sắp xếp.

115
00:05:09,540 --> 00:05:12,290
Trong thực tế, nếu chúng ta không cần để chèn hoặc xóa các mục,

116
00:05:12,290 --> 00:05:15,150
họ cư xử chính xác theo cùng một cách.

117
00:05:15,150 --> 00:05:17,600
Tuy nhiên, một cấu trúc cây là tốt hơn

118
00:05:17,600 --> 00:05:19,530
cho thêm vào xử lý và xóa bỏ

119
00:05:20,360 --> 00:05:22,670
>> Tên tôi là Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Đây là CS50.